给你一棵由 n 个顶点(编号从 1 到 n)组成的树。最初所有顶点都是白色的。您必须处理两种不同类型的 q 查询:
1. 1 x — 将顶点 x 的颜色更改为黑色。保证第一个查询将是这种类型。
2. 2 x — 对于顶点 x,找到最小索引 y,使得索引 y 的顶点属于从 x 到某个黑色顶点的简单路径(简单路径不会多次访问任何顶点)。
对于类型 2 的每个查询,打印其答案。
请注意,查询是以修改后的方式给出的。
输入
第一行包含两个数字 n 和 q (3 ≤ n, q ≤ 106)。
接下来是 n - 1 行,每行包含两个数字 xi 和 yi (1 ≤ xi < yi ≤ n) 并表示顶点 xi 和 yi 之间的边。
保证这些边形成一棵树。
接下来是 q 行。每行包含两个整数 ti 和 zi,其中 ti 是第 i 个查询的类型,zi 可用于以这种方式恢复此查询的 xi:您必须跟踪类型 2 的最后一个查询的答案(我们将此答案称为“last”,最初为“last = 0”);那么 xi = (zi + 最后) mod n + 1。
保证第一个查询是类型1,并且至少有一个查询是类型2。
输出
对于类型 2 的每个查询,输出其答案。
示例
输入 #1
4 6 1 2 2 3 3 4 1 2 1 2 2 2 1 3 2 2 2 2
输出 #1
3 2 1