题目描述

不久前，伯利兰新建成了一套公路网络。某些城市对之间有单向道路，第 $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$。

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$，依此类推。可以发现，从 $1$ 到 $2$ 存在无穷多条美丽度不为 $0$ 的路径，因此无法计算答案。
• 在第四组数据中，从城市 $2$ 到城市 $3$ 有无穷多条美丽度为 $0$ 的路径，但没有任何美丽度非零的路径，因此最终国家美丽度为 $0$。

评分说明

本题测试点分为 6 组。只有通过某一组的所有测试点，且通过部分之前组的所有测试点，才能获得该组分数。有些分组不要求通过样例测试点。“离线评测”表示该组的测试结果只会在比赛结束后公布。

组别	分值	$\sum n$	$\sum m$	$w_i$	必须通过的组	备注
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
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	离线评测