Találka
Rómeó és Júlia a lehető legrövidebb időn belül találkozni szeretne. Jelenleg egymástól távol, különböző városban vannak. Repülővel akarnak utazni egy olyan városba, ahova a legrövidebb idő alatt mindketten megérkezhetnek. Az útvonal kiválasztásához ismerik az összes igénybe vehető repülőjáratot.
Feladat
Készíts programot, amely a repülőjáratok, valamint Rómeó és Júlia tartózkodási helyének ismeretében megadja a legközelebbi találkozási pontot és azt a két útvonalat, amelyen közlekedniük kell ahhoz, hogy a lehető legkorábban találkozzanak!
Bemenet
A TALALKA.BE szöveges állomány első sorában a városok (1$\le$N$\le$100) és a repülőjáratok (1$\le$M$\le$10000) száma van, egyetlen szóközzel elválasztva. A városokat az 1,$\ldots$,N számokkal azonosítjuk. A második sorban a Rómeó és Júlia tartózkodási helyének sorszáma van (1$\le$A,B$\le$N). A következő M sor mindegyikében egy repülőjárat van (1$\le$K$\ne$V$\le$N), egyetlen szóközzel elválasztva. Ez azt jelenti, hogy a K városból van közvetlen egyirányú járat a V városba. Minden járat naponta csak egyszer közlekedik és reggel indul azonos időben.
Kimenet
A TALALKA.KI állomány három sort tartalmazzon. Az első sorba két számot kell írni, az első a legközelebbi találkozás ideje, a második a legközelebbi találkozási város sorszám legyen! Ha nincs ilyen, akkor az első sorba –1-et kell írni és ilyenkor a következő két sor legyen üres. A második sorba azt az útvonalat kell írni, amelyiken Rómeó eljut a találkozási városba, a harmadikba pedig azt az útvonalat, amelyiken Júlia eljut a találkozási városba. Ha több megoldás is van, egy tetszőlegeset ki lehet írni.
Példa
| TALALKA.BE | TALALKA.KI |
| 10 15 1 8 1 2 2 1 1 4 3 2 4 3 2 5 3 6 3 7 4 7 5 10 6 9 7 6 8 7 8 9 9 10 | 2 7 1 4 7 8 7 |