最近，百里兰（Berland）建成了一个新的道路网络。在某些城市对之间存在单向道路，其中第 $i$ 条道路从城市 $u_i$ 连向城市 $v_i$，其长度为 $w_i$。百里兰的两个主要城市编号为 $a$ 和 $b$。

百里兰的国王非常热爱他的国家。特别地，他喜欢计算其中的各种特征。他将一条路径的美妙度定义为该路径上所有道路长度的按位异或（XOR）和。而他将自己国家的美妙度定义为从城市 $a$ 到城市 $b$ 的所有路径的美妙度的按位异或和。请注意，这样的路径可能有无限多条，并且它们可以多次经过同一个城市。

国王想知道他的国家的美妙度是多少，因此他向你寻求帮助，请你计算这个值，或者说明无法计算该国家的美妙度。

一个数集的美妙度（按位异或和）定义为该集合中所有非零元素的按位异或和。如果集合中包含无限多个非零元素，则认为无法计算其按位异或和。

按位异或（或按位模 2 加法）是一种二元运算，其效果等同于对操作数二进制表示中相同位置的每一对二进制位应用逻辑异或。换句话说，如果操作数的对应位不同，则结果的对应二进制位为 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$。

样例

输入 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

输出 1

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, \dots$ 的路径。因此，从城市 $1$ 到城市 $2$ 存在无限多条具有非零美妙度的路径，这意味着无法计算答案。

在第四组测试数据中，从顶点 $2$ 到顶点 $3$ 存在无限多条美妙度为 $0$ 的路径，且不存在任何一条具有非零美妙度的路径。因此，该国的最终美妙度为 $0$。

子任务

本题的测试点由 6 个子任务组成。每个子任务的分数仅在通过该子任务的所有测试点以及某些先前子任务的所有测试点时才会获得。请注意，某些子任务不需要通过样例测试。Offline 评测意味着该子任务的测试结果仅在比赛结束后公布。