Query on a tree again!

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem

Initially every vertex is white. An update toggles the color of one vertex. A query asks for the first black vertex encountered on the path from root 1 to vertex $v$, or -1 if no such vertex exists.

Input

The first line contains $n$ and $q$. The next $n-1$ lines contain the tree edges. Each of the following $q$ lines is one of:

• 0 i: toggle vertex $i$ between white and black.
• 1 v: query the first black vertex on the path from root 1 to $v$.

Output

For each query of type 1, print the requested vertex, or -1 if none exists.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n\le10^5$.
• The number of operations follows the input format above.

Example

Input

1 13
0 1
1 1
0 1
1 1
0 1
1 1
1 1
0 1
1 1
1 1
1 1
1 1
0 1

Output

1
-1
1
1
-1
-1
-1
-1

Explanation

The only vertex is repeatedly toggled. A query therefore returns 1 exactly when that vertex is black.