P13529 [OOI 2023] 皇家任务

不久前，伯利兰新建成了一套公路网络。某些城市对之间有单向道路，第 $i$ 条道路从城市 $u_i$ 通向城市 $v_i$，其长度为 $w_i$。伯利兰有两个主要城市，编号为 $a$ 和 $b$。 伯利兰的国王非常热爱自己的国家，尤其喜欢计算各种有趣的性质。他把一条路径的「美丽度」定义为该路径上所有道路长度的按位异或（即 XOR）。而他把国家的「美丽度」定义为所有从城市 $a$ 到城市 $b$ 的路径的美丽度的按位异或。注意，这些路径可能有无穷多条，而且可以多次经过同一个城市。 国王想知道他的国家的美丽度是多少，所以他请你帮他计算这个值，或者判断无法计算美丽度。 集合中所有数的按位异或指的是集合中所有非零数的按位异或。如果集合中有无穷多个非零数，则无法计算按位异或。 按位异或是一种二元运算，相当于对两个操作数的每一位分别做逻辑异或。如果对应位不同，则该位结果为 $1$；如果相同，则为 $0$。例如，$x = 109_{10} = 1101101_2$，$y = 41_{10} = 101001_2$，则 $x \oplus y = 1000100_2 = 68_{10}$。 在图中，一条路径指的是一系列顶点，其中任意两个相邻顶点之间都有一条边相连。

每个测试包含若干组数据。第一行一个整数 $t$（$1 \le t \le 40\,000$），表示数据组数。 每组数据的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 200\,000$），分别表示城市数和道路数。 接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \le n$，$0 \le w_i \le 2^{30} - 1$），表示第 $i$ 条道路的起点、终点和长度。 每组数据的最后一行包含两个整数 $a, b$（$1 \le a, b \le n$），表示国王关心的起点和终点。 设 $\sum n$ 表示所有数据组的 $n$ 之和，$\sum m$ 表示所有数据组的 $m$ 之和。保证 $\sum n \le 200\,000$，$\sum m \le 200\,000$。

对于每组数据，输出一个整数，表示伯利兰的美丽度。如果无法计算美丽度，则输出 $-1$。

### 样例解释 - 在第一组数据中，国家只有一条长度为 $0$ 的道路，因此任意路径的美丽度均为 $0$，所有路径的美丽度异或起来也是 $0$。 - 在第二组数据中，从城市 $1$ 到城市 $3$ 的路径共有 $6$ 条，其美丽度分别为 $0 \oplus 5 = 5$、$0 \oplus 2 = 2$、$1 \oplus 5 = 4$、$1 \oplus 2 = 3$、$3 \oplus 5 = 6$、$3 \oplus 2 = 1$。将它们按位异或后，答案为 $5 \oplus 2 \oplus 4 \oplus 3 \oplus 6 \oplus 1 = 7$。 - 在第三组数据中，从城市 $1$ 到城市 $2$ 的路径有美丽度 $1$、$1 \oplus 2 \oplus 1 = 2$、$1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 = 1$、$1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 = 2$，依此类推。可以发现，从 $1$ 到 $2$ 存在无穷多条美丽度不为 $0$ 的路径，因此无法计算答案。 - 在第四组数据中，从城市 $2$ 到城市 $3$ 有无穷多条美丽度为 $0$ 的路径，但没有任何美丽度非零的路径，因此最终国家美丽度为 $0$。 ### 评分说明 本题测试点分为 6 组。只有通过某一组的所有测试点，且通过部分之前组的所有测试点，才能获得该组分数。有些分组不要求通过样例测试点。“离线评测”表示该组的测试结果只会在比赛结束后公布。 | 组别 | 分值 | $\sum n$ | $\sum m$ | $w_i$ | 必须通过的组 | 备注 | |:----:|:----:|:--------:|:--------:|:-----:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | 样例测试点 | | 1 | 16 | -- | -- | -- | -- | $n = m$，$u_i = i, v_i = i+1$ 对 $i < n$，$u_n = n, v_n = 1$ | | 2 | 17 | -- | -- | $w_i \le 1$ | -- | $u_i < v_i$ | | 3 | 15 | -- | -- | -- | 2 | $u_i < v_i$ | | 4 | 19 | $\sum n \le 1000$ | $\sum m \le 1000$ | $w_i \le 2^{10} - 1$ | 0 | | | 5 | 14 | -- | -- | $w_i \le 1$ | 2 | | | 6 | 19 | -- | -- | -- | 0--5 | **离线评测** |