题目描述

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 操作，输出一个数表示权值的最大值。

样例

input

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

output

3
4
2
2

数据范围与提示

测试点 $1$，$ 1 \leq n, m \leq 1000 $；
测试点 $2$、$3$，没有 2 操作；
测试点 $4$、$5$，没有 3 操作；
测试点 $6$，树的生成方式是，对于 $ i $（$ 2 \leq i \leq n $），在 $ i $ 到 $ i - 1 $ 中随机选一个点作为 $ i $ 的父节点；
测试点 $7$，$ 1 \leq n, m \leq 50000 $；
测试点 $8$，$ 1 \leq n \leq 50000 $；
测试点 $9$、$10$，无特殊限制。

对所有数据，$ 1 \leq n, m \leq 10 ^ 5 $。