Danil Fadeev
Ученик
(178),
на голосовании
2 месяца назад
Система исполнения «T-Saurus» разработана для параллельного выполнения процессов. Инженеры самой высокой квалификации разработали её таким образом, что одновременно может исполняться бесконечное количество процессов, т. е. вместимость исполнителя не ограничена. Причем, после запуска процесса он успешно завершается ровно через одну секунду.
Несмотря на невероятную эффективность параллелизации, некоторые процессы не могут быть начаты, пока другие не завершат своё исполнение (так часто бывает в реальных системах, когда один процесс использует результаты работы другого и соответственно не может быть запущен с ним параллельно). При этом один процесс может ожидать завершения нескольких процессов.
Все процессы в системе пронумерованы от 1 1 до ? n. Для каждого процесса известно, результаты работы каких процессов ему потребуются для исполнения. Ваша задача состоит в том, чтобы определить, за какое минимальное количество секунд могут быть исполнены все процессы.
Гарантируется, что отсутствуют циклические зависимости, и процессы завершатся за конечное время. Также гарантируется, что процесс с номером 1 1 всегда будет завершаться последним.
Формат входных данных
В первой строке дано число ? n ( 1 ≤ ? ≤ 1 0 5 ) (1≤n≤10 5 ) — количество процессов. Далее дано ? n строк. В ? i-й строке первым числом идёт ? ? a i — количество необходимых ? i-му процессу процессов для старта. Далее идет ? ? a i чисел через пробел — их номера.
Формат выходных данных
В единственной строке выведите количество секунд — минимальное время, за которое все процессы смогут завершиться.
Несмотря на невероятную эффективность параллелизации, некоторые процессы не могут быть начаты, пока другие не завершат своё исполнение (так часто бывает в реальных системах, когда один процесс использует результаты работы другого и соответственно не может быть запущен с ним параллельно). При этом один процесс может ожидать завершения нескольких процессов.
Все процессы в системе пронумерованы от
1
1 до
?
n. Для каждого процесса известно, результаты работы каких процессов ему потребуются для исполнения. Ваша задача состоит в том, чтобы определить, за какое минимальное количество секунд могут быть исполнены все процессы.
Гарантируется, что отсутствуют циклические зависимости, и процессы завершатся за конечное время. Также гарантируется, что процесс с номером
1
1 всегда будет завершаться последним.
Формат входных данных
В первой строке дано число
?
n
(
1
≤
?
≤
1
0
5
)
(1≤n≤10
5
) — количество процессов. Далее дано
?
n строк. В
?
i-й строке первым числом идёт
?
?
a
i
— количество необходимых
?
i-му процессу процессов для старта. Далее идет
?
?
a
i
чисел через пробел — их номера.
Формат выходных данных
В единственной строке выведите количество секунд — минимальное время, за которое все процессы смогут завершиться.