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 |
Tesztadatok
