25065번 - Light Heavy Edges 다국어

There is a tree with $n$ vertices. An edge of the tree may be either a light edge or a heavy edge. You need to perform $m$ operations on the tree. Initially, all edges on the tree are light edges. There are two operations:

1. Given two vertices $a$ and $b$, for all $x$ on the path between $a$ and $b$ (including $a$ and $b$ themselves), you need to turn all edges connected with $x$ into light edges, and turn all edges on the path between $a$ and $b$ into heavy edges.

2. Given two vertices $a$ and $b$, you need to compute the number of heavy edges on the path between $a$ and $b$.

The first line is an integer $T$ denoting the number of test cases. For each test case, the first line has two integers $n$ and $m$ where $n$ is the number of vertices and $m$ is the number of operations.

For the next $n-1$ lines, each line contains two integers $u$ and $v$ denoting an edge of the tree.

For the next $m$ lines, each line contains three integers $op_i,a_i,b_i$ denoting an operation. $op_i = 1$ means the operation is an operation of the first type, while $op_i = 2$ means the operation is an operation of the second type.

It's guaranteed that $a_i \ne b_i$ in all operations.

For each operation of the second type, output an integer denoting the answer to the query.

For all test sets, $T \le 3$, $1 \le n,m \le 10^5$.