8454번 - Rysunek 다국어

Bajtazar narysował na kartce wielokąt wypukły o n wierzchołkach. Wierzchołki ponumerował liczbami od 1 do n, 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.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i m (3 ≤ n ≤ 500 000, n ≤ m ≤ 2n - 3) oznaczające liczbę wierzchołków w wielokącie oraz liczbę par połączonych odcinkami. W każdym z kolejnych m wierszy znajduje się para liczb całkowitych a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), która oznacza, że wierzchołek numer a_i jest połączony odcinkiem z wierzchołkiem b_i. Każda nieuporządkowana para {a_i, b_i} pojawi się na wejściu co najwyżej jednokrotnie.

W jedynym wierszu wyjścia należy wypisać n 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 1, zaś druga jest jak najmniejsza.