COCI '14 Contest 1 #4 Mafija

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

Mafia is a social game played frequently by high school competitors in informatics on summer and winter camps and national competitions, usually very late at night, drinking various fruit sodas. This game is not about winning, it's about loss taking part, like in competitions.

To solve this task, you don't need to know the rules of Mafia: all you need to know is that some of the players are "mobsters" and the rest are "civilians". The mobsters know who is who, but the civilians don't. The civilians are trying to figure out who the mobsters are during the game.

In the current round of the game, out of N surviving players so far, each one has accused exactly one other player saying that he is the mobster. The civilians were only guessing and the mobsters have accused civilians, pretending to know nothing.

Not knowing who the mobsters are, but knowing who accused whom, determine the maximum possible number of mobsters among these players!

Input Specification

The first line of input contains the integer N (2 \le N \le 500\,000), the number of players. The players are labeled with integers from 1 to N. The K^{th} line of input, out of the following N lines, contains the label of the player accused by player K. (No player can accuse themselves.)

Output Specification

The first and only line of output must contain the maximum possible number of mobsters.

Sample Input 1

3
2
1
1

Sample Output 1

2

Explanation for Sample 1

The mobsters can be players 2 and 3.

Sample Input 2

3
2
3
1

Sample Output 2

1

Explanation for Sample 2

The mobster can be any player, but there cannot be more of them because that would mean that one of them accused the other.

Sample Input 3

7
3
3
4
5
6
4
4

Sample Output 3

4

Comments

There are no comments at the moment.