You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

有两种操作：

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

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

输入格式

第一行 $N$，$Q$，表示 $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

提示

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

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

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

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