409024 - 树上再询问

给出一棵有 N 个节点的树(无环无向连通图)。树节点的编号从 1 到 N。一开始,树中任何结点的颜色都是白色。有如下操作: 0 I:改变第 I 个结点的颜色(由白色变为黑色,或由黑色变为白色); 1 v:查询从结点 1 到结点 v 的路径上第一个黑色节点的 id,如果不存在,输出 -1。

Input

第一行有两个整数 N 和 Q。 随后 N – 1 行,每行两个整数 a 和 b,表示 a 和 b 有一条边。 随后 Q 行为 “0 i” 或 “1 v” 的操作(1 ≤ i,v ≤ N)。

Output

对于每组 “1 v” 的操作,输出结果。

Examples

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

Output

-1
8
-1
2
-1

Hint

对于 1 / 3 的数据有 N = 5000, Q = 400000。 对于 1 / 3 的数据有 N = 10000, Q = 300000。 对于 1 / 3 的数据有 N = 100000, Q = 100000。 此外,有 1 ≤ i, v ≤ N。

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题