[SDOI2017]树点涂色

题目描述

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

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\leq n,m\leq1000$; 测试点 $2,3$,没有 $2$ 操作; 测试点 $4,5$,没有 $3$ 操作; 测试点 $6$,树的生成方式是,对于 $i(2\leq i \leq n)$,在 $1 \sim i-1$ 中随机选一个点作为 $i$ 的父节点; 测试点 $7$,$1\leq n,m\leq 5\times 10^4$; 测试点 $8$,$1\leq n \leq 5 \times 10^4$; 测试点9,10,无特殊限制 对所有数据,$1\leq n \leq 10^5$,$1\leq m \leq 10^5$。