给出一棵有 N 个节点的树(无环无向连通图)。树节点的编号从 1 到 N。一开始,树中任何结点的颜色都是白色。有如下操作: 0 I:改变第 I 个结点的颜色(由白色变为黑色,或由黑色变为白色); 1 v:查询从结点 1 到结点 v 的路径上第一个黑色节点的 id,如果不存在,输出 -1。
第一行有两个整数 N 和 Q。 随后 N – 1 行,每行两个整数 a 和 b,表示 a 和 b 有一条边。 随后 Q 行为 “0 i” 或 “1 v” 的操作(1 ≤ i,v ≤ N)。
对于每组 “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 ≤ i, v ≤ N。