Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача D. Обновления

Задачу добавил: alef

Успешно сдано решений: 34

Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт

Обновления операционной системы, которую разрабатывает Gadget Operating System, являются бесплатными для пользователей устройств. Обновление — это пакет, который содержит некоторое количество новых функций.

Обладатели блокирующего пакета акций сочли, что распространять обновления бесплатно — неправильно. По их мнению, пользователь должен оплачивать каждую новую функцию в обновлении.

В обновлении содержится n новых функций.

Будем говорить, что функция #j непосредственно зависит от функции #k, если функция #j может быть активирована в системе сразу же после активации функции #k. Функция #k, в свою очередь, может непосредственно зависеть от какой-либо другой функции, например, функции #l. В этом случае про функцию #j можно сказать, что она косвенно зависит от функции #l.

Известно, что каждая функция непосредственно зависит не более чем от одной функции.

Менеджеры Quantum Artificial Intelligence предложили назначить за каждую новую функцию цену, на единицу большую количества функций, которые от нее зависят непосредственно или косвенно.

Ваша задача — определить, сколько, по мнению менеджеров Quantum Artificial Intelligence, должна стоить самая дорогая функция

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество функций в обновлении.

Во второй строке содержится n целых чисел ai (0 ≤ ai ≤ n), где ai — номер функции, от которой непосредственно зависит функция #i. Если ai = 0, то функция #i не зависит от других функций.

Гарантируется, что если функция #i зависит от функции #ai, то функция #ai ни прямо, ни косвенно не зависит от функции #i.

Выходные данные

В первой строке выведите два целых числа — номер наиболее дорогой функции и её цену. Если существует несколько вариантов ответа, выведите любой.

Пример

Входные данные
15
6 0 0 15 13 2 15 14 13 3 12 0 12 2 11
Выходные данные
12 8

Сдать задачу

Задать вопрос жюри по этой задаче