eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Не отрывая карандаша от бумаги

Не отрывая карандаша от бумаги

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Давайте вспомним известную головоломку - нарисовать некоторый рисунок не отрывая карандаша от бумаги, при этом каждую линию можно рисовать только один раз (то есть, нельзя проводить карандашом по уже нарисованной ранее линии).

Самым известным таким рисунком, который мы все пытались нарисовать в детстве, является открытый конвертик.

Итак, чтобы нарисовать такой конвертик не отрывая карандаша от бумаги и рисуя каждую линию только один раз, можно было бы соединить пронумерованные точки, например, в такой последовательности: 1 4 2 5 4 3 2 1 5.

Вот ещё пример рисунка, который можно нарисовать по описанным выше правилам.

Вам будет дано описание рисунка как набора точек и линий, их соединяющих. Ваша программа должна определить, можно ли нарисовать этот рисунок не отрывая карандаша от бумаги и рисуя каждую линию ровно один раз. Обратите внимание, что для того, чтобы нарисовать отдельно стоящую точку, не соединённую линией ни с какой другой точкой, необходимо оторвать карандаш от бумаги.

Входные данные

В первой строке входного текстового файла записаны через пробел два целых числа N и M. N - это количество точек в рисунке (2N200), M - количество линий, их соединяющих (0MN·(N-1)/2). Все точки пронумерованы числами от 1 до N. Каждая линия задается парой чисел - номерами точек, которые соединяет эта линия.

Следующие M строк входного файла содержат описание линий. Каждая строка содержит два натуральных числа А и В, разделённых пробелом (1A, BN, AB). Это номера точек, которые соединяет соответствующая линия. Любые две точки могут быть соединены не более, чем одной линией.

Выходные данные

Если заданный во входном файле рисунок можно нарисовать по описанным в условии правилам, то в выходной текстовый файл необходимо вывести через пробел последовательность номеров точек, которые необходимо соединять линиями, чтобы нарисовать рисунок.

Если рисунок нарисовать нельзя, необходимо вывести единственное число -1 (минус один).

Пример

Входные данные #1
7 10
4 3
2 7
1 2
2 3
3 5
3 1
5 4
2 5
6 5
7 6
Выходные данные #1
1 3 5 6 7 2 5 4 3 2 1 
Источник III этап УОИ Крым, Симферополь, 22 февраля 2012 г. II тур