There is a tree (a connected graph with no undirected cycles) consisting of $N$ vertices. Vertices are numbered from $1$ to $N$, and edges are numbered from $1$ to $N-1$. Initially, all vertices are black.

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

• 1 i: Toggle the color of vertex $i$ (white $\to$ black, black $\to$ white).
• 2 v: Print the minimum distance from vertex $v$ to any white vertex $u$ (it is allowed that $u = v$). If $v$ itself is white, the answer is $0$. If there are no white vertices in the tree, print $-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 two endpoints of edge $i$.

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

The following $M$ lines each contain one query.

Output

For each type‑2 query, print the result on its own line, in the order they appear.

Examples

Input 1

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

Output 1

2
2
2
3
0