#3319. 黑白树

题目描述

给定一棵树，边的颜色为黑或白，初始时全部为白色。维护两个操作：

1.查询u到根路径上的第一条黑色边的标号。

2.将u到v 路径上的所有边的颜色设为黑色。

Notice:这棵树的根节点为1

输入格式

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

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

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

1 v 表示第一个操作

2 v u 表示第二种操作

n，m<=10^6

输出格式

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

样例

样例输入

5 4  

1 2  

1 3  

2 4  

2 5  

1 2  

2 2 3  

1 3  

1 4

样例输出

0  

2  

1

数据范围与提示

2018.6.2新加数据两组By Cansult