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