Close Node

A tree on $N$ nodes labeled with integers between $0$ and $N-1$ is given. Initially, all nodes are white, except node $0$ which is black. Your task is to answer two types of queries:

• Type $0$: given node $u$, change the color of node $u$ from white to black

• Type $1$: given node $u$, print the distance between $u$ and the closest black node, measured in number of crossed edges

If a node is given in a query of type $0$, it is guaranteed to be white at that point in time.

Input

The first line of input contains the integers $N$ and $Q$ ($1 \leq N,Q \leq 2*10^5$), the number of nodes and queries.

The following $N-1$ lines each contain the integers $a$ and $b$ ($0 \leq a,b \leq N-1$), which means that there is an edge between node $a$ and $b$. These edges are guaranteed to form a tree.

Then, the next $Q$ each contain a query. Each query start with the integer $T$.

If $T=0$, the next integer is $u$ ($0 \leq u \leq N-1$), the node to be changed from white to black.

If $T=1$, the next integer is $u$ ($0 \leq u \leq N-1$), the node for which we want to know the distance to the nearest black node.

Output

For each query where $T=1$, print the smallest number of edges you need to cross to go from node $u$ to a black node.

Scoring

Your solution will be tested on multiple testcases. To solve the problem, your solution must solve every testcase correctly.

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

0
3
2