Kuvaus

Yritys koostuu $n$ jäsenestä, joiden työntekijätunnukset ovat $1, 2, \dots, n$. Jäsen $1$ on pomo, ja jokaisella muulla jäsenellä $i$ ($2 \le i \le n$) on suora esihenkilö $f_i$ ($1 \le f_i < i$). Yrityksen rakenne muodostaa juurellisen puun, jonka juurena on jäsen $1$.

Tässä yrityksessä jäsen $a$ tuntee jäsenen $b$ jos ja vain jos vähintään yksi seuraavista ehdoista täyttyy:

• $a = b$.
• $b$ on jäsenen $a$ esi-isä. Toisin sanoen on olemassa jono $u_1, u_2, \dots, u_k$ ($2 \le k$) siten, että $u_1 = a$, $u_k = b$ ja $u_i = f_{u_{i-1}}$ kaikilla $2 \le i \le k$.
• $b$ on jäsenen $a$ suora lapsi ($b$ on jäsenen $a$ suora alainen). Toisin sanoen $f_b = a$.

Huomaa, että tuttavuussuhde ei ole välttämättä symmetrinen; se, että $a$ tuntee jäsenen $b$, ei tarkoita, että $b$ tuntisi jäsenen $a$.

Nyt jäsenet pelaavat peliä. Jokaisella kierroksella tietty jäsen $m$ toimii arvaajana ja toinen jäsen $p$ on kohde. On taattu, että $p$ on jäsen, jota $m$ ei tunne.

Tunnistaakseen jäsenen $p$ jäsen $m$ esittää sarjan kysymyksiä. Jokaisessa kysymyksessä $m$ valitsee tunnuksen $x$ ja kysyy: ”Tunteeko $p$ jäsenen $x$?” Jäsen $p$ vastaa aina totuudenmukaisesti. Lisäksi jos $x = p$, $p$ paljastaa erikseen olevansa jäsen $x$, jolloin peli päättyy.

Jokaiseen kysymykseen liittyy yrityspuuhun perustuva matkakustannus. Jos $i$-s kysymys koskee jäsentä $x_i$, kyseisen kysymyksen kustannus on $dis(x_{i-1}, x_i)$, missä $dis(a, b)$ on solmujen $a$ ja $b$ välisen yksikäsitteisen polun kaarien lukumäärä puussa. Ensimmäisen kysymyksen ($i = 1$) kustannus on $dis(m, x_1)$.

Jäsen $m$ on erittäin älykäs ja käyttää optimaalista strategiaa minimoidakseen kokonaiskustannuksen, joka tarvitaan pelin päättymisen takaamiseen pahimmassa tapauksessa. Tehtäväsi on laskea tämä pahimman tapauksen pienin kustannus jokaiselle mahdolliselle arvaajalle $m \in \{1, 2, \dots, n\}$.

Jos jäsen $m$ tuntee jo kaikki yrityksen jäsenet, vastaus tälle $m$:lle on $0$.

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$), joka esittää yrityksen jäsenten kokonaismäärää.

Toinen rivi sisältää $n - 1$ kokonaislukua, jotka esittävät lukuja $f_2, f_3, \dots, f_n$. Pätee $1 \le f_i < i$.

Tuloste

Tulosta yksi rivi, joka sisältää $n$ kokonaislukua välilyönnein eroteltuina: vastaukset tapauksille $m = 1, m = 2, \dots, m = n$.

Esimerkit

Esimerkkisyöte 1

3
1 1

Esimerkkituloste 1

0 2 2

Esimerkkisyöte 2

5
1 1 3 2

Esimerkkituloste 2

4 3 3 4 4

Esimerkkisyöte 3

6
1 1 2 2 3

Esimerkkituloste 3

4 3 5 4 4 6

Huomautus

Selitetään esimerkin 3 tapaus $m = 4$: Ensinnäkin, kuten kaaviosta näkyy, jäsen $m$ ei tunne jäseniä $\{3, 5, 6\}$. Yksi mahdollinen optimaalinen strategia on kysyä ensin, tunteeko $p$ jäsenen $2$, mikä maksaa $1$. Jos tuntee, se tarkoittaa, että $p = 5$, ja seuraava askel on kysyä jäsenestä $5$ pelin lopettamiseksi, jolloin kokonaiskustannus on $2$. Muussa tapauksessa jatketaan kysymällä, tunteeko $p$ jäsenen $3$, mikä maksaa $2$. Jos $p = 3$, peli päättyy kokonaiskustannuksella $3$. Muussa tapauksessa se tarkoittaa, että $p = 6$, ja seuraava askel maksaa $1$ jäsenestä $6$ kysymiseksi, jolloin peli päättyy kokonaiskustannuksella $4$. Näin ollen tämä strategia vaatii pahimmassa tapauksessa kustannuksen $4$. Voidaan todistaa, ettei mikään muu strategia voi pienentää pahimman tapauksen kyselykustannusta enempää.