该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。当地部门正在对村庄进行重建。

题目描述

B 地区共有 $N$ 个村庄，编号从 $1$ 到 $N$。所有村庄被若干条公路连成一棵树，村庄 1 是树根。

现在村庄 $1$ 已经重建完成。

小 A 作为重建村庄的负责人，接到了上级部门发来的 $M$ 个命令，他需要依次执行。

命令分为两种类型：

• 0 i 表示修建命令，小 A 需要立刻组织工人重建村庄 i。可能有些村庄会多次重建。
• 1 i 表示回复命令，小 A 需要回复上级部门，在村庄 i 到村庄 1 的路径上，离村庄 i 最近的重建过的村庄是哪一个？（包括村庄 i 本身）

你能帮助小 A 吗？

输入格式

第一行包含两个整数 $N, M$，依次表示村庄的数目、命令的数目。

接下来 $N-1$ 行，每行 $2$ 个整数 $i, j$，表示村庄 $i$ 与村庄 $j$ 之间有一条公路。

接下来 $M$ 行，按顺序依次给出了每个命令：每行 $2$ 个整数 $k, i$，其中 $k$ 只可能为 $0$ 或 $1$，含义如题目所述。

输出格式

对于每个回复命令，输出小 A 回复的答案，每个回复答案占一行。

样例输入

5 5
1 2
1 3
2 4
2 5
1 2
0 2
1 2
1 5
1 3

样例输出

1
2
2
1

数据范围

100% 的数据：$1 ≤ N, M ≤ 100000， 1 ≤ i, j ≤ N， k ∈ \{0,1\}。$