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

Соревнование школьников. Октябрь 2002

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

C. Круговая порука

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Кто-то из N мальчиков и девочек опять разбил мамину любимую кружку. Мама рассердилась и перенумеровала мальчиков и девочек числами от 1 до N. После этого она подошла к мальчику (или девочке) под номером 1. И грозно спросила: «Кто разбил кружку?». Он (или она) честно ответил: «Я разбил кружку!». И был строго наказан.
Вы, конечно, понимаете, что рассказанная выше история идеализирована. На самом деле (правда это была или неправда — мы не знаем) мальчик (или девочка) под номером 1 ответил: «Да это не я! Это девочка (или мальчик) под номером K1!». Потом мама подошла к номеру 2, и задала тот же вопрос…
Некоторые дети пытались ответить маме честно. Некоторые отвечали просто так, лишь бы что-нибудь сказать. Некоторые же заранее сговорились не выдавать маме преступника: каждый из группы юных заговорщиков называл кого-то другого — по кругу. В итоге, мама совсем замучалась. Отчаявшись запомнить, что же говорил по поводу чашки каждый из отпрысков, она записала все их «показания» на листочек. Теперь она собирается серьезно расследовать дело. В первую очередь она решила установить, не сговорились ли какие-нибудь мальчики и девочки по кругу, так, как это было описано выше. Вы должны написать программу, чтобы помочь ей в такой ситуации — ведь, судя по всему, эта разбитая чашка не первая и не последняя…

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

В первой строке записано число T (1 ≤ T ≤ 16) — количество тестов. Каждый тест состоит из двух строк: в первой строке указано число N — количество детей (1 ≤ N ≤ 25000). Во второй строке через пробел записаны N чисел — показания опрошенных детей. Мама записывала в эту строку на i-е место номер того ребёнка, которого i-й ребёнок назвал виноватым, или число 0, если i-й ребёнок вдруг признался в том, что он разбил кружку.

Результат

Следует вывести по одной строке для каждого теста. В эту строку надо записать «YES» если показания детей, по крайней мере, выглядят непротиворечивыми: ровно один ребёнок признался в том, что он разбил кружку, и нет группы детей, которая указывает друг на друга по кругу. В противном случае необходимо вывести «NO».

Пример

исходные данныерезультат
4
4
2 0 2 2
4
2 0 2 1
5
2 3 4 1 3
3
0 3 2
YES
YES
NO
NO
Автор задачи: Леонид Волков
Источник задачи: USU Open Collegiate Programming Contest October'2002 Junior Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1211. Круговая порука