3728. [SPOJ 2798]Qtree3

【题目描述】

给出 $N$ 个点的一棵树（$N-1$ 条边），节点有白有黑，初始全为白。

有两种操作：

0 i：改变某点的颜色（原来是黑的变白，原来是白的变黑）。

1 v：询问 $1$ 到 $v$ 的路径上的第一个黑点，若无，输出 $-1$。

【输入格式】

第一行 $N$，$Q$，表示 $N$ 个点和 $Q$ 个操作。

第二行到第 $N$ 行 $N-1$ 条无向边。

再之后 $Q$ 行，每行一个操作 0 i 或者 1 v。

【输出格式】

对每个 1 v 操作输出结果

【样例 1 输入】

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 输出】

-1
8
-1
2
-1

【数据范围】

对于 $1/3$ 的数据有 $N=5000,Q=400000$。

对于 $1/3$ 的数据有 $N=10000,Q=300000$。

对于 $1/3$ 的数据有 $N=100000, Q=100000$。

此外，有$1 \le i,v \le N$。