Problem N
Rivalries
At the prestigious Colorado School of Mines, interdepartmental rivalries are both intense and theatrical. Each department considers exactly one other department as their rival. However, rivalries are not always reciprocated—a department may view another as their rival without that feeling being mutual.
The administration, seeking to foster cooperation despite these rivalries, has decided to form rivalry pairs for an upcoming school-wide fundraising event. Each rivalry pair consists of two departments where either:
-
One department considers the other as a rival, or
-
They consider each other as rivals.
The administration wants to maximize the number of rivalry pairs to have as many departments as they can at the fundraising event, but due to the asymmetric nature of rivalries, it may not be possible to pair up every department. Some departments will be left without a pair.
Given the rivalry preferences of all departments, and that the administration will maximize the number of departments at the event, determine the minimum number of departments that cannot be paired.
Input
The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of departments.
The second line contains $n$ space-separated integers $r_1, r_2, \dots , r_n$ ($1 \leq r_i \leq n$), where $r_i$ represents the department that department $i$ considers as its rival. A department may consider itself a rival, i.e., $r_i = i$.
Output
Print a single integer—the minimum number of departments that cannot be paired.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 3 1 5 4 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 1 4 3 |
0 |
