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 b: Nella would like to know how many roads he would have to redirect to make building ~b~ the town hall.
2 r: Flip the direction of road ~r~.
Please help him before his village is destroyed!
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.
For the ~i~th type 1 operation, output one line containing the number of roads Nella would have to redirect to make ~b_i~ the town hall.
~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~
4 5 1 4 2 4 3 4 1 1 1 4 1 2 2 2 1 1
2 3 2 1
Initially, the graph looks like this:
After the 4th operation, the graph looks like this: