Problem Description

Xiao W has a tree with $n$ nodes. Each edge in the tree can be either a light edge or a heavy edge. Next, you need to perform $m$ operations on the tree. Before all operations start, all edges in the tree are light edges. There are two types of operations:

1. Given two nodes $a$ and $b$, first, for every node $x$ on the path from $a$ to $b$ (including $a$ and $b$), you must change all edges incident to $x$ into light edges. Then, change all edges on the path from $a$ to $b$ into heavy edges.
2. Given two nodes $a$ and $b$, you need to compute how many heavy edges are currently on the path from $a$ to $b$.

Input Format

This problem has multiple test cases. The first line of the input contains a positive integer $T$, which indicates the number of test cases. For each test case:

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

The next $n - 1$ lines each contain two integers $u\ v$, representing an edge in the tree.

The next $m$ lines each contain three integers ${\mathit{op}}_i\ a_i\ b_i$, describing an operation, where ${\mathit{op}}_i = 1$ denotes an operation of type 1, and ${\mathit{op}}_i = 2$ denotes an operation of type 2.

The data guarantees that $a_i \neq b_i$.

Output Format

For each operation of type 2, output one line containing one integer, which is the answer.

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

Hint

[Sample Explanation #1]

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

In the 2nd operation, the heavy edges on the path are: $(1, 3)$.

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

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

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

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

In the 7th operation, the heavy edges on the path are: $(6, 7)$.

[Sample #2]

See the attachments edge/edge2.in and edge/edge2.ans.

The constraints of this sample are consistent with test points $3 \sim 6$.

[Sample #3]

See the attachments edge/edge3.in and edge/edge3.ans.

The constraints of this sample are consistent with test points $9 \sim 10$.

[Sample #4]

See the attachments edge/edge4.in and edge/edge4.ans.

The constraints of this sample are consistent with test points $11 \sim 14$.

[Sample #5]

See the attachments edge/edge5.in and edge/edge5.ans.

The constraints of this sample are consistent with test points $17 \sim 20$.

[Constraints]

For all testdata: $T \le 3$, $1 \le n, m \le {10}^5$.

Special property A: The tree is a chain.

Special property B: In each type 2 operation, $a_i$ and $b_i$ are directly connected by an edge.

Translated by ChatGPT 5