Beskrivning

Ett företag består av $n$ medlemmar med anställnings-ID $1, 2, \dots, n$. Medlem $1$ är chefen, och varje annan medlem $i$ ($2 \le i \le n$) har en närmaste chef $f_i$ ($1 \le f_i < i$). Företagsstrukturen bildar ett rotat träd med medlem $1$ som rot.

I detta företag känner medlem $a$ medlem $b$ om och endast om minst ett av följande villkor är uppfyllt:

• $a = b$.
• $b$ är en förfader till $a$. Med andra ord finns det en följd $u_1, u_2, \dots, u_k$ ($2 \le k$) sådan att $u_1 = a$, $u_k = b$ och $u_i = f_{u_{i-1}}$ för alla $2 \le i \le k$.
• $b$ är ett direkt barn till $a$ ($b$ är en direkt underordnad till $a$). Med andra ord, $f_b = a$.

Observera att bekantskapsrelationen inte nödvändigtvis är symmetrisk; att $a$ känner $b$ innebär inte att $b$ känner $a$.

Nu spelar medlemmarna ett spel. I varje runda agerar en specifik medlem $m$ som gissare, och en annan medlem $p$ är målet. Det garanteras att $p$ är en medlem som $m$ inte känner.

För att identifiera $p$ ställer $m$ en följd av frågor. För varje fråga väljer $m$ ett ID $x$ och frågar: ”Känner $p$ medlem $x$?” Medlem $p$ svarar alltid sanningsenligt. Dessutom, om $x = p$, kommer $p$ specifikt att avslöja att hen är medlem $x$, varpå spelet avslutas.

Varje fråga medför en resekostnad baserad på företagsträdet. Om den $i$-te frågan gäller medlem $x_i$ är kostnaden för den frågan $dis(x_{i-1}, x_i)$, där $dis(a, b)$ är antalet kanter på den unika vägen mellan $a$ och $b$ i trädet. För den första frågan ($i = 1$) är kostnaden $dis(m, x_1)$.

Medlem $m$ är extremt smart och använder en optimal strategi för att minimera den totala kostnaden som krävs för att garantera att spelet slutförs i värsta fall (worst-case scenario). Din uppgift är att beräkna denna minimala värstafallskostnad för varje möjlig gissare $m \in \{1, 2, \dots, n\}$.

Om en medlem $m$ redan känner alla i företaget är svaret för detta $m$ lika med $0$.

Indata

Den första raden i indatan innehåller ett heltal $n$ ($1 \le n \le 10^5$), som representerar det totala antalet medlemmar i företaget.

Den andra raden innehåller $n - 1$ heltal, som representerar $f_2, f_3, \dots, f_n$. Det gäller att $1 \le f_i < i$.

Utdata

Skriv ut en enda rad som innehåller $n$ heltal, vilka representerar svaren för fallen där $m = 1, m = 2, \dots, m = n$. Heltalen ska separeras med mellanslag.

Exempel

Exempelindata 1

3
1 1

Exempelutdata 1

0 2 2

Exempelindata 2

5
1 1 3 2

Exempelutdata 2

4 3 3 4 4

Exempelindata 3

6
1 1 2 2 3

Exempelutdata 3

4 3 5 4 4 6

Anmärkning

För att förklara fallet $m = 4$ i exempel 3: Först, som visas i diagrammet, känner medlem $m$ inte medlemmarna $\{3, 5, 6\}$. En möjlig optimal strategi är att först fråga om medlem $2$ är känd av $p$, vilket kostar $1$. Om så är fallet, indikerar det att $p = 5$, och nästa steg är att fråga om medlem $5$ för att avsluta spelet, med en totalkostnad på $2$. Annars fortsätter man med att fråga om medlem $3$ är känd av $p$, vilket kostar $2$. Om $p = 3$ avslutas spelet med en totalkostnad på $3$. Annars indikerar det att $p = 6$, och nästa steg kostar $1$ för att fråga om medlem $6$, vilket avslutar spelet med en totalkostnad på $4$. Därför kräver denna strategi en kostnad i värsta fall på $4$. Det kan bevisas att ingen annan strategi kan minska frågekostnaden i värsta fall ytterligare.