Spies

Time limit3sMemory limit512 MB

Summary

Given a functional graph where spy k shadows a_k, choose the largest subset S such that every member of S is shadowed by at least one spy outside S.

Level: Medium7 of 10
Topics: Graph, Greedy, Dynamic programming
Solved: No attempts yet

Problem

An intelligence agency employs $n$ spies. Each spy shadows exactly one other spy. This shadowing assignment is fixed: spy $k$ shadows spy $a_k$ (with $a_k \ne k$ ).

The agency wants to assign as many spies as possible to a secret operation. However, every spy taking part in the operation must be shadowed by at least one spy that does not take part in it. (The shadowing assignment never changes.)

Write a program that:

reads from standard input which spy each spy shadows,
computes the maximum number of spies that can be assigned to the operation so that each of them is shadowed by at least one spy not taking part in the operation,
writes the result to standard output.

Input

The first line contains the number of spies $n$ ( $2 \le n \le 10^6$ ). The spies are numbered from $1$ to $n$ . Each of the next $n$ lines describes whom a spy shadows: the $(k+1)$ -th line contains a single integer $a_k$ , meaning that spy $k$ shadows spy $a_k$ ( $1 \le k \le n$ , $1 \le a_k \le n$ , $a_k \ne k$ ).

Output

Print a single integer: the maximum number of spies that can be assigned to the secret operation.

Hint

Examples2

Example 1
Input
```
6
2
3
1
3
6
5
```
Expected output
```
3
```
Example 2
Input
```
2
2
1
```
Expected output
```
1
```