Disaccordo tra autisti#9881

Disaccordo tra autisti

2 secondi
128 megabyte
Difficile

Alice e Bob stanno viaggiando in auto in Italia, ma, sfortunatamente, hanno svoltato nel posto sbagliato e ora sono bloccati nel centro storico di Pisa. (Come forse saprete, per entrare nel centro città serve un permesso speciale, quindi rischiano una multa.) Si erano preparati male per il viaggio, e hanno con sé solo una mappa cartacea — niente GPS. Sulla mappa sono segnati tutti gli incroci. In ogni incrocio si può svoltare o a sinistra o a destra: non si può andare dritto né fare inversione a U, poiché molte strade sono a senso unico.

Ovviamente, entrando a Pisa, erano stati attenti e avevano cercato di seguire il percorso sulla mappa. Sfortunatamente, Alice è convinta che si trovino all'incrocio , mentre Bob è sicuro che si trovino all'incrocio . Come potete immaginare, la situazione è piuttosto tesa. Invece di cercare subito una via d'uscita da Pisa, vogliono scoprire chi dei due ha ragione.

Sulla mappa è indicato da quali incroci si vede la Torre di Pisa. Perciò escogitano un esperimento: continuano a guidare, effettuando una certa sequenza di svolte (a sinistra o a destra), e seguono questa sequenza sulla mappa, partendo contemporaneamente da e da . Non appena risulta dalla mappa che su uno dei due percorsi la torre dovrebbe essere visibile, mentre sull'altro no, potranno guardare fuori dal finestrino e capire chi dei due ha ragione. Si può assumere che esattamente uno dei due abbia ragione.

Input

Nella prima riga sono dati tre numeri interi e B~(2 \le n \le 10^5, 0 \le A, B < n, A \ne B) — il numero di incroci, nonché gli incroci in cui, secondo Alice e Bob rispettivamente, si trovano.

Le successive righe descrivono gli incroci. Nella -esima di queste righe (0 \le i < n) sono dati tre numeri interi l_i, r_i e t_i~(0 \le l_i, r_i < n, t_i \in \{0, 1\}). Se vi trovate all'incrocio , svoltando a sinistra arriverete all'incrocio l_i, mentre svoltando a destra arriverete all'incrocio r_i. Il valore t_i = 1 significa che dall'incrocio si vede la Torre di Pisa; altrimenti t_i = 0.

Output

Stampate il numero minimo di svolte necessarie per determinare chi ha ragione. Se nessun esperimento permette di determinare se ha ragione Alice o Bob, stampate indistinguishable.

Esempi

Esempio 1

Loading
Loading

Esempio 2

Loading
Loading

Esempio 3

Loading
Loading