В одной стране 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
|
