hld2

Description

You are given a tree with $N$ vertices where the $i^\text{th}$ edge connects vertices $u_i$ and $v_i$. Each edge on this tree is either a light or a heavy edge. Initially, all edges are light.

You should process the following $Q$ operation of $2$ types:

• $\texttt{1 a b}$, for all edges
  • if two of the endpoints of the edge are contained in the path from $a$ to $b$, then the edge becomes heavy
  • if one of the endpoints of the edge are contained in the path from $a$ to $b$, the edge becomes light
• $\texttt{2 a b}$ count the number of heavy edges on the path from $a$ to $b$

Input

Each test contains multiple test cases. The first line of input contains a single integer $T$, the number of test cases. The description of the test cases follows.

The first line of each test case contains two integer $N$ and $Q$, the size of the tree and the number of operations you need to process.

The following $N-1$ lines of each test case contains two integer $u_i$ and $v_i$, describing the vertices that the $i^\text{th}$ edge connects.

The following $Q$ lines of each test case contains three integers $op_i$, $a_i$ and $b_i$, describing an operation.

Output

For each operation of type $2$, print the answer in a separate line.

Constraints

• $1 \leq T \leq 3$
• $1 \leq N,Q \leq 10^5$
• $1 \leq u_i,v_i \leq N$
• It is guaranteed that the given edges form a tree.
• $op_i \in {1,2}$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$

Subtasks

• $N,Q \leq 5~000$ ($10$ points)
• each vertex is directly connected to at most $2$ other vertices and for the second type of operation, $a_i$ and $b_i$ are directly connected by an edge ($10$ points)
• each vertex is directly connected to at most $2$ other vertices ($20$ points)
• for the second type of operation, $a_i$ and $b_i$ are directly connected by an edge ($20$ points)
• $N,Q \leq 20~000$ ($20$ points)
• No additional constraints ($20$ points)

Sample Input

1
7 7
1 2
1 3
3 4
3 5
3 6
6 7
1 1 7
2 1 4
2 2 7
1 1 5
2 2 7
1 2 1
2 1 7

Sample Output

1
3
2
1