0385. Робот в серверной

Вы – системный администратор одной очень перспективной IT-фирмы. В чём именно заключаются перспективы этой фирмы никто не знает, но все уверены, что они есть. Под вашим управлением находится серверная, в которой установлено целых n серверов (или n целых серверов, вы точно не уверены), пронумерованных целыми числами от 1 до n.

Ваша работа – следить за тем, чтобы серверы работали и не выключались. Если какой-нибудь сервер выключится, вы должны моментально его включить (по крайней мере, так считает ваш начальник). Вашу работу усложняет тот факт, что работоспособность некоторых серверов зависит от других серверов (например, для работы Web-сервера должен работать сервер баз данных). Если попытаться включить сервер, когда работают не все сервера, от которых он зависит, то этот сервер просто не включится (и потом придется пытаться включать его заново). Например, если сервер номер 1 зависит от серверов 2, 3 и 5, то для того, чтобы его включить, требуется сначала включить серверы 2, 3 и 5. Как истинный системный администратор, вы ленивы и поэтому решили переложить эту сложную задачу на плечи маленького ни в чём не повинного робота. Бедняга робот не смог вам отказать, поэтому каждый день он выполняет следующий алгоритм. У робота в памяти записана последовательность из n различных чисел от 1 до n – порядок, в котором он обходит серверы. Подходя к очередному серверу, робот проверяет, выключен ли сервер, и если он выключен, то пытается его включить. После того, как робот дошёл до последнего сервера, он заканчивает выполнение алгоритма.

Недавно в серверной отключилось электричество, поэтому сейчас все серверы выключены. Вам интересно – сколько раз роботу придется выполнить свой алгоритм, чтобы все серверы оказались включенными.

Формат входного файла

Первая строка ввода содержит число n – количество серверов в серверной (1 ≤ n ≤ 10⁵). Следующая строка содержит n различных чисел от 1 до n – порядок, в котором робот обходит серверы. В следующих n строках задано описание зависимостей между серверами: i--я строка содержит число k_i – количество серверов, от которых зависит i--й сервер, и последовательность k_i различных чисел – номера этих серверов. Сервер не может зависеть от самого себя. Суммарное количество зависимостей не превышает 1,000,000.

Формат выходного файла

В единственную строку выведите количество итераций алгоритма, через которое робот включит все серверы, или -1, если робот так и не сможет включить все серверы.

Пример:

Подробное описание действий в первом примере:

1. Робот подходит к серверу 3 и включает его, так как этот сервер не зависит от других серверов;
2. Робот подходит к серверу 1 и не включает его, так как ещё не включен сервер 2, от которого зависит сервер 1;
3. Робот подходит к серверу 2 и включает его, так как этот сервер не зависит от других серверов;
4. Заканчивается первая итерация;
5. Робот подходит к серверу 3, сервер уже включен;
6. Робот подходит к серверу 1 и включает его, так как все серверы, от которых он зависит, уже включены;
7. Робот подходит к серверу 2, сервер уже включен;
8. Все серверы включены, прошло две итерации;

   Во втором примере невозможно включить все серверы.

Источник: Чемпионат ПетрГУ по программированию. Октябрь 2014.

Обсудить       Отправить решение



Версия для печати