黑白树

时间限制:10s      空间限制:512MB

题目描述

给定一棵树,边的颜色为黑或白,初始时全部为白色。维护两个操作:
 
 
1.查询u到根路径上的第一条黑色边的标号。
2.将u到v    路径上的所有边的颜色设为黑色。
 
Notice:这棵树的根节点为1


输入格式


第一行两个数n,m分别表示点数和操作数。
接下来n-?    1行,每行2个数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%    的数据:n,m<=10^6


题目来源

没有写明来源