CF825G.Tree Queries

You are given a tree consisting of n vertices (numbered from 1 to n). Initially all vertices are white. You have to process q queries of two different types:

1. 1 x — change the color of vertex x to black. It is guaranteed that the first query will be of this type.
2. 2 x — for the vertex x, find the minimum index y such that the vertex with index y belongs to the simple path from x to some black vertex (a simple path never visits any vertex more than once).

For each query of type 2 print the answer to it.

Note that the queries are given in modified way.

给你一棵由 $n$ 个顶点（编号从 $1$ 到 $n$）构成的树。初始时所有顶点均为白色。你需要处理 $q$ 个查询，查询分为两种类型：

1. 1 x —— 将顶点 $x$ 的颜色改为黑色。保证第一个查询必为该类型。
2. 2 x —— 对于顶点 $x$，找出最小的索引 $y$，使得编号为 $y$ 的顶点位于从 $x$ 到某个黑色顶点的简单路径上（简单路径中任意顶点至多被访问一次）。

对每个类型为 2 的查询，输出其答案。

注意：查询以某种修改后的方式给出。

The first line contains two numbers n and q (3 ≤ n, q ≤ 106).

Then n - 1 lines follow, each line containing two numbers x__i and y__i (1 ≤ x__i < y__i ≤ n) and representing the edge between vertices x__i and y__i.

It is guaranteed that these edges form a tree.

Then q lines follow. Each line contains two integers t__i and z__i, where t__i is the type of _i_th query, and z__i can be used to restore x__i for this query in this way: you have to keep track of the answer to the last query of type 2 (let's call this answer last, and initially last = 0); then x__i = (z__i + last) mod n + 1.

It is guaranteed that the first query is of type 1, and there is at least one query of type 2.

第一行包含两个整数 $n$ 和 $q$（$3 \leq n, q \leq 10^6$）。

接下来 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i < y_i \leq n$），表示顶点 $x_i$ 与 $y_i$ 之间的一条边。

保证这些边构成一棵树。

随后是 $q$ 行。每行包含两个整数 $t_i$ 和 $z_i$，其中 $t_i$ 表示第 $i$ 个查询的类型；而 $z_i$ 可用于按如下方式还原该查询的 $x_i$：你需要记录上一个类型为 2 的查询的答案（记作 $last$，初始时 $last = 0$）；然后 $x_i = (z_i + last) \bmod n + 1$。

保证第一个查询的类型为 1，且至少存在一个类型为 2 的查询。

For each query of type 2 output the answer to it.

对于每个类型为 2 的查询，输出其答案。