Time Limit : 30 Second
Memory Limit : 256 MB
Submission: 851
Solved: 213
Description
在图论中,包含n个结点(结点编号为1~n)、n-1条边的无向连通图被称为树。
在树中,任意一对结点间的简单路径总是惟一的。
你拥有一棵白色的树——所有节点都是白色的。接下来,你需要处理c条指令:


修改指令(0 v):改变一个给定结点的颜色(白变黑,黑变白);
查询指令(1 v):询问从结点1到一个给定结点所经过的第一个黑色结点编号(假设沿着简单路径走)。
注意,在查询指令中,必须从结点1而不是结点v出发。如果结点1本身就是黑色,查询指令应该返回1。
Input
第一行包含两个正整数n, c,即结点数和指令条数,n和c都不大于1,000,000.
以下n-1行,每行两个正整数(ui, vi) (1 <= ui < vi <= n),表示结点ui到vi之间有一条无向边。
以下c行,每行两个整数(c, v)。当c=0时表示修改指令,其中v代表被修改的结点编号;c=1时表示查询指令。
你的程序需要输出结点1到结点v之间路径的第一个黑色结点编号。
在第一条指令执行前,所有结点都是白色的。
Output
对于每个查询操作(c=1的操作),输出一行,包含一个整数,即第一个黑色结点的编号。如果不存在黑色结点,输出-1。

sample input
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 
sample output
-1
8
-1
2
-1 
hint
source
AStar 2008
Submit