Connect the Tree

You are given a tree with $N$ nodes. You should process $M$ queries of two types:

$1 \ x \ y$: $(x, y)$ is an edge from the initial tree. If the edge $(x, y)$ is still in the tree, delete it, else add it back.

$2 \ x \ y$: this output is either $0$ or $1$. Consider that total is the sum of all the previous type 2 queries. Then compute $x_{new} = (x + total) \text{ mod } N + 1$, $y_{new} = (y + total) \text{ mod } N + 1$.

Output $1$ if you can reach $y_{new}$ from $x_{new}$, or $0$ if you cannot.

Input data

The first line of the input will contain $N$, $M$.

On the next $N-1$ lines you will find the description of the tree. On each line there will be a pair ($x, y$), representing that there will be an edge between $x$ and $y$.

On the next $M$ lines you will find a triplet ($t, x, y$) representing a query, $t$ is $1$ or $2$.

Output data

The output will contain as many lines as there are type $2$ queries in the input. The $i^{th}$ line will contain the answer for the $i^{th}$ type $2$ query.

Constraints and clarifications

• $2 \leq N, M \leq 2.5 \cdot 10^5$
• For tests worth $25$ points, $1 \leq N, M \leq 1 \ 000$.
• For tests worth $15$ more points, $1 \leq N \leq 1 \ 000$.

Example

stdin

5 3
1 4
4 2
5 2
3 5
2 1 3
1 2 5
2 1 3

stdout

1
1