Description

Given a tree with $N$ nodes ($N-1$ edges). Each node is either white or black, and initially all nodes are white.

There are two operations:

0 i: Toggle the color of a node (black becomes white, white becomes black).

1 v: Query the first black node on the path from $1$ to $v$; if none, output -1.

Input Format

The first line contains $N$ and $Q$, the number of nodes and the number of operations.

Lines $2$ through $N$ contain the $N-1$ undirected edges.

Then $Q$ lines follow, each containing one operation 0 i or 1 v.

Output Format

For each 1 v operation, output the result.

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

-1
8
-1
2
-1

Hint

For $1/3$ of the testdata, $N=5000,Q=400000$.

For $1/3$ of the testdata, $N=10000,Q=300000$.

For $1/3$ of the testdata, $N=100000, Q=100000$.

In addition, $1 \le i,v \le N$.

Translated by ChatGPT 5