P4116 Qtree3

题目描述

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

有两种操作：

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

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

输入格式

第一行两个整数 $N \ Q \ (1 \le N \le 10^6 , 1 \le Q \le 10^5）$，表示 $N$ 个点和 $Q$ 个操作。

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

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

输出格式

对每个 1 v 操作输出结果

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