Задача №1273. Автобусные маршруты
Для решения транспортной проблемы в некотором городе до недавнего времени использовались 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