Road Redirection

View as PDF

Submit solution

Points: 17
Time limit: 0.5s
Memory limit: 256M

Author:
Problem types

Once upon a time, Nella lived in a peaceful village with N buildings and N-1 roads, where it was possible to reach any building from any other. One day, a large earthquake struck and directed all the roads! Since communication is extremely important, Nella would like to establish one building as the town hall, where it is possible to reach any building from the town hall after redirecting some amount of roads. Even worse for the village is that the roads started to redirect themselves randomly due to the instability caused by the earthquake! Being in this horrible situation, Nella would like you to write a program for him that supports 2 types of operations:

  1. 1 b: Nella would like to know how many roads he would have to redirect to make building b the town hall.

  2. 2 r: Flip the direction of road r.

Please help him before his village is destroyed!

Input Specification

The first line will contain 2 integers N and Q, the number of buildings and the number of operations.

The next N-1 lines will contain 2 integers u_i and v_i, indicating a one-way connection from building u_i to v_i.

The next Q lines will contain 2 integers each. The first integer will be t_i, the type of the operation. If t_i is 1, b_i will follow, indicating that the first operation will be performed on building b_i. If t_i is 2, r_i will follow, indicating that the second operation will be performed on road r_i. Note that the roads are identified by the order they are given in the input.

Output Specification

For the ith type 1 operation, output one line containing the number of roads Nella would have to redirect to make b_i the town hall.

Constraints

1 \le N, Q \le 2 \times 10^5

1 \le u_i, v_i, b_i \le N

1 \le r_i \le N-1

1 \le t_i \le 2

Sample Input

4 5
1 4
2 4
3 4
1 1
1 4
1 2
2 2
1 1

Sample Output

2
3
2
1

Explanation

Initially, the graph looks like this:

After the 4th operation, the graph looks like this:


Comments

There are no comments at the moment.