ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Collective Guarantee

Time limit: 2.0 second
Memory limit: 64 MB
Somebody of N boys and girls broke mummy's favourite cup. Mummy became angry and numbered the children with positive integers from 1 to N. Then she approached the child number 1 and asked: "Who has broken the cup?" "Me," — he (or she) answered and was punished.
You, of course, understand that the story is idealized. Practically (we don't know if it was true or not) the boy or the girl number 1 said: "It wasn't me! It was the child number K1!" Then mummy approached number 2 and asked him (or her) the same question…
Some children tried to answer the truth. Others replied in order to say something. But some children had agreed not to give away a juvenile to mummy: each one of them pointed someone else from the group — in a circle. As a result — mummy was racked. She was despaired to remember what every child had told her about the cup and she wrote down all thier "evidences" on a sheet of paper. Now she's willing to investigate the cause. First of all she decided to find out if there is a "collective guarantee" between some of the children so that it was described above. You are to write a program that would help mummy in such a case — to all appearences it was not the first and not the lsat cup.


The first lines contains a positive integer T (1 ≤ T ≤ 16) — the number of input tests. Each test consists of two lines: the first one contains a number N (1 ≤ N ≤ 25000) — and amount of children. The second line contains N numbers separated with a space — that are the evidences of the children. Mummy has written down at ith position of the line the number of a child that the ith child pointed to, or 0 if the ith child suddenly confessed.


You should write one line for each test. It should contain "YES", if the evidences of the children at least seem to be noncontradictory: exactly one child has confessed the he (or she) had broken the cup, and there is no group of children that point to each other in a circle. Otherwise you are to output "NO".


2 0 2 2
2 0 2 1
2 3 4 1 3
0 3 2
Problem Author: Leonid Volkov
Problem Source: USU Open Collegiate Programming Contest October'2002 Junior Session
To submit the solution for this problem go to the Problem set: 1211. Collective Guarantee