Dylans loves tree

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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.

Hint

hujie

Source

BestCoder Round #45

提交代码