First black vertex on a path

You have a tree with $N$ vertices. A tree is a connected undirected graph with no cycle. The vertices are numbered 1 to $N$, and every vertex starts out white.

Write a program that processes the following two queries in the order they are given.

• 1 i: flip the colour of vertex $i$. White becomes black, and black becomes white.
• 2 v: walk the path from vertex 1 to vertex $v$, starting at vertex 1, and print the number of the first black vertex you meet. If the path holds no black vertex, print -1.

The path includes vertex 1 and vertex $v$. A tree has exactly one path between two vertices, so each query has a single answer.

The first line has the number of vertices $N$. ($2 \le N \le 100000$)

Each of the next $N-1$ lines has the numbers $u$ and $v$ of the two vertices joined by one edge. ($1 \le u, v \le N$, $u \ne v$) The $N-1$ edges always form a tree.

The next line has the number of queries $M$. ($1 \le M \le 100000$)

Each of the next $M$ lines has one query, either 1 i or 2 v. ($1 \le i, v \le N$)

For each query of type 2, print its answer on one line, in the order the queries are given.