Deputy Rating
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Before the upcoming elections, deputies cannot sleep peacefully. They have nightmares where everyone wants to take away their mandates, no one wants to vote for them, and so on and so forth.
In order to increase their chances of getting into parliament, every deputy tries their best to increase their rating. To do this, they organize agitation tours through the cities of their constituency.
It is known that in one of the constituencies there are \(n\) cities and \(m\) bidirectional roads connecting them. One of the deputies is planning their agitation journey, which should start in city \(s\) and end in city \(t\). The tour can be of any length and can pass through cities and/or roads more than once.
Each road has its own rating change coefficient \(x\), which affects the rating rather unpredictably. If before driving along the road the candidate had a rating \(r\), then after it will be equal to \(r \mbox{ XOR } x\), where \(\mbox{XOR}\) is the bitwise exclusive OR operation (bitwise addition modulo two).
At the beginning of the agitation journey, our candidate has a zero rating. He wants to know what maximum rating he can get after completing the election campaign.
Input
The first line contains four integers \(n\), \(m\), \(s\), and \(t\) — the number of cities, the number of roads, the starting city, and the destination city, respectively.
The following \(m\) lines each contain three integers \(a_i\), \(b_i\), and \(x_i\). The \(i\)-th road connects cities \(a_i\) and \(b_i\), and its rating change coefficient is equal to \(x_i\).
Output
In a single line, print one integer — the maximum rating of the candidate after completing the journey.
Constraints
\(1 \le n, m \le 10^5\),
\(1 \le s, t \le n\),
\(1 \le a_i, b_i \le n\),
\(0 \le x_i \le 10^9\),
\(a_i \ne b_i\), from every city, any other city can be reached via roads, between each pair of cities, there is at most one road.
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
The path that gives the maximum answer: 1, 2, 5, 3, 6, 5, 2, 4.
Answer \(=8 \mbox{ XOR } 7 \mbox{ XOR } 6 \mbox{ XOR } 9 \mbox{ XOR } 8 \mbox{ XOR } 7 \mbox{ XOR } 3 = 12\).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|