Trzymilowe Buty

W Bajtocji w ostatnim czasie wybudowano Sieć Chodników. Owa Sieć składa się z jednomilowych Chodników. Każdy z tych Chodników łączy dwa różne Skrzyżowania, albo jedno Skrzyżowanie samo ze sobą. Nie wykluczone, że wybudowano nawet tunele lub estakady. Chodniki są dwukierunkowe i wiadomo, że z kaźdego Skrzyżowania można dojść do wszystkich innych.
Przy każdym ze skrzyżowań znajduje się Bardzo Interesująca Tabliczka (w skrócie: BIT). Dlatego Bajtazar chciałby zobaczyć wszystkie owe Tabliczki. Ale ponadto nie chciałby żadnej z nich widzieć dwa razy, oraz po przejściu trasy chce się znaleźć z powrotem w punkcie wyjścia. W tym celu załatwił sobie Trzymilowe Buty. Mają one taką własność, że Bajtazar może za ich pomocą przeskakiwać skrzyżowania, ale w żadnym kroku nie może przeskoczyć więcej niż dwóch skrzyżowań. Jedyne, co pozostało do zrobienia, to opracowanie trasy dla Bajtazara. To Twoja robota najwyraźniej.

Zadanie:

Napisz program który:

  • Wczyta ze standardowego wejścia opis Chodników w Bajtocji
  • Wyznaczy dowolną trasę spełniającą wymagania Bajtazara
  • Wypisze wynik na standardowe wyjście.

Wejście:

W pierwszej linii standardowego wejścia zapisane są liczby n oraz m ($1 \leq n, m \leq 1000000$) oznaczające odpowiednio ilość Skrzyżowań oraz Chodników. W kolejnych m liniach znajdują się opisy Chodników, po jednym w każdej linijce. Opis składa się z dwóch liczb a, b ($1 \leq a, b \leq n$) oznaczających numery Skrzyżowań, które łączy dany Chodnik. Bajtazar na początku stoi na Skrzyżowaniu numer 1 (i ma wrócić do tego skrzyżowania na końcu wędrówki). Można udowodnić, że dla każdych możliwych danych wejściowych istnieje rozwiązanie.

Wyjście:

Na wyjście Twój program powinien zapisać numery kolejnych Skrzyżowań odwiedzanych przez Bajtazara na dowolnej trasie zgodnej z wymaganiami. Skrzyżowanie numer 1 powinno wystąpić dokładnie dwa razy - na początku i na końcu. Każde inne Skrzyżowanie musi wystąpić dokładnie raz.

Przykład

Dla danych wejściowych:
4 5
2 2
2 1
3 4
2 1
1 4
jedną z prawidłowych odpowiedzi jest:
1 2 3 4 1

Źródło: The Trening 2005