M. Witch Trial
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Your trident has struck a villager again. This time, when the trial ends, you discover that you can no longer find it.

You know that the trident landed on a rooted tree $$$T$$$ with $$$n$$$ vertices, rooted at vertex $$$1$$$. Each vertex has a weight $$$a_i$$$, and at every moment these weights form a permutation of $$$1 \sim n$$$. For vertices $$$u,v$$$, let $$$P(u,v)$$$ be their simple path, including both $$$u$$$ and $$$v$$$.

A set $$$S$$$ of tree vertices is a trident if and only if there exist three vertices $$$F,x,y$$$ (which may be equal) satisfying:

  • $$$F$$$ is an ancestor of $$$x$$$, or $$$F=x$$$;
  • $$$F$$$ is an ancestor of $$$y$$$, or $$$F=y$$$;
  • $$$S = P(F,x)\cup P(F,y)$$$；

Process $$$q$$$ operations in order. There are three types:

Operation 1: Lightning. Given vertices $$$x$$$ and $$$y$$$, swap their current weights.

Operation 2: Judgment. Given two distinct weights $$$l \lt r$$$, reverse the weights within $$$[l,r]$$$.

Formally, if vertex $$$x$$$ has weight $$$a_x$$$ before this operation and $$$a'_x$$$ afterward, define $$$$$$ a'_x= \begin{cases} l+r-a_x, & l\le a_x\le r,\\ a_x, & \text{otherwise}. \end{cases} $$$$$$

Then set $$$a_x\leftarrow a'_x$$$ simultaneously for every integer $$$1 \le x \le n$$$. The weights remain a permutation of $$$1 \sim n$$$.

Operation 3: Find the trident. Given $$$l \le r$$$, determine whether $$$S=\{x\in N,\ 1\le x\le n\mid l\le a_x\le r\}$$$ is a trident.

Answer all questions from Operation 3 in order.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^3$$$), the number of test cases.

The first line of each test case contains two integers $$$n,q$$$ ($$$1 \le n,q \le 10^5$$$), the numbers of tree vertices and operations.

Each of the next $$$n-1$$$ lines contains two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$, $$$u\ne v$$$), describing a tree edge.

The next line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$), the initial vertex weights.

Each of the next $$$q$$$ lines describes an operation. It starts with an integer $$$\text{op}_i$$$ ($$$1 \le \text{op}_i \le 3$$$), followed by:

  • If $$$\text{op}_i=1$$$, two integers $$$x,y$$$ ($$$1 \le x,y \le n$$$): perform Operation 1, swapping their weights.
  • If $$$\text{op}_i=2$$$, two integers $$$l,r$$$ ($$$1 \le l \lt r \le n$$$): perform Operation 2, reversing the weights in $$$[l,r]$$$.
  • If $$$\text{op}_i=3$$$, two integers $$$l,r$$$ ($$$1 \le l \le r \le n$$$): perform Operation 3, asking whether the vertices with weights in $$$[l,r]$$$ form a trident.

Within each test case, the initial weights form a permutation of $$$1\sim n$$$, and the given edges form a tree with $$$n$$$ vertices.

Across all test cases, $$$\sum n \le 3 \times 10^5$$$ and $$$\sum q \le 3 \times 10^5$$$.

Output

For each Operation 3, output one line:

  • Output YES if $$$S=\{x\in N,\ 1\le x\le n\mid l\le a_x\le r\}$$$ is a trident;
  • Otherwise, output NO.

The answer is case-insensitive; for example, yes, YES, Yes, and YeS are all accepted as affirmative answers.

Example
Input
1
7 6
1 2
1 3
2 4
2 5
3 6
3 7
4 2 6 1 3 5 7
3 1 3
3 1 5
2 1 7
3 4 7
1 4 5
3 5 7
Output
YES
NO
YES
YES
Note

For the third trident query in the first test case, after the preceding Judgment operation, the current weights are $$$$$$ (a_1,a_2,\ldots,a_7)=(4,6,2,7,5,3,1). $$$$$$

Weights $$$4,5,6,7$$$ are at vertices $$$1,5,2,4$$$, respectively, so $$$S=\{1,2,4,5\}$$$.

Choose $$$F=1$$$, $$$x=4$$$, and $$$y=5$$$. Then:

  • Vertex $$$1$$$ is an ancestor of vertex $$$4$$$.
  • Vertex $$$1$$$ is an ancestor of vertex $$$5$$$.
  • $$$ P(1,4)\cup P(1,5) =\{1,2,4\}\cup\{1,2,5\}=S$$$。

Therefore, $$$S$$$ is a trident.