P6417 [COCI 2014/2015 #1] MAFIJA

There are $n$ people. Some of them are civilians, and some of them are gangsters. Now the civilians want to find all the gangsters, so each of the $n$ people has accused one person of being a gangster. If a person is a civilian, they will accuse someone randomly. Otherwise, they will accuse a civilian. Find the maximum possible number of gangsters.

The first line contains an integer $n$. The next $n$ lines each contain an integer $k$. Line $i$ means that person $i$ accused person $k$.

Output a single integer: the maximum possible number of gangsters.

#### Sample Explanation #### Explanation for Sample Input/Output 1 The gangsters can be person $2$ and person $3$. #### Explanation for Sample Input/Output 2 The gangsters could be everyone, but then there can only be one gangster among them. If there is one more gangster, a gangster would accuse a gangster, which is not allowed. #### Constraints - For the testdata worth $40$ points, it is guaranteed that $n\le 15$. - For the testdata worth $80$ points, it is guaranteed that $n\le 2\times 10^4$. - For the testdata worth $100\%$ of the testdata, it is guaranteed that $1\le n\le 5\times 10^5$, $1\le k\le n$. #### Note **The total score of this problem is $120$ points.** This problem is translated from [Croatian Open Competition in Informatics 2014/2015](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf) T4 MAFIJA. Translated by ChatGPT 5