Dylans loves tree

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$

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)$.

For each question ② in each testcase,if the value all appear even times output "-1",otherwise output the value that appears odd times.

1
3 2
1 2
2 3
1 1 1
1 1 2
1 1 3

-1
1

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.

BestCoder Round #45