Cei doi prieteni se vor plimba împreună până când *ciclează*, adică până când vor ajunge în acelaşi nod a doua oară, notat cu $Z$. După ciclare, ei îşi pot continua drumurile separat. Totuşi, dacă vor, pot să meargă amândoi în
continuare pe acelaşi drum: doar dispare obligaţia de a merge împreună.

Fiecare dintre ei trebuie să-şi termine drumul doar după ciclare, adică după ce nu mai sunt obligaţi să meargă împreună. Totuşi, este în regulă dacă drumul unuia se termină exact în nodul în care au ciclat (adică ciclează în $A$ sau $B$).

Fiecare dintre ei trebuie să-şi termine drumul doar după ciclare, adică după ce nu mai sunt obligaţi să meargă împreună.
Totuşi, este în regulă dacă drumul unuia se termină exact în nodul în care au ciclat (adică ciclează în $A$ sau $B$).

Care este numărul minim de minute necesar, astfel încât să fie posibil ca amândoi să ajungă la destinaţiile lor, în timpul alocat, în $A$, respectiv $B$?

Există două tipuri de cerinţe, reprezentate printr-un număr $c$:
* Dacă $c = 1$, trebuie calculată valoarea minimă a lui _max_$(t + t{~A~}, t  + t{~B~})$.

* Dacă $c = 2$, trebuie afişat un triplet de drumuri care poate fi urmat de cei doi veri (drumul comun din $S$ până în $Z$, drum urmat ulterior de primul văr din $Z$ până în $A$, drum urmat ulterior de al doilea văr din $Z$ până în $B$), astfel încât valoarea asociată drumurilor, adică _max_$(t + t{~A~}, t  + t{~B~})$ să fie minimă. Orice triplet corect cu valoarea asociată minimă poate fi afişat.

h2. Date de intrare

Fişierul de intrare $veri.in$ ...

Pe prima linie se găseşte $c$. Pe a doua linie se găsesc doi întregi $n$ şi $m$. Pe a treia linie se găsesc trei întregi $S$, $A$ şi $B$.
 
Pe următoarele $m$ linii se găsesc câte doi întregi $X$ şi $Y$ , reprezentând că există o muchie direcţionată de la nodul $X$ la nodul $Y$, care poate fi parcursă într-un minut (de cost 1).

h2. Date de ieşire

În fişierul de ieşire $veri.out$ ...

Dacă $c = 1$, afişaţi un singur număr, valoarea minimă a lui _max_$(t + t{~A~}, t  + t{~B~})$.
 
Dacă $c = 2$, afişaţi trei drumuri. Primul drum este format de la $S$ până la $Z$. Al doilea drum este format de la $Z$ până la $A$. Al treilea drum este format de la $Z$ până la $B$, unde $S$, $A$, $B$, $Z$ sunt definite anterior.
 
Fiecare drum se va tipări pe două linii separate.
 
* Pe prima linie va apărea lungimea drumului, adică numărul de muchii.
* Pe a doua linie vor apărea nodurile drumului, separate prin câte un spaţiu.
 
Valoarea asociată drumurilor, adică _max_$(t + t{~A~}, t  + t{~B~})$, trebuie să fie minimă.

h2. Restricţii