Problem description


Ścieżka Eulera
(euler)
Memory limit: 64 MB
Time limit: 1.00 s

Treść zadania nie będzie skomplikowana. Napisz program, który wczyta ze standardowego wejścia opis nieskierowanego grafu prostego i jeżeli istnieje w nim ścieżka Eulera, to wypisze taką ścieżkę.

Gwoli przypomnienia, ścieżka Eulera to taka ścieżka, która rozpoczyna się w wierzchołku tego grafu i przechodzi przez wszystkie jego krawędzie dokładnie jednokrotnie.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne N oraz M, oznaczające odpowiednio liczbę wierzchołków i krawędzi w grafie.

W kolejnych M wierszach znajdują się opisy krawędzi. W (i + 1)-szym wierszu standardowego wejścia znajdują się dwie liczby naturalne oddzielone pojedynczym odstępem – wierzchołki połączone i-tą krawędzią.

Możesz przyjąć, że graf podany na standardowym wejściu jest grafem prostym.

Wyjście

Jeżeli w grafie nie istnieje żadna ścieżka Eulera, to wypisz w pierwszym wierszu standardowego wyjścia jedną liczbę -1.

W przeciwnym wypadku w pierwszym (jedynym) wierszu standardowego wyjścia wypisz (M+1) liczb naturalnych ai oznaczających tę ścieżkę, gdzie a1 oznacza wierzchołek w którym zaczyna się ścieżka, am + 1 koniec tej ścieżki, a każde dwie sąsiednie liczby aiai + 1 oznaczają, że i-ta krawędź na ścieżce prowadzi z wierzchołka ai do wierzchołka ai + 1.

Jeżeli istnieje wiele poprawnych odpowiedzi, wypisz dowolną z nich.

Ograniczenia

2 ≤ N ≤ 100 000, 1 ≤ M ≤ 200 000.

Przykład

Input Output
2 1
1 2
1 2 
Input Output
5 5
5 1
4 5
1 4
1 2
1 3
2 1 4 5 1 3