АВТ
Язык:

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

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

693. Кольцевой маршрут

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

В одной стране N городов, связанных между собой сетью дорог. Сеть такая, что из каждого города можно добраться до любого другого, передвигаясь по дорогам. Президент страны решил пойти по стопам Франклина Делано Рузвельта и занять безработных строительством дорог, однако стройматериалов для новых дорог в достаточном количестве не оказалось, и решили разобрать часть старых дорог, чтобы улучшить оставшиеся дороги.

Президент хочет убрать несколько дорог, образующих кольцевой маршрут (цикл) так, чтобы по оставшимся дорогам можно было всё равно добраться из каждого города в каждый. Найдите такой кольцевой маршрут, или скажите, что его не существует.

В первой строке входного файла содержатся два целых числа N и M, количество городов и дорог соответственно (1 <= N <= 100 000, 2N <= M <= 3N). В следующих M строках заданы дороги. Каждая дорога задана номерами городов, которые она соединяет. Города занумерованы числами от 1 до N. Между двумя городами может быть несколько дорог, также дорога может соединять город с самим собой.

Выведите в выходной файл число –1, если требуемого маршрута не существует. Если же он существует, выведите номера городов, образующих маршрут.

Пример

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

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

4 8

1 2

1 3

1 4

1 2

1 3

1 4

2 3

4 3

3 1 2 3

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Графы /
205. Игра в города 693. 890. Лабиринт. 208. Михаил Густокашин против бюрократии 267. Муха - слон
Учебные курсы / Структуры и алгоритмы / Алгоритмы на графах /
205. Игра в города 693. 267. Муха - слон 207. Открытки и конверты 246. Путь в лабиринте
Задачи с соревнований / Межвузовские олимпиады / XII Межвузовская олимпиада 2009 /
696. Z - ровные делители (с пробного тура) 693.
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А.