You are given a tree with $N$ nodes and $Q$ questions.
All nodes have a value.Nodes on tree is numbered by $1~N$.
The questions have two types:
¢Ù$0$ $x$ $y$:Change node $x$'s value to $y$
¢Ú$1$ $x$ $y$ :you should output the maxinum times of some value that in the path from node $x$ to node $y$,
Input
In the first line there is a number $T$¡ª¡ªThe test numbers.
(In the finall test $T \leq 5$,and there are at most $2$ tests that $N>100$.)
For each test:
In the first line there are two numbers $N$ and $Q$.
In the next $N-1$ lines there are pairs of $(X,Y)$.It means there is a road between $x$ and $y$.
In the following line there are $N$ numbers $A_1..A_N$.$A_i$ means the value of node $i$ in the initial time.
In the last $Q$ lines there are three numbers.The meaning is above.
$1 \leq N,Q \leq 50000$,the value is in $[1,n]$.
You'd better print the enter in the last line when you hack others.
You'd better not print space in the last of each line when you hack others.
