33649번 - 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.

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.

입력

The first line of input contains one integer $N,ドル the number of rapids in the river (1ドル≤N≤10^5$). The second line contains $N$ integers $p_1,p_2,\dots ,p_n$ (0ドル≤p_i≤N$). If 1ドル≤p_i≤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ドル≤i≤N,ドル and there is no way to start at the $i$th rapid and eventually return to it for any $i$.

출력

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

제한

힌트