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

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

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

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

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

Результат

Вывод содержит количество остановок в новом маршруте 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