Connect the Tree

Time limit: 1s Memory limit: 64MB Input: Output:

You are given a tree with NN nodes. You should process MM queries of two types:

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

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

Output 11 if you can reach ynewy_{new} from xnewx_{new}, or 00 if you cannot.

Input data

The first line of the input will contain NN, MM.

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

On the next MM lines you will find a triplet (t,x,yt, x, y) representing a query, tt is 11 or 22.

Output data

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

Constraints and clarifications

  • 2N,M2.51052 \leq N, M \leq 2.5 \cdot 10^5
  • For tests worth 2525 points, 1N,M1 0001 \leq N, M \leq 1 \ 000.
  • For tests worth 1515 more points, 1N1 0001 \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

Log in or sign up to be able to send submissions!