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:
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.
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.
Sample Input 1
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
1 3 2 1
Explanation to Sample 1
After operation 1, the heavy edges are ~(1,3)~; ~(3,6)~; ~(6,7)~.
In operation 2, the only heavy edge on the path from vertex ~1~ to vertex ~4~ is ~(1,3)~.
In operation 3, the heavy edges on the path from vertex ~2~ to vertex ~7~ are ~(1,3)~; ~(3,6)~; ~(6,7)~.
After operation 4, ~(1,3)~ and ~(3,6)~ will become light edges first, and then ~(1,3)~ and ~(3,5)~ will become heavy edges.
In operation 5, the heavy edges on the path from vertex ~2~ to vertex ~7~ are ~(1,3)~ and ~(6,7)~.
After operation 6, edge ~(1,3)~ will become a light edge while ~(1,2)~ will become a heavy edge.
In operation 7, the heavy edge on the path from vertex ~1~ to vertex ~7~ is edge ~(6,7)~.
Sample inputs and outputs can be found here.
- Sample 2 (
edge2.ans) corespond to cases 3-6.
- Sample 3 (
edge3.ans) corespond to cases 9-10.
- Sample 4 (
edge4.ans) corespond to cases 11-14.
- Sample 5 (
edge5.ans) corespond to cases 17-20.
For all test sets, ~T \le 3~, ~1 \le n,m \le 10^5~.
|Test Case||~n,m \le~||Additional Constraints|
|15~16||~2 \times 10^4~||None.|
Constraint A means the tree is a path.
Constraint B means for operations of the second type, ~a_i~ and ~b_i~ are directly connected by an edge.