题目描述

给定一棵树，根节点编号为 $1$，边的颜色为黑或白，初始时全部为白色。维护两个操作：

• 查询 $u$ 到根路径上的第一条黑色边的标号。
• 将 $u$ 到 $v$ 路径上的所有边的颜色设为黑色。

输入格式

第一行两个数 $n,m$，分别表示点数和操作数。

接下来的 $n-1$ 行，每行两个整数 $u,v$，表示一条 $u$ 到 $v$ 的边。

接下来的 $m$ 行，每行为以下格式：

• $1 \ v$ 表示第一个操作；

• $2 \ v \ u$ 表示第二种操作。

输出格式

对于每个询问，输出相应答案。如果不存在，输出 $0$。

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

0
2
1

数据范围

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$。