30142 - Qtree3
时间限制 : 1 秒
内存限制 : 128 MB
给出 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。