ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2004 Тур II

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Одноклассники

Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ
Таня почти уже вышла из дома, чтобы идти в школу, когда раздался звонок. Звонила завуч, сказала, что сегодня первые три урока не состоятся — в школе нет электричества. Таня — староста своего класса, и завуч просила передать всему классу эту новость.
— Что же теперь делать? Времени-то практически не осталось — подумала Таня. — Ну ладно, сейчас я позвоню Лене, потом Кате, потом Маше. А Лена в это время пусть звонит Вите, она знает его телефон, а Витя пусть позвонит Маше. Нет, Маше же я сама позвоню — пусть лучше он звонит Мише. А Катя пусть позвонит Наташе... Нет, так не получится, они же вчера поссорились. Так, некогда размышлять, надо скорее звонить Лене, авось все в конце концов узнают...
С горем пополам Таня все-таки смогла разослать новость по классу, причем получилось так, что до нескольких человек новость дошла слишком поздно, а многим позвонило, сообщая новость, сразу несколько человек. В итоге, класс в целом понес ощутимые моральные (опоздания) и материальные (лишние расходы на телефон) потери. Вечером Таня решила для подобных случаев заранее придумать план звонков, и не пускать больше такие оповещения на самотек, не зря же ее назначили старостой класса... Но задача оказалась непростой.
Помогите Тане составить такой план звонков, с помощью которого удастся разнести новость по классу как можно скорее. При этом все ученики должны получить сообщение, но ни один не должен получить его более одного раза. Передача новости по телефону занимает ровно одну минуту. В начальный момент времени новость знает только староста.
Для решения задачи Таня выписала список всех учеников, а так же для каждого ученика список тех учеников, кому он может позвонить. Можно считать, что если Маша может позвонить Кате, то и Катя может позвонить Маше (даже если в составленном Таней списке указана только одна из этих связей). Можно также предполагать, что по такому "сарафанному радио" сообщение может дойти до любого ученика класса.

Исходные данные

Первая строка содержит количество учеников в классе N (1 ≤ N ≤ 10). Вторая строка содержит целое число M (0 ≤ M ≤ 45). Каждая из следующих M строк содержит пару имен одноклассников, которые могут звонить друг другу, разделенных пробелом. Последняя строка содержит имя старосты. Все имена учеников различны, и состоят не более, чем из 20 заглавных и прописных латинских букв.

Результат

В первой строке — время в минутах, необходимое для передачи новости всему классу согласно предлагаемому плану. Далее выводится описание плана звонков. Звонки идущие параллельно следует объединить в группу. Группы следует упорядочить по времени. Описание каждой группы начинается со строки, содержащей количество звонков. Каждый звонок описывается в отдельной строке. Описание звонка состоит из пары имен (кто звонит, кому звонит), записанной через пробел.

Пример

исходные данныерезультат
6
7
Tanya Lena
Tanya Katya
Tanya Masha
Lena Natasha
Lena Vitya
Natasha Vitya
Masha Vitya
Tanya
3
1
Tanya Lena
2
Tanya Masha
Lena Vitya
2
Vitya Natasha
Tanya Katya
Автор задачи: Идея — Евгений Кобзев, подготовка — Павел Атнашев, Александр Мироненко
Источник задачи: VIII Командный студенческий чемпионат Урала по программированию. Екатеринбург, 11-16 марта 2004 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1323. Одноклассники