Problem D
Driver Disagreement
Alice and Bob are travelling in Italy. They are travelling by car and unfortunately they took a wrong turn. Now they are stuck in the city centre of Pisa. (You may know that you need an allowance to drive in the city centre, so they are at risk of getting a fine.) As they were not fully prepared for this, they have a map, but no GPS. The map lists all intersections. At each intersection you can go either left or right (you cannot go straight or take a U-turn, as many streets are one-way).
Of course, they paid attention when entering Pisa and tried to follow on the map. Unfortunately, Alice thinks they are at intersection $A$, while Bob believes they are now at intersection $B$. You can imagine this is quite a stressful situation. Instead of figuring out how to get out of Pisa, they want to know who is right first. On the map it is indicated from which intersections you can see the leaning tower of Pisa. So they believe they can conduct an experiment: drive a bit and take the same actions on the map starting from $A$ and $B$. They can trace the route they drive on the map for both of their starting points. As soon as the tower of Pisa should be visible for one of them but not for the other, they can look out of the window to see who is right. You may assume exactly one of them is right.
Input
-
The first line of the input has three space-separated integers. The first integer, $2 \leq n \leq 10^5$ is the number of intersections. The next two integers are $0 \leq A, B < n$, the intersections that Alice and Bob respectively think they are currently at. In particular $A \neq B$.
-
Then follow $n$ lines. The $i$’th of these lines ($0\leq i<n$) has three space-separated integers: $l_ i$ $r_ i$ $t_ i$. If you are at intersection $i$ and take a left turn, you arrive at $l_ i$, while a right turn brings you to $r_ i$. The number $t_ i = 1$ if you can see the leaning tower of Pisa from intersection $i$. Otherwise $t_ i = 0$.
Output
Print the minimal number of turns it takes to show either person correct. If no experiment can tell whether Alice or Bob is correct, print “indistinguishable”.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 2 1 2 1 0 2 0 0 1 0 |
indistinguishable |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 0 1 1 1 1 0 0 0 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 1 2 1 2 0 2 0 1 0 1 1 |
1 |
