Dylans is given a tree with $N$ nodes.
All nodes have a value $A[i]$.Nodes on tree is numbered by $1 \sim N$.
Then he is given $Q$ questions like that:
¢Ù$0 \ x \ y$£ºchange node $x's$ value to $y$
¢Ú$1 \ x \ y$£ºFor all the value in the path from $x$ to $y$,do they all appear even times?
For each ¢Ú question,it guarantees that there is at most one value that appears odd times on the path.
$1 \leq N,Q \leq 100000$, the value $A[i]¡ÊN$ and $A[i] \leq 100000$
Input
In the first line there is a test number $T$.
($T \leq 3$ and there is at most one testcase that $N > 1000$)
For each testcase:
In the first line there are two numbers $N$ and $Q$.
Then in the next $N - 1$ lines there are pairs of $(X,Y)$ that stand for a road from $x$ to $y$.
Then in the next line there are $N$ numbers $A_1..A_N$ stand for value.
In the next $Q$ lines there are three numbers$(opt,x,y)$.
Output
For each question ¢Ú in each testcase,if the value all appear even times output "-1",otherwise output the value that appears odd times.
Sample Input
1
3 2
1 2
2 3
1 1 1
1 1 2
1 1 3
Sample Output
-1
1
Hint
If you want to hack someone,N and Q in your testdata must smaller than 10000£¬and you shouldn't print any space in each end of the line.
