米海生活在一个流星风暴是常见问题的小镇。这很烦人,因为米海有时要买杂货,而被流星击中可不是什么好玩的事情。所以我们请你找到最危险的方式去买菜,这样我们就可以骗他去那里。
该镇有 $$$n$$$ 建筑物,编号从 $$$1$$$ 到 $$$n$$$。有些建筑物之间有道路,并且从任何建筑物到任何其他建筑物都存在 $$$1$$$ 的简单路径。每条道路都有一定的流星危险级别。大楼里都有杂货店,但米海当然只关心开门的。最初,所有杂货店都关门了。
您将获得三种类型的 $$$q$$$ 查询:
1. 给定整数 $$$l$$$ 和 $$$r$$$,编号从 $$$l$$$ 到 $$$r$$$ 的建筑物开设杂货店(对于已经开设杂货店的范围内的建筑物没有任何反应)。
2. 给定整数 $$$l$$$ 和 $$$r$$$,编号从 $$$l$$$ 到 $$$r$$$ 的建筑物关闭杂货店(没有营业杂货店的建筑物没有任何反应)。
3. 给定整数 $$$x$$$,找到从 $$$x$$$ 到任何开放杂货店的简单路径上的最大流星危险级别,或者如果到开放商店的任何简单路径上没有边,则找到 $$$-1$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n, q \le 3\cdot 10^5$$$)。
然后是 $$$n - 1$$$ 行,其中第 $$$i$$$ 包含整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n, \enspace 1 \le w_i \le 10^9$$$) 意味着之间有两条路建筑$$$u_i$$$和$$$v_i$$$,流星危险等级为$$$w_i$$$。
保证给定的边形成一棵树。
接下来是 $$$q$$$ 行,其中第 $$$j$$$ 行以整数 $$$t_j$$$ 开头 ($$$1 \le t_j \le 3$$$),这意味着第 $$$j$$$ 查询属于第 $$$t_j$$$ 类型。
如果 $$$t_j$$$ 是 $$$1$$$ 或 $$$2$$$,则该行的其余部分包含整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$)。
如果 $$$t_j$$$ 为 $$$3$$$,则该行的其余部分包含整数 $$$x_j$$$ ($$$1 \le x_j \le n$$$)。
输出
对于 $$$3$$$rd 类型的每个查询 ($$$t_j = 3$$$),输出从 $$$x_j$$$ 到某个开放商店的简单路径上的某个边缘上的最大流星危险级别,如果没有这样的边缘,则输出 $$$-1$$$。
示例
输入 #1
6 9 1 3 1 2 3 2 4 5 3 4 6 4 3 4 5 3 1 1 1 1 3 1 2 1 1 1 5 6 3 4 2 6 6 3 4 3 1
输出 #1
-1 -1 4 3 5
注意
这是示例输入中给出的城镇的插图。
在第一个查询中,没有开放商店,因此显然从 $$$1$$$ 到任何开放商店的简单路径上没有边,因此答案是 $$$-1$$$。
在第二次和第三次查询之后,开放商店的集合是$$$\{1\}$$$。从 $$$1$$$ 到 $$$1$$$ 的简单路径没有边,因此 $$$3$$$rd 查询的答案是 $$$-1$$$。
第四次查询后,没有营业商店。
在第五次和第六次查询之后,开放商店的集合为$$$\{5, 6\}$$$。在第六个查询中,从 $$$x_j = 4$$$ 到某个营业的杂货店有两条路径:$$$4$$$ 到 $$$5$$$ 和 $$$4$$$ 到 $$$6$$$。最大的流星危险出现在 $$$4$$$ 到 $$$6$$$ 的边缘,因此第 $$$6$$$ 查询的答案是 $$$4$$$。这条路径在图中用红色标记。
在其余查询之后,开放商店的集合是$$$\{5\}$$$。在第八个查询中,从 $$$x_j = 4$$$ 到开放商店的唯一路径是从 $$$4$$$ 到 $$$5$$$,并且该路径上的最大权重是 $$$3$$$。这条路径在图中用绿色标记。
在第九个查询中,从$$$x_j = 1$$$到开放商店的唯一路径是从$$$1$$$到$$$5$$$,并且该路径上的最大权重是$$$5$$$。这条路径在图中用蓝色标记。