#104817. [BZOJ 4817] [Sdoi2017]树点涂色

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

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

Bob可能会进行这几种操作：

• 1 x 表示把点 到根节点的路径上所有的点染上一种没有用过的新颜色。
• 2 x y 求 到 的路径的权值。
• 3 x 在以 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob 一共会进行 次操作。

第一行两个数 。

接下来 行，每行两个数 ，表示 与 之间有一条边。

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

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

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

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

样例输入

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

共 个测试点。

测试点 ，；

测试点 ，没有 操作；

测试点 ，没有 操作；

测试点 ，树的生成方式是，对于 ，在 中随机选一个点作为 的父节点；

测试点 ，；

测试点 ，；

测试点 ，无特殊限制。

对所有数据，，。