EXPLOSN - The Explosion

The day of 6.XII.2003 in Megabyteland began calm and quietly as any other day. Some people went to work, some - to school, some - to store to buy food. Drivers were traditionally stucked in traffic jams, drinking coffee and reading morning newspaper. Suddenly the regularity of this day was disturbed by huge explosion."They blew up the embassy of Bajtocja!!!" - somebody cried. Everybody began to run away in panic.

Police works pretty good in Megabyteland and first radiocars appeared near the embassy only few seconds after the explosion. All the people near the embassy were detained. Some of these people are the organizers of the explosion, but the others could by just occasional witnesses. During the testification each person named exactly one perpetrator. It is known, that if a man is not a perpetrator, than he always says the truth (he haven't a reason to lie, have he?). However, perpetrators want to make the work of the police more difficult, so a perpetrator can name any person during the testification (even himself).

The policemen are in the very hard situation. They should arrest some group of potential perpetrators, but it is difficult to determine who is guilty and who is not from the data they have. There exists many groups of potential perpetrators, that don't contradict to any of the testimonies. The policemen want to arrest as small innocent people as possible. So they would like to choose the group with minimal number of people.

Write a program that, given the number of detained people and their testimonies, will determine the number of people in the smallest group of potential perpetrators, that don't contradict to the testimonies.


The first line of the input contains a single integer T, the number of testcases (1<=T<=10).

First line of each testcase contains integer number N (2 <= N <= 100000), equal to the number of detained people (the people are numbered from 1 to N). The i-th of the following N lines contain one integer number Pi (1 <= Pi <= N). Here Pi is the man whom i-th man testified to be guilty.


The output should consist of T lines, containing one integer number for each testcase - the number of people in the smallest group of potential perpetrators, that don't contradict to the testimonies.




hide comments
shubhamnitt: 2020-10-01 21:08:03

explain the ques please!!

arpit_01: 2018-01-30 19:31:43

problem statement is poorly stated!!

narek: 2017-08-06 01:48:05

can somebody explain the example

rogerioagjr: 2015-02-19 12:23:51

a person who is not in the group of potencial perpetrators acusing another one that isn't either

Last edit: 2015-11-18 20:22:41
yaswanth: 2014-08-23 13:59:07

What do you mean by a contradiction?

Added by:Bin Jin
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:First Minsk Training Camp for NEERC teams, day 2 – MWPZ' 2003