Задача №115252. Королевская задача
Совсем недавно в Берляндии была построена новая дорожная сеть. Между некоторыми парами городов есть односторонние дороги, \(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\).
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(\sum n\) | \(\sum m\) | \(w_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия |
| 1 | 16 | – | – | – | – | \(n = m\); \(u_i = i, v_i = i + 1\) для \(i \lt n\); \(u_{n} = n, v_{n} = 1\) |
| 2 | 17 | – | – | \(w_i \le 1\) | – | \(u_i \lt v_i\) |
| 3 | 15 | – | – | – | 2 | \(u_i \lt v_i\) |
| 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 | Offline-проверка. |
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