시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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, nm ≤ 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 aibi (1 ≤ ai, bin, aibi), która oznacza, że wierzchołek numer ai jest połączony odcinkiem z wierzchołkiem bi. Każda nieuporządkowana para {ai, bi} 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.

예제 입력 1

6 8
1 4
1 6
4 6
3 6
2 5
2 6
3 4
3 5

예제 출력 1

1 4 3 5 2 6