30142 - 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/3 的数据有 N=5000,Q=400000。

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

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

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