В городе Фишбург есть несколько циклических автобусных маршрутов. Никакие из них не имеют общего участка дороги, хотя возможны пересечения маршрутов и общие остановки. Старожилы Фишбурга утверждают, что возможно проехать с любой остановки на любую другую, возможно, с пересадками. Новый мэр решил реформировать транспортную систему города. Он предложил сделать только один циклический маршрут, но проходящий через все отрезки дорог, по которым автобусы ездили ранее. Направление движения вдоль существовавших отрезков дорог должно остаться старым, также не должно использоваться дополнительных отрезков дорог.
Напишите программу, которая создаёт один из возможных новых маршрутов или находит, что такого маршрута создать нельзя.
Исходные данные
Первая строка содержит количество старых маршрутов 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
|
Замечания
Рисунок, соответствующий примеру:
Источник задачи: Четвертьфинал, центральный регион России, Рыбинск, 17–18 октября 2001