АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1085. Проверка дорог

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

В некоторой местности имеется 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

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XV Межвузовская олимпиада 2012 /
1084. E - Восстановление текста 1085. 1086. G - Наряды 1087. H - Поиск маячка 1088. I - Защищённое сообщение
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.