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.