$N$ 頂点からなる木が与えられます。頂点 $i$ は、頂点 $A_i$ に接続しています。

$f(x)$ を、「頂点 $x$ から深さ優先探索を始めたときに、最後に訪れることになる頂点」と定義します。

すべての $i\ (1 \leq i \leq N)$ について $f(i)$ を求めてください。

$f(x)$ の厳密な定義

数列 $E \coloneqq (x), S = ()$ とする。以下を繰り返す。

［$E = (y, \dots )$ の場合］

• $E$ から $y$ を取り除く。
• $y$ に接続する頂点のうち、$S$ に含まれない頂点を $C=c_1, c_2, \dots, c_n$ とする。
• $C$ を 昇順に 並び替えて、$E$ の先頭に追加する。
• $S$ の末尾に $y$ を追加する。

［$E = ()$ の場合］

• $f(x) = S_m\ (m=|S|)$ である。繰り返し終了。（制約により $S$ が空でないことは保証される。）

この問題では、すべてのテストケースについて、以下の制約を満たす。

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N\ (2 \leq i \leq N)$
• $A_i \neq i\ (2 \leq i \leq N)$
• 与えられるグラフは木である。

部分点

この問題には、部分点が設定されている。
$N \leq 300$ のテストケースにすべて正解すると、$100$ 点が与えられる。
$N \leq 2000$ のテストケースにすべて正解すると、追加で $100$ 点が与えられる。

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

問題文で指定された方法で計算した $f(x)$ について、

の形で出力せよ。