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

Инспекция короля

Инспекция короля

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

Король Карл является ответственным и прилежным правителем. Каждый год он путешествует по своей стране, чтобы убедиться, что во всех городах все нормально.

В стране имеется n городов и m дорог. Для контроля путешественника каждая дорога является однонаправленной, то есть дорогу из города a в город b, невозможно пройти из b в a.

prb7571.gif

Карл хочет пройти по дорогам таким образом, чтобы начав движение в столице, посетить все остальные города в точности один раз, и завершить свой путь в столице.

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

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

Первая строка содержит два числа n и m (2n100 000, 0mn + 20) - количество городов и дорог в стране.

Каждая из следующих m строк содержит два целых числа a[i] и b[i] (1a[i], b[i]n), обозначающих что существует однонаправленный путь из города a[i] в город b[i]. Города пронумерованы с 1 до n. Столица имеет номер 1.

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

Если существует путь, начинающийся и заканчивающийся в столице и проходящий по остальным городам только один раз, то вывести n + 1 число - список городов на пути. Столицу следует вывести в начале и конце пути.

Если требуемого пути не существует, то вывести "There is no route, Karl!" (без кавычек).

Пример

Входные данные #1
4 6
1 4
4 1
4 2
2 1
3 4
1 3
Выходные данные #1
1 3 4 2 1
Входные данные #2
4 3
1 4
1 4
2 2
Выходные данные #2
There is no route, Karl!
Источник 2015 ACM NEERC, Semifinals, December 6, Problem K