10601: Автобусні маршрути
Для вирішення транспортної проблеми в деякому місті донедавна використовувалися \(N\) (\(N≤100000\)) автобусних маршрутів. Кожен маршрут починався на одній із \(M\) \((M≤100000)\) площ і там же закінчувався. У процесі проїзду маршрутом автобус міг кілька разів проїжджати одну й ту саму площу, і навіть міг проїжджати більше одного разу однією і тією ж вулицею в тому самому напрямку. У певний момент місцева влада вирішила скоротити кількість автобусних маршрутів у місті до одного. На їхню думку, мав залишитися лише один маршрут, який проходив би всіма вулицями, якими раніше проходили автобусні маршрути, причому в тому ж напрямку (але не обов'язково в тому ж порядку). Якщо будь-якими вулицями автобуси їздили в обох напрямках, то і новий маршрут повинен проходити цими вулицями в обох напрямках. Тими вулицями та в тих напрямках, якими раніше автобуси не їздили, новий маршрут проходити не повинен. Однак оскільки контролерів звільняти не можна, влада вирішила, що кожною вулицею в кожному напрямку новий маршрут повинен проходити стільки разів, скільки нею проходили всі старі маршрути, разом узяті. Потрібно написати програму, яка для заданих вихідних даних визначає необхідний місцевої влади автобусний маршрут.
Формат вхідних даних
Вхідний потік складається з наступної послідовності рядків. Перший рядок містить число \(N\) – кількість автобусних маршрутів, \(M\) – кількість площ.
Кожний з наступних \(N\) рядків служить для опису відповідного автобусного маршруту і спочатку містить число \(k\) \((k≤100000)\), що визначає кількість елементів маршруту, а потім \(k+1\) чисел, що задають номери площ, які послідовно проїжджає автобус на цьому маршруті. Загальна довжина маршрутів трохи більше 100000 вулиць. При описі маршруту завжди задаються номери першої та останньої площі маршруту, причому вони завжди збігаються.
Формат вихідних даних
Вихідний потік повинен містити опис нового маршруту в тому ж форматі, що використовується у вхідному, або одне число 0, якщо організувати необхідний маршрут.
Приклад вхідних даних
2 5
6 1 2 3 4 3 2 1
2 4 5 4Приклад вихідних даних
9 1 2 3 4 5 4 3 2 1
Коментарі
Формат вхідних даних не співпадає з форматом вихідних даних.
Мова йде про зайвий пропуск, що явно не вписаний у форматі вхідних?
Проте формат вхідних та вихідних даних відповідає тестам.