给出 $$$n$$$ 个节点的边加权树,每条边都以某种颜色着色。该树的每个节点都可以被阻塞或解除阻塞,所有节点最初都是解除阻塞的。
简单路径是图中没有重复节点的路径。路径的长度定义为路径上所有边的权重之和。
当一条路径是由相同颜色 $$$c$$$ 的边组成的简单路径,所有颜色 $$$c$$$ 的边都在这条路径上,并且路径上的每个节点都畅通无阻时,这条路径就是好的。
需要操作$$$2$$$种查询:
1. 阻塞一个节点,
2. 解锁节点。
每次查询后,打印所有好路径中的最大长度。如果没有好的路径,则打印$$$0$$$。
输入
第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n,q \leq 2\cdot 10^5$$$) — 节点数和查询数。
接下来是 $$$n-1$$$ 行,每行包含四个整数 $$$u$$$、$$$v$$$、$$$w$$$ 和 $$$c$$$ ($$$1 \leq u,v,w,c \leq n$$$; $$$u \not = v$$$),表示连接节点 $$$u$$$ 和节点的加权边$$$v$$$ 重量 $$$w$$$ 和颜色 $$$c$$$。保证这些边形成一棵树。
接下来是 $$$q$$$ 行,每行包含两个整数 $$$p$$$ 和 $$$x$$$($$$p = 0$$$ 或 $$$p = 1$$$, $$$1\leq x\leq n$$$),表示一个查询:
1. 如果$$$p = 0$$$,则阻止节点$$$x$$$。保证此时不被阻塞;
2. 如果$$$p = 1$$$,则解锁节点$$$x$$$。这个时候保证是被堵住的。
输出
对于每个查询,打印好路径的最大长度。如果没有好的路径,则打印$$$0$$$。
示例
输入 #1
5 4 4 1 3 4 5 2 4 4 3 1 3 2 1 2 5 1 0 4 0 3 0 2 1 3
输出 #1
5 5 0 3
输入 #2
5 5 4 1 4 4 4 5 2 2 3 1 2 4 3 2 3 1 0 3 0 4 1 3 1 4 0 1
输出 #2
2 0 3 6 3
输入 #3
6 9 3 2 2 3 2 4 4 2 3 1 5 5 6 4 3 2 5 3 1 3 0 2 0 4 0 5 0 6 1 2 1 4 1 5 0 3 1 6
输出 #3
5 5 5 5 5 5 5 0 7
输入#4
1 2 0 1 1 1
输出#4
0 0