Королевская задача

문제

Совсем недавно в Берляндии была построена новая дорожная сеть. Между некоторыми парами городов есть односторонние дороги, $ii$-я из которых ведёт из города $u_{i}u\_i$ в город $v_{i}v\_i$, а её длина равна $w_{i}w\_i$. Два главных города Берляндии имеют номера $aa$ и $bb$.

Король Берляндии очень любит свою страну. В частности, он обожает подсчитывать всякие характеристики в ней. Он называет красотой пути побитовое исключающее ИЛИ длин всех дорог на этом пути. А красотой своей страны он называет побитовое исключающее ИЛИ красот всех путей из города $aa$ в город $bb$. Обратите внимание, что таких путей может быть бесконечно много, и они могут проходить через один и тот же город несколько раз.

Король хочет узнать, чему равна красота его страны, а поэтому он обратился к вам за помощью и просит вас посчитать это значение или сказать, что красоту страны посчитать невозможно.

Побитовым исключающим ИЛИ множества чисел называется побитовое исключающее ИЛИ всех ненулевых чисел в этом множестве. Если в множестве бесконечно много ненулевых чисел, то побитовое исключающее ИЛИ посчитать невозможно. \\

Побитовое исключающее ИЛИ (или побитовое сложение по модулю два) --- это бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичной записи операндов. Иными словами, если соответствующие биты операндов различны, то соответствующий двоичный разряд результата равен 1; если же биты одинаковые, то двоичный разряд результата равен 0. Например, если $x={109}_{10}={1101101}_{2}x\; =\; 109\_\{10\}\; =\; 1101101\_2$, а $y={41}_{10}={101001}_{2}y\; =\; 41\_\{10\}\; =\; 101001\_2$, то их побитовое исключающее ИЛИ равно $x\oplus y={1000100}_2={68}_{10}x\; \backslash oplus\; y\; =\; 1000100\_2\; =\; 68\_\{10\}$.

Путём в графе называется последовательность вершин, в которой любые две последовательные вершины соединены ребром.

입력

Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число $tt$ ($1\le t\le 400001\; \backslash le\; t\; \backslash le\; 40\backslash ,000$) --- количество наборов входных данных.

В первой строке каждого набора входных данных даны два целых числа $nn$ и $mm$ ($1\le n,m\le 2000001\; \backslash le\; n,\; m\; \backslash le\; 200\backslash ,000$) --- количество городов и количество дорог в Берляндии.

В следующих $mm$ строках даны по три целых числа $u_{i}u\_i$, $v_{i}v\_i$ и $w_{i}w\_i$ ($1\le u_i,v_i\le n1\; \backslash le\; u\_i,\; v\_i\; \backslash le\; n$, $0\le w_i\le 2^{30}-10\; \backslash le\; w\_i\; \backslash le\; 2^\{30\}-1$) --- номера начала и конца $ii$-й дороги и её длина.

Последняя строка каждого набора входных данных содержит два целых числа $aa$ и $bb$ ($1\le a,b\le n1\; \backslash le\; a,\; b\; \backslash le\; n$) --- номера начала и конца путей, которые интересуют короля.

Обозначим за $\sum n\backslash sum\; n$ сумму $nn$, а за $\sum m\backslash sum\; m$ сумму $mm$ по всем наборам входных данных в одном тесте. Гарантируется, что $\sum n\le 200000\backslash sum\; n\; \backslash le\; 200\backslash ,000$ и $\sum m\le 200000\backslash sum\; m\; \backslash le\; 200\backslash ,000$.

출력

Для каждого набора входных данных выведите одно целое число --- красоту Берляндии. Если ответа не существует, то выведите $-1-1$.

힌트

В первом наборе входных данных в стране есть только одна дорога длины $00$, поэтому красота любого пути равна $00$, а тогда и побитовое исключающее ИЛИ красот всех путей равно $00$.

Во втором наборе входных данных в стране есть всего $66$ возможных путей из города $11$ в город $33$, красоты которых равны $0\oplus 5=5,0\oplus 2=2,1\oplus 5=4,1\oplus 2=3,3\oplus 5=6,3\oplus 2=10\; \backslash oplus\; 5\; =\; 5,\; 0\; \backslash oplus\; 2\; =\; 2,\; 1\; \backslash oplus\; 5\; =\; 4,\; 1\; \backslash oplus\; 2\; =\; 3,\; 3\; \backslash oplus\; 5\; =\; 6,\; 3\; \backslash oplus\; 2\; =\; 1$. Тогда красота страны равна $5\oplus 2\oplus 4\oplus 3\oplus 6\oplus 1=75\; \backslash oplus\; 2\; \backslash oplus\; 4\; \backslash oplus\; 3\; \backslash oplus\; 6\; \backslash oplus\; 1\; =\; 7$.

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

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