配点 : $800$ 点

問題文

$N$ 人の人が大会に出場しました。この大会はトーナメント形式であり、$N-1$ 回の試合が行われました。 諸事情により、このトーナメントは全参加者に平等に組まれているとは限りません。 すなわち、各人に対し、優勝するために必要なその人が勝者となるような試合数が等しいとは限りません。 トーナメントの構造は、正式には問題文の末尾で定義されます。

各試合では必ず片方の人が勝者、もう片方の人が敗者となり、最後まで負けなかった $1$ 人が優勝となります。

図: トーナメントの例

人には $1$ から $N$ までの番号がついており、$1$ 番の人が優勝し、優勝者以外の人 $i(2 \leq i \leq N)$ は人 $a_i$ との試合で負けました。

トーナメントの深さとは、すべての人に対する、その人が優勝するために必要な、その人が勝者となるような試合数の最大値です。

トーナメントの深さとしてありうる最小の値を求めてください。

トーナメントの構造の正式な定義は以下の通りです。$i$ 回目の試合では、

• あらかじめ決められた、まだ試合をしていない $2$ 人の人
• あらかじめ決められたまだ試合をしていない人 $1$ 人と、あらかじめ決められた $j(j に対する、$j$ 回目の試合の勝者
• あらかじめ決められた $j,k(j,k に対する、$j$回目の試合の勝者と$k$ 回目の試合の勝者

のうちのいずれかの $2$ 人が試合を行います。このような構造であって、どのように試合結果を決めても、すでに一度試合に負けた人が再び試合をすることのないようなものをトーナメントと呼びます。

制約

• $2 \leq N \leq 10^5$
• $1 \leq a_i \leq N(2 \leq i \leq N)$
• 入力の試合結果と合致するようなトーナメントが存在する

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_2$

:

$a_N$

出力

トーナメントの深さとしてありうる最小の値を出力せよ。

5
1
1
2
4

3

次のような試合結果が条件を満たします。

• $1$ 回目の試合では、人 $4$ と 人 $5$ が対戦し、人 $4$ が勝つ
• $2$ 回目の試合では、人 $2$ と 人 $4$ が対戦し、人 $2$ が勝つ
• $3$ 回目の試合では、人 $1$ と 人 $3$ が対戦し、人 $1$ が勝つ
• $4$ 回目の試合では、人 $1$ と 人 $2$ が対戦し、人 $1$ が勝つ

このトーナメントは、人 $5$ が優勝するためには $3$ 回勝利する必要があるので、深さ $3$ のトーナメントとなります。 逆に、深さ $2$ 以下の条件を満たすトーナメントは存在しないので、$3$ を出力します。

7
1
2
1
3
1
4

3

4
4
4
1

3