作为一名老师,Riko Hakozaki 经常需要帮助她的学生解决各个科目的问题。今天,她被要求完成一项编程任务,内容如下。
给您一个带有 $$$n$$$ 个节点的无向完整图,其中一些边预先分配了正权重,而其余边则没有。您需要为所有未分配的边分配非负权重,以便在生成的完全分配的完整图中,所有权重的异或总和将等于 $$$0$$$。
将完全分配的完整图的丑陋定义为其最小生成树的权重,其中生成树的权重等于其边的权重之和。您需要分配权重,以使结果图表的丑陋程度尽可能小。
提醒一下,具有 $$$n$$$ 节点的无向完全图包含所有边 $$$(u, v)$$$ 且 $$$1 \le u < v \le n$$$;这样的图有 $$$\frac{n(n-1)}{2}$$$ 边。
她不确定如何解决这个问题,所以她请你帮她解决。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2} - 1)$$$) — 节点数和预分配边数。给出输入以便至少有一个未分配的边。
以下 $$$m$$$ 行中的第 $$$i$$$ 包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u \ne v$$$, $$$1 \le w_i < 2^{30}$$$),表示从$$$u_i$$$到$$$v_i$$$的边已预先分配了权重$$$w_i$$$。输入中没有边出现多次。
输出
在一行上打印一个整数——异或和等于 $$$0$$$ 的所有权重分配中最丑陋的。
示例
输入 #1
4 4 2 1 14 1 4 14 3 2 15 4 3 8
输出 #1
15
输入 #2
6 6 3 6 4 2 4 1 4 5 7 3 4 10 3 5 1 5 2 15
输出 #2
0
输入 #3
5 6 2 3 11 5 3 7 1 4 10 2 4 14 4 3 8 2 5 6
输出 #3
6
注意
下图展示了第一个测试用例。黑色权重是从语句中预先分配的,红色权重是我们分配的,最小生成树由蓝色边缘表示。