517. Код ревью

Не решаласьЛёгкая

В Яндексе был стажер по имени Ян, замечательный друг и хороший человек. Недавно он получил задачку и буквально сегодня закончил её выполнение. Дело оставалось за малым: его код должен пройти ревью. Для этого необходимо, чтобы с ним ознакомились зависимые от предлагаемых Яном изменений команды.

Вот только проблема: некоторые команды не хотели тратить время на проверку кода, ссылалась на большую загруженность, и предлагали направить код на проверку другим командам. Ян решил подойти к ревью очень серьезно и начал опрашивать команды для составления списка всех возможных перенаправлений. В результате получился довольно внушительный документ.

Ян начал чувствовать себя как в замкнутом круге. Он бегал от команды к команде, каждая ссылалась на другую. В какой-то момент он начал думать, что они могут ссылаться друг на друга и в таком случае нет никакого шанса на то, что его изменения увидят мир!

Вы решили не оставаться в стороне и помочь Яну (он же замечательный друг и хороший человек). Вы сказали, что сможете проанализировать полученный документ и ответить на вопрос, есть ли в нем циклические зависимости.

Формат ввода

Первая строка содержит целое число NN — количество элементов в списке.

Вторая строка содержит NN целых чисел, разделенных пробелами, принимающие значения в диапазоне от 1-1 до N1N - 1 включительно.

Значение под номером ii говорит о том, на какую команду ссылается команда под номером ii. Нумерация команд начинается с нуля. Значение 1-1 говорит об отсутствии ссылки на какую-либо команду.

  • 1N1071 \leqslant N \leqslant 10^7;
  • 1A[i]N1-1 \leqslant A[i] \leqslant N - 1, где AA — список чисел, описывающих перенаправления команд;
  • A[i]iA[i] \neq i.

Формат вывода

Выведите одно слово в зависимости от того, существуют ли циклические зависимости в требованиях команд.

YES — циклические зависимости существуют.

NO — в противном случае.

Примечание

В первом примере команда Яна не перенаправляля код никакой другой команде.

Во втором примере команды 1 и 3 перенаправляли код друг другу.

В третьем хоть команды и ссылаются друг на друга, но так как команда Яна (нулевая) не ссылается ни на какую другую команду, то перенаправлений не будет.

Ограничения

Ограничение времени

20 с

Ограничение памяти

2 ГБ

Пример 1

Ввод
5
-1 -1 -1 -1 -1
Вывод
NO

Пример 2

Ввод
5
1 3 -1 1 0
Вывод
YES

Пример 3

Ввод
5
-1 2 1 -1 -1
Вывод
NO

Теги

Нужно войти, чтобы отправить решение.Войти