[AdditionalFile5371.zip](file://AdditionalFile5371.zip?type=additional_file)

#5371. 「OOI 2023 Day 1」国王的问题

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2023 Day1 T3 「Королевская задача」。

伯利兰迪亚最近新建了一套道路网络。某些城市之间存在单向道路，第 $i$ 条道路从城市 $u_i$ 通往城市 $v_i$，其长度为 $w_i$。伯利兰迪亚的两个主要城市编号为 $a$ 和 $b$。

伯利兰迪亚的国王非常热爱他的国家。他尤其喜欢计算国家中的各种特性。他将路径的美感定义为路径上所有道路长度的按位异或值。而他将国家的美感定义为从城市 $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 40000)$，表示输入数据的组数。

每组输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \le n, m \le 200000)$，分别表示伯利兰迪亚的城市数量和道路数量。

接下来的 $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 200000$ 和 $\sum m \le 200000$。

输出格式

对于每组输入数据，输出一个整数，即伯利兰迪亚的美感。如果答案不存在，则输出 $-1$。

样例

输入

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

输出

0
7
-1
0
-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$，等等。由于存在无限多条具有非零美感的路径，无法计算答案。

在第四组输入数据中，从顶点 $2$ 到顶点 $3$ 有无限多条美感为 $0$ 的路径，且没有任何一条路径具有非零美感。因此，国家的最终美感为 $0$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。