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

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Тим-билдинг

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В компании, занимающейся разработкой программного обеспечения, работают n программистов. Каждый из них считает себя либо первым, либо вторым по силе программистом в компании. Во втором случае он может назвать коллегу, который, по его мнению, является более сильным программистом.
Руководство компании решило поделить всех программистов на группы разработки, действуя по следующему алгоритму:
  1. Если есть программисты, ещё не определённые ни в одну из групп разработки, выбираем любого из них и называем его текущим.
  2. Создаётся новая группа разработки, куда направляется текущий программист.
  3. Если текущий программист считает кого-то из коллег более сильным и этот программист ещё не определён ни в одну группу разработки, то он направляется в эту же группу, после чего сам объявляется текущим. Затем шаг 3 повторяется. Иначе формирование группы на этом заканчивается, и руководство возвращается к шагу 1.
Какое минимальное и максимальное количество групп разработки можно сформировать в этой компании, действуя по описанному алгоритму?

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

В первой строке записано целое число n (1 ≤ n ≤ 105). В i-й из следующих n строк указан номер программиста, которого i-й программист считает самым сильным в компании.

Результат

Выведите через пробел минимальное и максимальное количество групп разработки.

Пример

исходные данныерезультат
4
2
3
4
2
1 2
Автор задачи: Артём Рипатти
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1742. Тим-билдинг