Két út
Egy vállalatnak N városban van telephelye.
A városokat az 1,...,N számokkal azonosítjuk.
A központi telephely az 1. városban van. Alkatrészeket kell kiszállítani a központi telephelyről két különböző, U és V városba két kamionnal, az egyiknek az U, a másiknak a V városba kell mennie. Ismerjük, hogy mely városok között van közvetlen út. A korlátozások miatt a két kamion olyan útvonalon közlekedhet, amely különböző városokon keresztül halad.
Feladat
Készíts programot, amely kiszámít egy olyan U-ba és egy olyan V-be vezető útvonalat, hogy a két útvonalban csak a kiindulási pont (a központi telephely) közös!
Bemenet
A KETUT.BE szöveges állomány első sorában
a városok N száma (3$\le$N$\le$100) és az U és V város sorszáma (2$\le$U, V$\le$N, U$\ne$V) és a közvetlen utak M (2$\le$M$\le$3000) száma van. A következő M sor mindegyikében két szám van egy szóközzel elválasztva: X Y ami azt jelenti, hogy X városból van Y városba út, amin X-ből Y-ba lehet menni, de fordítva nem. Minden közvetlen útra teljesül, hogy X<Y.
Kimenet
A KETUT.KI szöveges állomány első sorába két egész számot kell írni, az U-ba vezető útvonalon lévő városok r számát, és a V-be vezető útvonalon lévő városok s számát (beleértve a kiindulási központi telephely 1 sorszámát)! A második sor az U-ba vezető, a harmadik pedig a V-be vezető útvonalat tartalmazza. Ha nincs megoldás, akkor a 0 0 számpárt kell kiírni az első sorba. Több megoldás esetén bármelyik megadható.
Példa
|
ketut.be
|
ketut.ki
|
10 9 5 12
1 2
1 3
2 4
3 6
4 5
5 7
6 8
7 9
3 5
4 7
6 9
9 10
|
4 4
1 3 6 9
1 2 4 5
|
Tesztadatok
