L. Little Gas Station
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The students of some programming summer camp love going to a meeting place known by all as the little gas station. For some reason, the city they currently live in can be thought of as having $$$n$$$ road intersections, with a total of $$$n - 1$$$ roads. From every intersection, you can reach every other one. They loved going to the same little gas station as always, which was originally located at the intersection whose label is $$$1$$$. However, the students sometimes complained that they had to walk too much in order to get to the original little gas station, as they could sometimes be on the other side of town.

Thus, a businessman from out of town appeared in order to help these poor students. Depending on the day, this businessman would build a replica of the original little gas station at some intersection $$$x$$$ (he would never build in an intersection that already contains a gas station). The owner of the original little gas station, furious with this new businessman, would, depending on the day, destroy one of the businessman's gas station replicas. However, the students simply didn't care enough about this fight between them, so given a day in which they wanted to hang out at a little gas station, they'd go to the nearest to the intersection they're currently at.

This fight lasted for $$$q$$$ days, and on each day, one of three events could occur: the businessman could build a replica at intersection $$$x$$$, the original owner could destroy a replica at intersection $$$y$$$, or the students, currently at intersection $$$z$$$, want to find out the minimum amount of roads they need to cover to reach any little gas station.

Input

The first line contains two integers, $$$n$$$ and $$$q$$$, $$$(1 \leq n \leq 2 \times 10^5)$$$, $$$(1 \leq q \leq 2 \times 10^5)$$$ — the amount of intersections and days the conflict lasted.

The next $$$n - 1$$$ lines describe the structure of the city; the $$$i^{th}$$$ line contains two integers, $$$a_i$$$, $$$b_i$$$, $$$(1 \leq a_i, b_i \leq n)$$$, $$$(a_i \neq b_i)$$$ — the roads $$$a_i$$$ and $$$b_i$$$ are connected via a road.

The next $$$q$$$ lines will contain information about the event that occurs on the $$$i^{th}$$$ day. Each line will start with an integer $$$t_i$$$, $$$(1 \leq t \leq 3)$$$ — the type of event that occurs on that day.

  • For $$$t_i = 1$$$, an integer $$$x$$$, $$$(2 \leq x \leq n)$$$ will be followed, indicating that a gas station will be built on the road with id $$$x$$$. It is guaranteed that the businessman doesn't try to build on an intersection that already has a gas station.
  • For $$$t_i = 2$$$, an integer $$$y$$$, $$$(2 \leq y \leq n)$$$ will be followed, indicating that the replica present at intersection $$$y$$$ will be destroyed. It is guaranteed that there is a replica at intersection $$$y$$$.
  • For $$$t_i = 3$$$, an integer $$$z$$$, $$$(1 \leq z \leq n)$$$ will be followed, indicating which intersection the students are at. For this type of query, print out the minimum amount of roads that need to be traversed in order to reach the closest gas station. It is guaranteed that there will be at least one day of this type.
Output

For every day in which $$$t_i = 3$$$, output the minimum amount of roads that need to be traversed, with each one being on separate lines.

Example
Input
7 5
1 2
1 3
2 4
2 5
3 6
3 7
1 2
1 3
3 7
2 3
3 7
Output
1
2
Note

When the first $$$t_i = 3$$$ query is made, the closest node to $$$7$$$ is $$$3$$$, and we can see that the distance is equal to one. Once this gas station is destroyed, the closest one to $$$7$$$ is $$$1$$$.