测试数据来自 system/2014

描述

Bob有一颗n个点的有根树，其中1号点是根结点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。

定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。

Bob会进行这几种操作：

1 x：把点x到根的路径上所有的点染上一种没有用过的新颜色。

2 x y：求x到y的路径的权值。

3 x：在以x为根的子树中选择一个点，使得这个点到根结点的路径权值最大，求最大权值。

Bob一共会进行m次操作。

格式

输入格式

第一行两个数n和m。

接下来n-1行，每行两个数a，b，表示a与b之间有一条边。

接下来m行，表示操作，格式参见题目描述。

输出格式

每当出现2，3操作，输出一行。

如果是2操作，输出一个数表示路径的权值。

如果是3操作，输出一个数表示权值的最大值。

样例1

样例输入1

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

样例输出1

3
4
2
2

限制

共10个测试点。

测试点1：\(1\le n,m\le 1000\)

测试点2，3：没有2操作

测试点4，5：没有3操作

测试点6：树的生成方式是，对于i（\(2\le i\le n\)），在1到\((i-1)\)中随机选一个点作为\(i\)的父节点。

测试点7：\(1\le n,m\le 50000\)

测试点8：\(1\le n\le 50000\)

测试点9，10：无特殊限制

对所有数据：\(1\le n,m\le 10^5\)

来源

SDOI 2017 Round1 Day1