Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Берляндия в опасности

(Время: 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.TXTOUTPUT.TXT
15
6
1 2
2 3
3 4
4 1
4 5
5 2
1 2 3 5 4
1 4 5 3 2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2022, ICQ: 151483, E-mail: admin@acmp.ru



Ставки на баскетбол 3x3