There is a tree (an undirected connected acyclic graph) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. Initially, all vertices are colored white.

Write a program that processes the following two types of queries:

• 1 i: Toggle the color of vertex $i$ (white -> black, black -> white).
• 2 v: Output the number of the first black vertex on the path from vertex $1$ to vertex $v$. If no such vertex exists, output $-1$.

Input

The first line contains $N$ ($2 \le N \le 100{,}000$).

The next $N-1$ lines each contain two integers $u$ and $v$, the endpoints of the $i$-th edge.

The next line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

The next $M$ lines each contain one query.

Output

For each type 2 query, output the result in order, one per line.

Examples

Input 1

9
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
8
2 3
1 8
2 6
2 7
1 2
2 9
1 2
2 9

Output 1

-1
8
-1
2
-1