問題文

N 頂点の根付き木があります。根は頂点 1 です。頂点 i (2 \leq i \leq N) の親は頂点 P_i です。

各 i (1 \leq i \leq N) について、頂点 i を根とする部分木の頂点数を求めて下さい。すなわち、頂点 j から頂点 1 へ到達するために必ず頂点 i を経由する必要のあるような j の個数を求めて下さい。

制約

入力は以下の条件を満たす。

• 2 \leq N \leq 5 \times 10^5
• 入力されるグラフは木をなす。

入力例 1

4
1
2
2

出力例 1

4
3
1
1

入力例 2

10
1
2
3
2
1
5
6
3
4

出力例 2

10
7
4
2
2
2
1
1
1
1