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
Time Limit: 3 Seconds
Memory Limit: 1024MB
No. of ACs: 7
Your best score: 0
Source: LOJ P3532

Subtask Score
1 10
2 10
3 20
4 20
5 20
6 20
7 0