Инспекция короля
Инспекция короля
Король Карл является ответственным и прилежным правителем. Каждый год он путешествует по своей стране, чтобы убедиться, что во всех городах все нормально.
В стране имеется n городов и m дорог. Для контроля путешественника каждая дорога является однонаправленной, то есть дорогу из города a в город b, невозможно пройти из b в a.
Карл хочет пройти по дорогам таким образом, чтобы начав движение в столице, посетить все остальные города в точности один раз, и завершить свой путь в столице.
Будучи министром транспорта, Вы должны найти такой маршрут, или сообщить, что он не существует.
Входные данные
Первая строка содержит два числа n и m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ n + 20) - количество городов и дорог в стране.
Каждая из следующих m строк содержит два целых числа a[i]
и b[i]
(1 ≤ a[i]
, b[i]
≤ n), обозначающих что существует однонаправленный путь из города a[i]
в город b[i]
. Города пронумерованы с 1 до n. Столица имеет номер 1.
Выходные данные
Если существует путь, начинающийся и заканчивающийся в столице и проходящий по остальным городам только один раз, то вывести n + 1 число - список городов на пути. Столицу следует вывести в начале и конце пути.
Если требуемого пути не существует, то вывести "There is no route, Karl!" (без кавычек).
Пример
4 6 1 4 4 1 4 2 2 1 3 4 1 3
1 3 4 2 1
4 3 1 4 1 4 2 2
There is no route, Karl!