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

NEERC, Центральный подрегион, Рыбинск, октябрь 2001

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

E. Автобусные маршруты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В городе Фишбург есть несколько циклических автобусных маршрутов. Никакие из них не имеют общего участка дороги, хотя возможны пересечения маршрутов и общие остановки. Старожилы Фишбурга утверждают, что возможно проехать с любой остановки на любую другую, возможно, с пересадками. Новый мэр решил реформировать транспортную систему города. Он предложил сделать только один циклический маршрут, но проходящий через все отрезки дорог, по которым автобусы ездили ранее. Направление движения вдоль существовавших отрезков дорог должно остаться старым, также не должно использоваться дополнительных отрезков дорог.
Напишите программу, которая создаёт один из возможных новых маршрутов или находит, что такого маршрута создать нельзя.

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

Первая строка содержит количество старых маршрутов n (1 ≤ n ≤ 100). Каждая из следующих n строк содержит описание одного маршрута: количество остановок m (2 ≤ m ≤ 200) и затем список этих остановок. Идентификаторы остановок — это целые числа в пределах от 1 до 1000. Маршрут представлен последовательностью из m + 1 идентификатора остановок: l1, l2, …, lm, lm+1 = l1, которые последовательно посещаются автобусом, двигающимся вдоль этого маршрута. Маршрут может быть самопересекающимся. Маршрут всегда заканчивается той же остановкой, которой он начинается.

Результат

Вывод содержит количество остановок в новом маршруте k и сам новый маршрут в том же формате, в каком маршруты даны во вводе. Последняя, (k+1)-я остановка должна совпадать с первой. Если новый маршрут невозможно проложить в соответствии с условием задачи, выведите одно число 0.

Пример

исходные данныерезультат
3
6 1 2 5 7 5 2 1
4 1 4 7 4 1
5 2 3 6 5 4 2
15 2 5 4 2 3 6 5 7 4 1 2 1 4 7 5 2

Замечания

Рисунок, соответствующий примеру:
Problem illustration
Источник задачи: Четвертьфинал, центральный регион России, Рыбинск, 17–18 октября 2001
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1137. Автобусные маршруты