Депутатський рейтинг
Обмеження: 2 сек., 256 МіБ
Перед майбутніми виборами депутати не можуть спокійно спати. Їм сняться жахіття, де всі хочуть відібрати у них мандати, ніхто не хоче за них голосувати і так далі і тому подібне.
Для того, щоб збільшити шанси потрапляння до парламенту кожен депутат намагається з усіх сил підвищити свій рейтинг. Для цього влаштовують агітаційні турне містами свого виборчого округу.
Відомо, що у одному з округів є n міст та m двосторонніх доріг, що їх сполучають. Один з депутатів планує свою агітаційну подорож, яка має розпочатися у місті s та завершитися у місті t. Тур може бути як завгодно довгим та може проходити містами та/чи дорогами більше одного разу.
Кожна дорога має свій коефіцієнт рейтингозміни x, який досить непередбачливо впливає на рейтинг. Якщо перед проїздом дорогою кандидат мав рейтинг r, то після він буде рівним r XOR x, де XOR — операція побітової виключної диз’юнкції (побітове додавання за модулем два).
На початку агітаційної подорожі наш кандидат має нульовий рейтинг. Він хоче знати який максимальний рейтинг він може отримати після завершення передвиборчої агітації.
Вхідні дані
У першому рядку задано чотири натуральних n, m, s та t — кількість міст, кількість доріг, початкове місто і кінцеве місто відповідно.
У наступних m рядках задано по три натуральних числа ai, bi та xi. i-та дорога сполучає міста ai тa bi, а її коефіцієнт рейтингозміни є рівним xi.
Вихідні дані
У єдиному рядку виведіть одне ціле число — максимальний рейтинг кандидата після завершення подорожі.
Обмеження
1≤n,m≤105,
1≤s,t≤n,
1≤ai,bi≤n,
0≤xi≤109,
ai≠bi, з кожного міста дорогами можна дістатися до будь-якого іншого, між кожною парою міст існує не більше однієї дороги.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 7 7 1 4 1 2 8 2 4 3 3 5 6 5 2 7 5 6 8 6 7 5 6 3 9 | 12 |
Примітки
Шлях, що дає максимальну відповідь: 1, 2, 5, 3, 6, 5, 2, 4.
Відповідь =8 XOR 7 XOR 6 XOR 9 XOR 8 XOR 7 XOR 3=12.