Problem D
Secret Santa Cycles
Tina is organizing Secret Santa at work. Secret Santa is a game where everyone is assigned to give a gift to another person, in secret. On the last day before Christmas, everyone opens their present.
The opening ceremony is organized in the following way: Tina picks a random person who gets to open their present. Then the person who gave that present gets to open theirs, and so on, until they get to a person who already opened theirs. At this point, Tina has to pick another random person, and continue the process from there.
Tina doesn’t like picking a random person, so she very much prefers that everyone form one big cycle. You have been given the task to find out if this is the case, so she can mentally prepare for how many random people she has to pick.
To your great horror, you find out that a secret Grinch has messed with the process so that each person $A$ has to give a present to a random person $B$, instead of each person $B$ receiving a present from a random person $A$. Specifically this means that some people might get no gifts, and some people might get multiple gifts.
This mistake obviously needs to be fixed. What is the smallest number of people that have to be assigned a new person to give a gift, so that everyone will get a gift, and Tina only has to pick one random person in the opening ceremony?
Input
The first line of the input consists of a single integer
$N$, the number of people
involved.
The following $N$ lines
each consists of a single integer $G_ i$, the id of the person they
should give a gift to.
Output
Output the number of people who have to be assigned a new person as their secret Santa target.
Limits
-
$1 \leq N \leq 10\, 000$
-
$1 \leq G_ i \leq N$
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 3 4 5 1 2 |
1 |
