Description

Wayte has a tree with $n$ nodes, and every edge on the tree is either a light edge or a heavy edge. You're going to perform $m$ operations on the tree. Prior to any operation, all edges on the tree are light edges. There are two types of operations:

1. Given two points $a$ and $b$, first for each point $x$ along the path from $a$ to $b$ (including $a$ and $b$), you make all edges incident to $x$ light edges. Then change all edges in the path from $a$ to $b$ to heavy edges.
2. Given two points $a$ and $b$, you need to figure out the current count of heavy edges in the path from $a$ to $b$.

Input Format

Each test contains multiple test cases. The first line contains a integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$. $n$ is the number of nodes, and $m$ is the number of operations.

Next $n-1$ lines each contain two integers $u,v$, indicating an edge on the tree.

Next $m$ lines each contain three integers $op_i,a_i,b_i$, describing an operation, where $op_i=1$ denotes operation type $1$, and $op_i=2$ denotes operation type $2$.

It is guaranteed that $a_i \neq b_i$ in tests.

Output Format

For each type-$2$ operation, print a line of one integer equal to its result.

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

1
3
2
1

Sample Explanation 1

After the $1$st operation, heavy edges are: $(1,3)$, $(3,6)$, $(6,7)$.

In the $2$nd operation, involved heavy edge: $(1,3)$.

In the $3$rd operation, involved heavy edges: $(1,3)$, $(3,6)$, $(6,7)$.

In the $4$th operation, first $(1,3)$ and $(3,6)$ become light edges, then $(1,3)$ and $(3,5)$ become heavy edges.

In the $5$th operation, involved heavy edges: $(1,3)$, $(6,7)$.

In the $6$th operation, first $(1,3)$ becomes a light edge, then $(1,2)$ becomes a heavy edge.

In the $7$th operation, involved heavy edge: $(6,7)$.

Sample 2

See attached files edge2.in and edge2.ans. Constraints of this sample is the same as test cases $3 \sim 6$.

Sample 3

See attached files edge3.in and edge2.ans. Constraints of this sample is the same as test cases $9 \sim 10$.

Sample 4

See attached files edge4.in and edge4.ans. Constraints of this sample is the same as test cases $11 \sim 14$.

Sample 5

See attached files edge5.in and edge5.ans. Constraints of this sample is the same as test cases $17 \sim 20$.

Constraints and Specification

For all the tests, $T \leq 3$, $1 \leq n,m \leq 10^5$.

Special case $A$: the tree is isomorphic to a chain.

Special case $B$: $a_i$ and $b_i$ given by type-$2$ operations are directly connected by an edge.