30634번 - Королевская задача 서브태스크다국어

Совсем недавно в Берляндии была построена новая дорожная сеть. Между некоторыми парами городов есть односторонние дороги, $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 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$.

Во втором наборе входных данных в стране есть всего $6$ возможных путей из города $1$ в город $3$, красоты которых равны $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, \ldots$. Тогда из города $1$ в город $2$ есть бесконечно много путей с ненулевой красотой, а значит ответ посчитать нельзя.

В четвёртом наборе входных данных из вершины $2$ в вершину $3$ есть бесконечно много путей красоты $0$, и нет ни одного пути с ненулевой красотой. Тогда итоговая красота страны равна $0$.