Count on a Tree II Striking Back

You are given a tree with $n$ nodes. The tree nodes are numbered from $1$ to $n$. The color of the $i$-th node is $col_i$.

You need to perform the following operations for $m$ times:

· "$\texttt{1 x y}$" ($1\leq x,y\leq n$): Change the color of the $x$-th node into $y$.

· "$\texttt{2 a b c d}$" ($1\leq a,b,c,d\leq n$): Let's denote $f(u,v)$ as the number of different colors occured on the path from $u$ to $v$. You need to answer whether $f(a,b)>f(c,d)$ is true.

The first line of the input contains a single integer $T$ ($1 \leq T \leq 4$), the number of test cases.

For each case, the first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 500\,000$, $1\leq m\leq 10\,000$), denoting the number of nodes and the number of operations.

The second line of the input contains $n$ integers $col_1,col_2,\dots,col_n$ ($1\leq col_i\leq n$), denoting the initial color of each node.

Each of the following $n-1$ lines contains two integers $u_i$ and $v_i$ ($1\leq u_i,v_i\leq n,u_i\neq v_i$), denoting an bidirectional edge between the $u_i$-th node and the $v_i$-th node.

Each of the next $m$ lines describes an operation in formats described in the statement above, except that some parameters are encrypted in order to enforce online processing.

Let $cnt$ be the number of queries that you answered "$\texttt{Yes}$" before in this test case. Note that $cnt$ should be reset to $0$ in each new test case. For each operation, $x,y,a,b,c$ and $d$ are encrypted. The actual values of $x,y,a,b,c$ and $d$ are $x\oplus cnt,y\oplus cnt,a\oplus cnt,b\oplus cnt,c\oplus cnt$ and $d\oplus cnt$. In the expressions above, the symbol "$\oplus$" denotes the bitwise exclusive-or operation. Also note that the constraints described in the statement above apply to the corresponding parameters only after decryption, the encrypted values are not subject to those constraints.

It is guaranteed that $f(a,b)\geq 2f(c,d)$ or $f(c,d)\geq 2f(a,b)$ always holds for each query.

For each query, print a single line. If $f(a,b)>f(c,d)$ is true, print "$\texttt{Yes}$" else print "$\texttt{No}$".

1
8 4
1 2 1 4 1 3 3 2
1 2
2 3
3 4
3 5
1 6
6 7
6 8
2 1 4 3 5
2 7 6 5 9
1 4 9
2 2 4 7 6

Yes
No
Yes

2020 Multi-University Training Contest 2