|
В некоторой местности имеется N перекрёстков, соединённых M двухсторонними дорогами. Начальник дорожно-ремонтной службы собрался проверить качество всех дорог, проехав по ним на автомобиле. Он хочет начать движение с перекрёстка номер 1, проехать по каждой дороге ровно один раз в каждом направлении и в конце вернуться в исходную точку. Требуется предложить маршрут движения.
Исходные данные
В первой строке входного файла через пробел записаны числа N (2 <= N <= 100 000) и M (1 <= M <= 100 000). В следующих M строках записано по 2 целых числа от 1 до N включительно - номера перекрёстков, которые соединяет соответствующая дорога. Любые два перекрёстка соединены не более чем одной дорогой. Перекрёсток не бывает соединён сам с собой.
Результат
Выведите через пробел последовательность проезжаемых перекрёстков. Если ответов может быть несколько, выведите любой. Если ответа не существует, выведите одно число -1.
Пример
| Исходные данные | Результат |
|---|
3 3
1 2
2 3
3 1
|
1 2 3 1 3 2 1
|
4 2
1 2
3 4
|
-1
|
| 
