Driver Disagreement#9881
Alice and Bob are travelling around Italy by car, but unfortunately they have taken a wrong turn and are now stuck in the city centre of Pisa. (As you may know, driving in the city centre requires a special permit, so they risk getting a fine.) They have not prepared properly for the trip and have only a paper map — no GPS. The map shows all intersections. At each intersection, you can either turn left or turn right: you cannot go straight on or make a U-turn, because many of the streets are one-way.
Of course, they paid attention when entering Pisa and tried to follow their route on the map. Unfortunately, Alice thinks they are at intersection , while Bob believes they are at intersection . As you can imagine, this is quite a stressful situation. Instead of immediately looking for a way out of Pisa, they want to find out who is right.
The map shows from which intersections the Leaning Tower of Pisa is visible. So they come up with an experiment: they drive on, making some sequence of turns (left or right), and trace this sequence on the map starting from both and . As soon as, according to the map, the tower should be visible on one of the two routes but not on the other, they can look out of the window and see which of them is right. You may assume that exactly one of them is right.
The first line contains three integers and B~(2 \le n \le 10^5, 0 \le A, B < n, A \ne B) — the number of intersections and the intersections at which Alice and Bob, respectively, think they are.
The next lines describe the intersections. The -th of these lines (0 \le i < n) contains three integers l_i, r_i and t_i~(0 \le l_i, r_i < n, t_i \in \{0, 1\}). If you are at intersection , turning left takes you to intersection l_i, and turning right takes you to intersection r_i. The value t_i = 1 means that the Leaning Tower of Pisa is visible from intersection ; otherwise, t_i = 0.
Print the minimum number of turns needed to determine who is right. If no experiment can determine whether Alice or Bob is right, print indistinguishable.
Пример 1
Пример 2
Пример 3