Desacuerdo de los conductores#9881

Desacuerdo de los conductores

2 segundos

128 megabytes

Difícil

Alicia y Roberto viajan en coche por Italia, pero, lamentablemente, en algún lugar giraron mal y ahora están atrapados en el centro histórico de Pisa. (Como quizás sepan, para entrar en el centro de la ciudad se necesita un permiso especial, por lo que corren el riesgo de recibir una multa.) Se prepararon mal para el viaje, y solo tienen un mapa de papel — nada de GPS. En el mapa están marcadas todas las intersecciones. En cada intersección se puede girar a la izquierda o a la derecha: no se puede seguir recto ni dar la vuelta, ya que muchas calles son de sentido único.

Por supuesto, al entrar en Pisa, estuvieron atentos e intentaron seguir la ruta en el mapa. Lamentablemente, Alicia cree que están en la intersección $A$ , mientras que Roberto está seguro de que están en la intersección $B$ . Como pueden imaginar, la situación es bastante tensa. En lugar de buscar de inmediato un camino para salir de Pisa, quieren averiguar quién de los dos tiene razón.

En el mapa está marcado desde qué intersecciones se puede ver la Torre de Pisa. Por eso se les ocurre un experimento: seguirán conduciendo, realizando una cierta secuencia de giros (a la izquierda o a la derecha), y seguirán esta secuencia en el mapa, comenzando simultáneamente desde $A$ y desde $B$ . En cuanto resulte, según el mapa, que en una de las dos rutas la torre debería ser visible y en la otra no, podrán mirar por la ventana y averiguar quién de los dos tiene razón. Se puede asumir que exactamente uno de los dos tiene razón.

Entrada

En la primera línea se dan tres números enteros $n, A$ y $B (2 \leq n \leq 1 0^{5}, 0 \leq A, B < n, A \neq = B)$ B~(2 \le n \le 10^5, 0 \le A, B < n, A \ne B) — la cantidad de intersecciones, así como las intersecciones en las que, según la opinión de Alicia y Roberto respectivamente, se encuentran.

Las siguientes $n$ líneas describen las intersecciones. En la $i$ -ésima de estas líneas $(0 \leq i < n)$ (0 \le i < n) se dan tres números enteros $l_{i}, r_{i}$ l_i, r_i y $t_{i} (0 \leq l_{i}, r_{i} < n, t_{i} \in {0, 1})$ t_i~(0 \le l_i, r_i < n, t_i \in \{0, 1\}). Si se encuentran en la intersección $i$ , al girar a la izquierda llegarán a la intersección $l_{i}$ l_i, y al girar a la derecha — a la intersección $r_{i}$ r_i. El valor $t_{i} = 1$ t_i = 1 significa que desde la intersección $i$ se puede ver la Torre de Pisa; en caso contrario, $t_{i} = 0$ t_i = 0.

Salida

Imprima la cantidad mínima de giros necesarios para determinar quién tiene razón. Si ningún experimento permite determinar si Alicia o Roberto tiene razón, imprima indistinguishable.

Ejemplos

Ejemplo 1

Ejemplo 2

Ejemplo 3