## NOI '21 P1 - Light Heavy Edges

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

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

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

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

#### Input Specification

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

For the next lines, each line contains two integers and denoting an edge of the tree.

For the next lines, each line contains three integers denoting an operation. means the operation is an operation of the first type, while means the operation is an operation of the second type.

It's guaranteed that in all operations.

#### Output Specification

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 for Sample Output 1

After operation 1, the heavy edges are ; ; .

In operation 2, the only heavy edge on the path from vertex to vertex is .

In operation 3, the heavy edges on the path from vertex to vertex are ; ; .

After operation 4, and will become light edges first, and then and will become heavy edges.

In operation 5, the heavy edges on the path from vertex to vertex are and .

After operation 6, edge will become a light edge while will become a heavy edge.

In operation 7, the heavy edge on the path from vertex to vertex is edge .

Sample inputs and outputs can be found here.

• Sample 2 (edge2.in and edge2.ans) corresponds to cases 3-6.
• Sample 3 (edge3.in and edge3.ans) corresponds to cases 9-10.
• Sample 4 (edge4.in and edge4.ans) corresponds to cases 11-14.
• Sample 5 (edge5.in and edge5.ans) corresponds to cases 17-20.

#### Constraints

For all test sets, , .

Test Case Additional Constraints
1~2 None.
3~6 7~8 A,B
9~10 A
11~14 B
15~16 None.
17~20 Constraint A means the tree is a path.
Constraint B means for operations of the second type, and are directly connected by an edge.