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.