题目描述

给定一棵有 $n$ 个点的无根树，需要依次执行 $m$ 次操作。

第 $i$ 次操作有以下三种类型之一：

• 1 x y w：加入一条从 $x$ 到 $y$ 的简单路径，该路径的权值为 $w$；
• 2 t：删除第 $t$ 次操作加入的路径。保证 $t<i$，第 $t$ 次操作一定是加入路径操作，并且该路径尚未被删除；
• 3 x：询问当前所有经过点 $x$ 的路径中，最大的路径权值。如果当前没有路径经过 $x$，输出 $0$。

树上两个点之间的路径是唯一的，路径经过其两个端点。

输入格式

第一行输入两个正整数 $n,m$。

接下来 $n-1$ 行，每行输入两个正整数 $x,y$，表示树中有一条连接点 $x$ 与点 $y$ 的无向边。

接下来 $m$ 行，第 $i$ 行描述第 $i$ 次操作，格式如下：

• 1 x y w；
• 2 t；
• 3 x。

具体含义见题目描述。

输出格式

对于每一个类型为 3 的操作，输出一行一个非负整数，表示询问答案。

样例

5 7
1 2
2 3
2 4
1 5
3 1
1 4 5 5
3 2
1 1 3 2
3 2
2 2
3 2

0
5
5
2

样例解释

• 第一次询问时，没有路径经过点 $1$，答案为 $0$；
• 第二次询问时，只有路径 $4\leftrightarrow 5$ 经过点 $2$，其权值为 $5$；
• 第三次询问时，新加入的路径 $1\leftrightarrow 3$ 也经过点 $2$，但其权值为 $2<5$，因此答案仍为 $5$；
• 删除路径 $4\leftrightarrow 5$ 后，只剩路径 $1\leftrightarrow 3$ 经过点 $2$，答案为 $2$。

数据范围与约定

对于所有测试数据：

• $1\le n,m\le 3\times 10^5$；
• $1\le w_i\le 10^5$；
• $1\le x_i,y_i\le n$；
• 对删除操作，$t_i<i$，第 $t_i$ 次操作一定是加入路径操作，并且对应路径尚未被删除。

特殊性质 A：所有加入路径操作均满足 $w_i=1$。

请注意常数因子对程序效率造成的影响。