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 |