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$。