Problem Description

The Takahashi Kingdom consists of $ N $ towns, each labeled from $ 0 $ to $ N-1 $. There are $ N-1 $ roads connecting pairs of towns, allowing travel from any town to any other town using some roads.

Takahashi, the king of the Takahashi Kingdom, is trying to decide on a capital city. To help with this decision, he decided to calculate the "balance value" for each town. The "balance value" when town $ v $ is the capital is the maximum size of a set of towns that can travel between each other without passing through town $ v $.

For example, if town $ 1 $ is the capital in the figure below, sets of towns like {town $ 0 $, town $ 4 $} or {town $ 2 $} or {town $ 3 $} can travel between each other without passing through town $ 1 $. The largest set is {town $ 0 $, town $ 4 $}, with a size of $ 2 $, so the "balance value" when town $ 1 $ is the capital is $ 2 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ p_1 $ $ p_2 $ : $ p_{N-1} $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 100,000)$, representing the number of towns.
• The next $ N-1 $ lines contain road information. The $ i $-th line contains an integer $p_i\ (0\ ≦\ p_i\ ≦\ i-1)$, indicating that there is a road connecting town $ i $ and town $ p_i $.

Output Format

Output $ N $ lines. The $ i $-th line should contain a single integer representing the "balance value" when town $ i-1 $ is the capital.

Sample Input and Output

Sample Input #1

5
0
1
1
0

Sample Output #1

3
2
4
4
4

Sample Input #2

3
0
0

Sample Output #2

1
2
2

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $N\ ≦\ 1000$, you will be awarded $ 30 $ points.

Sample Explanation 1

The input for this case represents the road information as shown in the figure in the problem statement.

见题面 Input 部分

见题面 Output 部分