|
Берляндия в опасности
(Время: 1 сек. Память: 16 Мб Сложность: 82%)
Всем известно, что в Берляндии N городов, некоторые пары из которых соединены двусторонними дорогами. Между парой городов не может быть более одной дороги. Известно, что для любой пары городов A, B существует простой цикл, проходящий через них. Правительству известно, что вражеская империя Бирлэнд атаковала страну. Захвачен один город, отличный от столицы, но какой именно неизвестно.
Президент Берляндии решил известить жителей о предстоящей войне. Для этого он собирается отправить двух посланников. В силу специфики мировоззрения берляндцев, они будут ходить по следующему правилу. Каждому из них президент выдаст план посещения P1, P2, ... , PN перестановку целых чисел от 1 до N , P1 = 1 (столица имеет номер 1). Этот план обозначает, что посланник должен посещать города в таком порядке, но, проходя от города Pi к Pi+1, он может посещать другие города, но только те, которые он уже посещал до того.
Если посланник зайдет в захваченный город, то ... он оттуда уже не выйдет. Помогите Президенту составить два таких плана, что, исполняя их, посланники могут избрать такие маршруты, что любой город будет посещен хотя бы одним из них, независимо от положения захваченного города.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число N (3 ≤ N ≤ 500). Во второй – количество дорог M. Далее в M строках описаны дороги парами номеров соединяемых городов. Города пронумерованы от 1 до N.
Выходные данные
В выходной файл OUTPUT.TXT выведите две искомые перестановки, по одной в строке. Если решений несколько, то следует вывести любое.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
6
1 2
2 3
3 4
4 1
4 5
5 2
| 1 2 3 5 4
1 4 5 3 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
