Tree Path Black Query

You are given a tree with \(N\) nodes (and \(N-1\) edges). Each node is initially white. The nodes can be toggled between white and black. You are to process two types of operations:

• 0 i: Toggle the color of node \(i\) (if it is white, it becomes black; if black, it becomes white).
• 1 v: Query the unique path from node \(1\) to node \(v\) and output the first black node encountered along this path (starting from node \(1\)). If there is no black node on the path, output \(-1\).

The tree is rooted at node \(1\) for the purpose of the queries.

inputFormat

The first line of input contains a single integer \(N\) denoting the number of nodes in the tree.

The next \(N-1\) lines each contain two integers \(u\) and \(v\) which represent an edge between nodes \(u\) and \(v\).

The next line contains an integer \(Q\) denoting the number of operations.

The following \(Q\) lines each describe an operation in one of the following two formats:

• 0 i — Toggle the color of node \(i\).
• 1 v — Query the path from node \(1\) to node \(v\) for the first black node.

outputFormat

For each query of type 1 v, output one line containing the index of the first black node on the path from node \(1\) to \(v\). If there is no black node, output \(-1\).

sample

5
1 2
1 3
3 4
3 5
5
1 5
0 3
1 5
0 1
1 4

-1
3
1