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.