Hide

Problem J
Rerouting Rapids

The famous East Manitoba river that flows through Edmonton consists of $N$ rapids. The river is a popular rafting destination, with many visitors coming to the river each summer. When a visitor enters a rapid $i$, the current will take them to some unique other rapid $p_ i$, except when $i$ is the end of the river. Because water can only flow downhill, visitors can never flow back into the rapid at which they started. It is often the case that multiple rapids $j, j’$ flow into the same rapid $p_ j = p_{j'}$.

Unfortunately, there have been many collisions lately in rapids that have many other rapids feeding into them, as many visitors may enter the same rapid at similar times, each being fed into it by a different rapid. You work for the City of Edmonton and have been tasked with rerouting some rapids to decrease the rate of collisions. If it’s possible for a visitor to start at some rapid $i$ and eventually reach another rapid $j$, you may shortcut rapid $i$ to lead directly into rapid $j$, setting $p_ i = j$.

You wish to reroute rapids in this manner to minimize the maximum number of rapids feeding into any given rapid. Report this minimum number.

\includegraphics[scale=0.5]{rapids.pdf}
Figure 1: Illustration of the second sample case. By rerouting rapid $3$ to lead directly to rapid $1$, all rapids now have at most two rapids feeding into them.

Input

The first line of input contains one integer $N$, the number of rapids in the river ($1 \leq N \leq 10^5$). The second line contains $N$ integers $p_1, p_2, \ldots , p_ n$ ($0 \leq p_ i \leq N$). If $1 \leq p_ i \leq N$, then $p_ i$ is the rapid that the $i$th rapid feeds into. Otherwise, if $p_ i = 0$, then the $i$th rapid is at the end of the river. It is guaranteed that $p_ i = 0$ for exactly one of the indices $1 \leq i \leq N$, and there is no way to start at the $i$th rapid and eventually return to it for any $i$.

Output

Output the minimum possible highest number of rapids feeding into any given rapid, subject to rerouting as described above.

Sample Input 1 Sample Output 1
5
2 0 2 2 2
4
Sample Input 2 Sample Output 2
5
0 1 2 2 2
2

Please log in to submit a solution to this problem

Log in