Обучение в Ягеллонском университете в Кракове имеет свои плюсы и минусы. Плюсы: Ягеллонский университет. Минусы: Краков... Точнее, постоянная необходимость заниматься реконструкцией трамвайных путей.
Изначально сеть общественного транспорта состоит из некоторого количества трамвайных линий. Потом одну из них приостанавливают, затем другую, потом еще... Как Вы сами знаете, в Кракове существует нерушимое правило: всегда приостанавливать линию до того, как возобновит работу какая-либо из ранее приостановленных линий. Сейчас еще не все линии приостановлены (пока), и вы сидите в трамвае, раздражаясь, что ваше прямое сообщение с университетом только что исчезло. Смотришь в окно и спрашиваешь себя: "Я действительно самый невезучий пассажир в этом городе? Или где-то есть кто-то, кому нужно пересаживаться еще большее число раз, чтобы добраться туда, куда он хочет?"
Точнее, мы говорим, что остановка B достижима из остановки A с c изменениями, если существуют такие линии l[0]
, ..., l[c]
что l[0]
обслуживает остановку A, l[c]
обслуживает остановку B, и для каждого 0 ≤ i < c существует существует некоторая остановка, обслуживаемая l[i]
и l[i+1]
. В каждый момент времени Вы хотите знать наибольшее значение c, при котором существует такая пара остановок (A, B), что в B можно добраться из A с c изменениями, но при этом B недостижима из A с c' изменениями для любого c' < c.
Обратите внимание, что иногда вообще невозможно проехать между парой остановок. Как следует из приведенного выше определения, Вы решаете не учитывать такие пары в своем анализе - если кто-то захочет проехать между этими остановками, он воспользуется Uber.
Первая строка содержит количество тестов z (1 ≤ z ≤ 35). Далее следует описание тестов.
Первая строка каждого теста содержит количество остановок n и количество трамвайных путей k (2 ≤ n, k ≤ 750).
Остановки пронумерованы от 1 до n, а линии пронумерованы от 1 до k.
Затем следуют k строк. i-я из этих строк описывает маршрут трамвайной линии номер i. Каждая строка начинается с целого числа r[i]
(2 ≤ r[i]
≤ n), за которым следуют r[i]
различных целых чисел a[i,j]
(1 ≤ a[i,j]
≤ n) - идентификаторы остановок, обслуживаемых i-ым трамвайным маршрутом. Любая трамвайная линия идет в обоих направлениях.
Следующая строка содержит одно целое число s (1 ≤ s ≤ k − 1).
Затем следуют s строк, описывающих порядок остановки трамвайных путей. Каждая из этих строк содержит единственное целое число s[i]
(1 ≤ s[i]
≤ k) - идентификатор остановленной линии трамвая. Любая линия может быть приостановлена не более одного раза.
Суммы значений n и k во всех тестах не превышают 1000 каждое.
Для каждого теста выведите s + 1 строк, каждая из которых содержит одно целое число. В i + 1-ой строке выведите наибольшее количество пересадок между линиями, которые следует совершить после i-го события приостановки (первая строка содержит ответ до любых приостановок).
Первоначально для проезда, например, от остановки 4 до остановки 5 (или наоборот) требуется одна пересадка. Такой проезд возможен по маршруту 2, затем по маршруту 1. Нет пар остановок, требующих 2 или более пересадки.
После удаления линии 1 для проезда от остановки 1 до остановки 3 (или наоборот) требуется две пересадки.
После удаления линий 1 и 4 единственными парами остановок, которые все еще могут быть достигнуты друг от друга, являются (1, 4) и (2, 3), и в обоих случаях для проезда между ними не требуется никаких пересадок.
После удаления линий 1, 4 и 3 единственная пара остановок, достижимая друг от друга, - это (1, 4). Для проезда между этими остановками не требуется никаких пересадок.