Gońcy
Limit pamięci: 32 MB
Król Informaticus, władca Bajtocji, ma zmartwienie. Tajne służby doniosły mu, że zły król Haker postanowił napaść na jego królestwo. Co więcej, Haker wysłał już tajnych agentów do jednego z miast Bajtocji poza stolicą, by utrudniali królowi Informaticusowi przygotowania do obrony. Informaticus postanowił powiadomić mieszkańców kraju o grożącym niebezpieczeństwie.
Obywatele Bajtocji mieszkają tylko w miastach.
Miasta są ponumerowane od do
, gdzie
.
Stolica kraju ma numer
.
W kraju istnieje dobrze rozwinięta sieć dróg.
Wszystkie drogi są dwukierunkowe.
Dowolne dwa miasta mają co najwyżej jedno bezpośrednie połączenie drogowe,
ale dla każdych dwóch różnych miast
,
można przejechać z
do
,
a następnie wrócić z
do
nie przejeżdżając ponownie przez żadne z miast na trasie z
do
.
Król Informaticus postanowił wysłać niezależnie dwóch gońców, by ostrzegli mieszkańców wszystkich miast o grożącym niebezpieczeństwie. Każdy goniec porusza się po drogach Bajtocji i może wielokrotnie odwiedzać to samo miasto. Jednak kolejność, w jakiej goniec odwiedza poszczególne miasta po raz pierwszy, musi być zgodna z planem, który otrzymał od króla.
Plan jest ciągiem różnych liczb całkowitych
z zakresu
, przy czym
.
Po drodze z miasta o numerze
do miasta o numerze
goniec może przejść przez dowolną,
skończoną liczbę miast, ale tylko tych, które już wcześniej odwiedził.
Niestety, na posłańców czyhają ludzie Hakera i biorą w niewolę każdego gońca,
który trafi do opanowanego przez nich miasta.
Trzeba przygotować takie plany tras podróży obu gońców,
aby do każdego miasta Bajtocji dotarł przynajmniej jeden z nich,
zanim obaj zostaną schwytani przez ludzi Hakera, ukrytych w jednym z miast poza stolicą.
Zadanie
Ułóż program, który:
- wczytuje ze standardowego wejścia liczbę
wszystkich miast w Bajtocji, liczbę
wszystkich odcinków dróg łączących bezpośrednio dwa różne miasta, a następnie opisy wszystkich bezpośrednich połączeń drogowych,
- układa plany tras obu gońców zaczynające się w stolicy w taki sposób, aby do każdego miasta w Bajtocji dotarł przynajmniej jeden z nich zanim obaj zostaną schwytani przez ludzi Hakera,
- zapisuje wyznaczone plany na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba naturalna —
jest to liczba wszystkich miast w Bajtocji.
W drugim wierszu jest zapisana jedna liczba naturalna
—
jest to liczba wszystkich bezpośrednich połączeń drogowych.
W każdym z kolejnych
wierszy znajduje się opis jednego bezpośredniego połączenia drogowego.
Opis bezpośredniego połączenia to dwie różne liczby naturalne z zakresu
oddzielone pojedynczym odstępem.
Każde połączenie występuje w pliku tylko raz.
Wyjście
W pierwszym wierszu standardowego wyjścia należy zapisać plan trasy pierwszego gońca w postaci ciągu
różnych liczb naturalnych z zakresu
pooddzielanych pojedynczym odstępem.
W drugim wierszu należy zapisać w takiej samej postaci plan trasy drugiego gońca.
Przykład
Dla danych wejściowych:
5 6 1 2 2 3 3 4 4 1 4 5 5 2
poprawną odpowiedzią jest:
1 2 3 5 4 1 4 5 3 2
Autor zadania: Krzysztof Diks.