题目描述

一棵树有 $n$ 个节点，初始均为白色，有两种操作：

1. 1 x：代表把结点 $x$ 设置为黑色；

2. 2 x：代表查询 $x$ 到树上任意一个黑色结点的简单路径上的编号最小的结点的编号。

输入 $t$ 和 $z$，其中 $t$ 表示操作类型，$x=(last+z)\mod n +1$，$last$ 代表上一次询问答案，初始为 $0$，保证第一个操作为 $1$。

输入格式

第一行两个整数 $n,q$，$3 \le n, q \le 10^6$。

接下来 $n-1$ 行，每行两个整数 $x_i,y_i$。

接下来 $q$ 行，每行两个整数 $t_i,z_i$。

输出格式

对于每个询问，在一行中输出一个整数表示答案。

4 6
1 2
2 3
3 4
1 2
1 2
2 2
1 3
2 2
2 2

3
2
1