Rysunek
Limit pamięci: 128 MB
Bajtazar narysował na kartce wielokąt wypukły o
wierzchołkach.
Wierzchołki ponumerował liczbami od
do
, przy czym numery nadawał w przypadkowej kolejności.
Dodatkowo w wielokącie narysował pewną liczbę przekątnych, które nie przecinają się, choć mogą mieć wspólne końce w wierzchołkach wielokąta.
Rysunek spodobał mu się na tyle, że postanowił zanotować numery wierzchołków połączonych odcinkami.
Po jakimś czasie Bajtazar chciał odtworzyć rysunek na podstawie swoich zapisków, jednak okazało się to trudne.
Poprosił Cię o napisanie programu, który pomoże odzyskać rysunek.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
i
(
) oznaczające liczbę wierzchołków w wielokącie oraz liczbę par połączonych odcinkami.
W każdym z kolejnych
wierszy znajduje się para liczb całkowitych
,
(
), która oznacza, że wierzchołek numer
jest połączony odcinkiem z wierzchołkiem
.
Każda nieuporządkowana para
pojawi się na wejściu co najwyżej jednokrotnie.
Wyjście
W jedynym wierszu wyjścia należy wypisać
numerów kolejnych wierzchołków na obwodzie wielokąta.
Spośród możliwych wyników należy wypisać ten, w którym pierwszą liczbą jest
, zaś druga jest jak najmniejsza.
Przykład
Dla danych wejściowych:
6 8
1 4
1 6
4 6
3 6
2 5
2 6
3 4
3 5
poprawną odpowiedzią jest:
1 4 3 5 2 6
Autor zadania: Jakub Łącki.