Есептің шарты

Компания қызметкер ID-лері $1, 2, \dots, n$ болатын $n$ мүшеден тұрады. $1$-мүше — бастық, ал қалған әрбір $i$-мүшенің ($2 \le i \le n$) тікелей жетекшісі $f_i$ ($1 \le f_i < i$) бар. Компания құрылымы түбірінде $1$-мүше орналасқан түбірлі ағашты құрайды.

Бұл компанияда $a$ мүшесі $b$ мүшесін келесі шарттардың кем дегенде біреуі орындалса және тек сонда ғана таниды:

• $a = b$.
• $b$ — $a$ мүшесінің арғы тегі (ата-бабасы). Басқаша айтқанда, $u_1 = a$, $u_k = b$ және барлық $2 \le i \le k$ үшін $u_i = f_{u_{i-1}}$ болатындай $u_1, u_2, \dots, u_k$ ($2 \le k$) тізбегі бар.
• $b$ — $a$ мүшесінің тікелей баласы ($b$ — $a$ мүшесінің тікелей бағыныштысы). Басқаша айтқанда, $f_b = a$.

Таныстық қатынасы міндетті түрде симметриялы емес екенін ескеріңіз: $a$-ның $b$-ны тануы $b$-ның $a$-ны танитынын білдірмейді.

Қазір мүшелер ойын ойнап жатыр. Әр раундта белгілі бір $m$ мүшесі болжаушы рөлін атқарады, ал басқа бір $p$ мүшесі нысана болады. $p$ мүшесі $m$ танымайтын мүше екеніне кепілдік беріледі.

$p$-ны анықтау үшін $m$ бірқатар сұрақтар қояды. Әр сұрақта $m$ бір $x$ ID-ін таңдап: «$p$ мүшесі $x$ мүшесін тани ма?» деп сұрайды. $p$ мүшесі әрқашан шын жауап береді. Сонымен қатар, егер $x = p$ болса, $p$ өзінің $x$ мүшесі екенін арнайы айтады да, сол сәтте ойын аяқталады.

Әрбір сұрақ компания ағашына негізделген жол жүру шығынын талап етеді. Егер $i$-ші сұрақ $x_i$ мүшесіне қатысты болса, ол сұрақтың құны $dis(x_{i-1}, x_i)$ болады, мұндағы $dis(a, b)$ — ағаштағы $a$ мен $b$ арасындағы жалғыз жолдағы қырлар саны. Бірінші сұрақ үшін ($i = 1$) құны $dis(m, x_1)$ болады.

$m$ мүшесі өте ақылды және ең нашар жағдайда ойынның аяқталуын кепілдендіруге қажетті жалпы шығынды барынша азайту үшін оңтайлы стратегияны қолданады. Сіздің міндетіңіз — әрбір мүмкін болжаушы $m \in \{1, 2, \dots, n\}$ үшін осы ең нашар жағдайдағы ең аз шығынды есептеу.

Егер $m$ мүшесі компаниядағы барлық адамды бұрыннан танитын болса, ол $m$ үшін жауап $0$ болады.

Кіріс деректер

Кірістің бірінші жолында компаниядағы мүшелердің жалпы санын білдіретін бүтін сан $n$ ($1 \le n \le 10^5$) берілген.

Екінші жолда $f_2, f_3, \dots, f_n$ мәндерін білдіретін $n - 1$ бүтін сан берілген. $1 \le f_i < i$ шарты орындалады.

Шығыс деректер

$m = 1, m = 2, \dots, m = n$ жағдайлары үшін жауаптарды білдіретін, бос орынмен бөлінген $n$ бүтін саннан тұратын бір жолды шығарыңыз.

Мысалдар

Мысал кірісі 1

3
1 1

Мысал шығысы 1

0 2 2

Мысал кірісі 2

5
1 1 3 2

Мысал шығысы 2

4 3 3 4 4

Мысал кірісі 3

6
1 1 2 2 3

Мысал шығысы 3

4 3 5 4 4 6

Ескертпе

3-мысалдағы $m = 4$ жағдайын түсіндіру үшін: Біріншіден, диаграммада көрсетілгендей, $m$ мүшесі $\{3, 5, 6\}$ мүшелерін танымайды. Мүмкін болатын оңтайлы стратегиялардың бірі — алдымен $p$-ның $2$-мүшені танитынын-танымайтынын $1$ шығынмен сұрау. Егер таныса, бұл $p = 5$ екенін білдіреді, ал келесі қадам — ойынды жалпы құны $2$-мен аяқтау үшін $5$-мүше туралы сұрау. Әйтпесе, $p$-ның $3$-мүшені танитынын-танымайтынын $2$ шығынмен сұрауды жалғастырамыз. Егер $p = 3$ болса, ойын жалпы құны $3$-пен аяқталады. Әйтпесе, бұл $p = 6$ екенін білдіреді, ал келесі қадамда $6$-мүше туралы сұрауға $1$ шығын кетеді де, ойын жалпы құны $4$-пен аяқталады. Сондықтан бұл стратегия ең нашар жағдайда $4$ шығынды қажет етеді. Басқа ешбір стратегия ең нашар жағдайдағы сұрау шығынын одан әрі азайта алмайтынын дәлелдеуге болады.