*【树链剖分】Qtree3 加强版
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
P4116 Qtree3
题目描述
给出 个点的一棵树（ 条边），节点有白有黑，初始全为白。
有两种操作：
0 i：改变某点的颜色（原来是黑的变白，原来是白的变黑）。
1 v：询问 到 的路径上的第一个黑点，若无，输出 。
输入格式
第一行两个整数 ，表示 个点和 个操作。
第二行到第 行 条无向边。
再之后 行，每行一个操作 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