Beskrivelse

Et selskap består av $n$ medlemmer med ansatt-ID $1, 2, \dots, n$. Medlem $1$ er sjefen, og hvert annet medlem $i$ ($2 \le i \le n$) har en nærmeste leder $f_i$ ($1 \le f_i < i$). Selskapsstrukturen danner et rotfestet tre med medlem $1$ som rot.

I dette selskapet kjenner medlem $a$ medlem $b$ hvis og bare hvis minst én av følgende betingelser er oppfylt:

• $a = b$.
• $b$ er en forgjenger (ane) til $a$. Med andre ord finnes det en følge $u_1, u_2, \dots, u_k$ ($2 \le k$) slik at $u_1 = a$, $u_k = b$ og $u_i = f_{u_{i-1}}$ for alle $2 \le i \le k$.
• $b$ er et direkte barn av $a$ ($b$ er en direkte underordnet av $a$). Med andre ord, $f_b = a$.

Merk at kjennskapsrelasjonen ikke nødvendigvis er symmetrisk; at $a$ kjenner $b$ betyr ikke at $b$ kjenner $a$.

Nå spiller medlemmene et spill. I hver runde fungerer et bestemt medlem $m$ som gjetteren, og et annet medlem $p$ er målet. Det er garantert at $p$ er et medlem som $m$ ikke kjenner.

For å identifisere $p$ stiller $m$ en rekke spørsmål. For hvert spørsmål velger $m$ en ID $x$ og spør: «Kjenner $p$ medlem $x$?» Medlem $p$ svarer alltid ærlig. I tillegg, hvis $x = p$, vil $p$ spesifikt avsløre at vedkommende er medlem $x$, og da avsluttes spillet.

Hvert spørsmål har en reisekostnad basert på selskapstreet. Hvis det $i$-te spørsmålet gjelder medlem $x_i$, er kostnaden for dette spørsmålet $dis(x_{i-1}, x_i)$, der $dis(a, b)$ er antall kanter på den unike stien mellom $a$ og $b$ i treet. For det første spørsmålet ($i = 1$) er kostnaden $dis(m, x_1)$.

Medlem $m$ er ekstremt smart og bruker en optimal strategi for å minimere den totale kostnaden som kreves for å garantere at spillet fullføres i verste fall (worst-case scenario). Din oppgave er å beregne denne minimale kostnaden i verste fall for hver mulig gjetter $m \in \{1, 2, \dots, n\}$.

Hvis et medlem $m$ allerede kjenner alle i selskapet, er svaret for denne $m$ lik $0$.

Inndata

Den første linjen i inndataene inneholder et heltall $n$ ($1 \le n \le 10^5$), som representerer det totale antallet medlemmer i selskapet.

Den andre linjen inneholder $n - 1$ heltall, som representerer $f_2, f_3, \dots, f_n$. Det gjelder at $1 \le f_i < i$.

Utdata

Skriv ut én enkelt linje som inneholder $n$ heltall, som representerer svarene for tilfellene der $m = 1, m = 2, \dots, m = n$. Heltallene skal være adskilt med mellomrom.

Eksempler

Eksempelinndata 1

3
1 1

Eksempelutdata 1

0 2 2

Eksempelinndata 2

5
1 1 3 2

Eksempelutdata 2

4 3 3 4 4

Eksempelinndata 3

6
1 1 2 2 3

Eksempelutdata 3

4 3 5 4 4 6

Merk

For å forklare tilfellet $m = 4$ i eksempel 3: Først, som vist i diagrammet, kjenner ikke medlem $m$ medlemmene $\{3, 5, 6\}$. En mulig optimal strategi er å først spørre om medlem $2$ er kjent av $p$, noe som koster $1$. Hvis ja, indikerer det at $p = 5$, og neste steg er å spørre om medlem $5$ for å avslutte spillet, med en totalkostnad på $2$. Ellers fortsetter man med å spørre om medlem $3$ er kjent av $p$, noe som koster $2$. Hvis $p = 3$, avsluttes spillet med en totalkostnad på $3$. Ellers indikerer det at $p = 6$, og neste steg koster $1$ for å spørre om medlem $6$, noe som avslutter spillet med en totalkostnad på $4$. Derfor krever denne strategien en kostnad på $4$ i verste fall. Det kan bevises at ingen annen strategi kan redusere spørrekostnaden i verste fall ytterligere.