← 返回题目列表

Codeforces · 825/G

G. 树查询

中文机器翻译题面 查看原题

给你一棵由 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