[Sdoi2017]树点涂色

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

题目描述

Bob有一棵n个点的有根树,其中1号点是根节点。Bob在每个点上涂了颜色,并且每个点上的颜色不同。定义一条路
径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。Bob可能会进行这几种操作:
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x y:
在以x为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。
Bob一共会进行m次操作


输入格式

第一行两个数n,m。
接下来n-1行,每行两个数a,b,表示a与b之间有一条边。
接下来m行,表示操作,格式见题目描述
1<=n,m<=100000


输出格式

每当出现2,3操作,输出一行。
如果是2操作,输出一个数表示路径的权值
如果是3操作,输出一个数表示权值的最大值


样例输入

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

样例输出

3
4
2
2

提示

没有写明提示


题目来源

鸣谢infinityedge上传

Menuappsclose