ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1362. Одноклассники 2

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
На чемпионате Урала-2004 была задача "Одноклассники". Вкратце её содержание таково:
Ученице Тане поступило задание от директора школы оповестить свой класс о том, что 3 первых завтрашних занятия отменяются в связи с отключением электричества. Таня очень ловко справилась с этим. Сначала она решила позвонить Лене, затем Кате, а потом Маше. В то время, пока она звонила Кате, Лена, уже узнавшая новость, звонила Мише и т.д. В результате весь класс в миг узнал об отмене занятий.
В задаче требовалось узнать минимальное время, за которое весь класс мог узнать о приятной новости.
Но время шло, и летом Таня пошла работать в рекламное агентство "Карамболь". Рекламное агентство "Карамболь" имеет чётко выраженную иерархическую структуру. В её вершине находится генеральный директор. Он имеет своих подчинённых, которые, в свою очередь, также могут иметь подчинённых и т.д. В один прекрасный день Таня придумала метод, помогающий увеличить отдачу от рекламы на 110%. Она сразу же позвонила своей начальнице, затем своей подруге Лене, находящейся у неё в подчинении, потом Кате и Маше. Те, в свою очередь, быстро перезвонили своим друзьям и т.д. Определите, какое наименьшее время понадобится для того, чтобы всё агентство "Карамболь" узнало о сказочно эффективном методе Тани. Но учтите, что телефоны рекламного агентства настроены так, чтобы каждый сотрудник мог говорить либо со своим непосредственным начальником, либо со своим непосредственным подчинённым (иначе и нельзя — девушки прекрасно заменяют работу продолжительным общением по телефону, если им разрешить чуток больше). Каждый телефонный разговор занимает ровно одну минуту.

Исходные данные

В первой строке находится одно число N (N ≤ 100000) — количество служащих в фирме "Карамболь". Каждый служащий имеет свой уникальный ID — число от 1 до N.
Далее следует N строк. Строка с номером K содержит список подчинённых K-го служащего, завершающийся нулём. В последней строке находится одно число — Танин ID. Напомним, что в агентстве "Карамболь" у каждого сотрудника, кроме генерального директора, есть ровно один непосредственный начальник.

Результат

Выведите одно число — минимальное время в минутах, за которое вся компания "Карамболь" узнает о гениальном методе простой девочки по имени Таня.

Пример

исходные данныерезультат
10
2 3 0
4 5 7 0
6 9 0
0
0
8 10 0
0
0
0
0
2
5

Замечания

Обратите внимание: несмотря на пример в тексте, Таня и другие сотрудники могут звонить своему начальнику и подчинённым в любом порядке.
Автор задачи: Евгений Крохалев
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005 г.