Lele wants to see apricot blossoms and is always on the road to see them.

Lele is always on the road to see apricot blossoms, but the world is too big and the flowering period of apricot blossoms is too short. At some moment, the apricot blossoms in a certain place bloom, and at another moment, they fall. Lele knows that always heading towards the nearest apricot blossoms does not guarantee she will arrive before they fall, so she decides to use a dice to decide which path to take.

However, she always wants to know how far away the nearest blooming apricot blossoms are.

The world map is summarized by Lele as a connected graph with $n$ nodes and $n-1$ edges, where each node has an apricot tree. After finishing her complex dynamic out-of-order multi-issue processor, Lele decides to spend $m$ units of time searching for apricot blossoms. That is to say, within $m$ units of time, one of the following three events will occur at each unit of time:

• Apricot blossoms in a certain place bloom.
• Apricot blossoms in a certain place fall.
• Lele moves to a node adjacent to her current node.

Lele is initially at node 1.

Input

The first line contains two integers $n$ and $m$, representing the number of nodes and the time, respectively.

The next $n-1$ lines each contain two integers $x$ and $y$, representing an edge between $x$ and $y$.

The next $m$ lines each contain two integers $op$ and $x$:

• If $op = 1$, it means the state of the apricot blossoms at node $x$ has changed. If there were blooming apricot blossoms at node $x$ before, they now wither; if there were no blooming apricot blossoms at node $x$ before, they now bloom.
• If $op = 2$, it means Lele has moved to node $x$. It is guaranteed that node $x$ is adjacent to the node where Lele was previously located.

Output

Output $m$ lines. The $i$-th line represents the distance from Lele to the nearest blooming apricot blossoms at time $i$. If there are no blooming apricot blossoms, output "2147483648".

Examples

Input 1

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

Output 1

2147483648
0
0
1

Note

$1 \le n, m \le 10^5$, $op \in \{1, 2\}$, $1 \le x \le n$.