الوصف

تتكون شركة من $n$ أعضاء بأرقام تعريف موظفين $1, 2, \dots, n$. العضو $1$ هو المدير، ولكل عضو آخر $i$ ($2 \le i \le n$) مشرف مباشر $f_i$ ($1 \le f_i < i$). يشكل هيكل الشركة شجرة مجذرة جذرها العضو $1$.

في هذه الشركة، العضو $a$ يعرف العضو $b$ إذا وفقط إذا تحقق شرط واحد على الأقل من الشروط التالية:

• $a = b$.
• $b$ هو سلف لـ $a$. بعبارة أخرى، توجد متتالية $u_1, u_2, \dots, u_k$ ($2 \le k$) بحيث يكون $u_1 = a$، و$u_k = b$، و$u_i = f_{u_{i-1}}$ لجميع $2 \le i \le k$.
• $b$ هو ابن مباشر لـ $a$ ($b$ هو مرؤوس مباشر لـ $a$). بعبارة أخرى، $f_b = a$.

لاحظ أن علاقة المعرفة ليست بالضرورة متماثلة؛ فمعرفة $a$ بـ $b$ لا تعني بالضرورة أن $b$ يعرف $a$.

الآن، يلعب الأعضاء لعبة. في كل جولة، يعمل عضو معين $m$ كـ مُخمِّن، ويكون عضو آخر $p$ هو الهدف. من المضمون أن $p$ هو عضو لا يعرفه $m$.

لتحديد هوية $p$، يطرح $m$ سلسلة من الأسئلة. في كل سؤال، يختار $m$ رقم تعريف $x$ ويسأل: «هل يعرف $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$)، يمثل العدد الإجمالي للأعضاء في الشركة.

يحتوي السطر الثاني على $n - 1$ أعداد صحيحة، تمثل $f_2, f_3, \dots, f_n$. وتتحقق المتباينة $1 \le f_i < i$.

الإخراج

اطبع سطرًا واحدًا يحتوي على $n$ أعداد صحيحة، تمثل الإجابات للحالات التي يكون فيها $m = 1, m = 2, \dots, m = 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

ملاحظة

لتوضيح حالة $m = 4$ في المثال 3: أولًا، كما هو موضح في الرسم التخطيطي، لا يعرف العضو $m$ الأعضاء $\{3, 5, 6\}$. تتمثل إحدى الاستراتيجيات المثلى الممكنة في السؤال أولًا عما إذا كان العضو $2$ معروفًا لدى $p$، بتكلفة قدرها $1$. إذا كان الأمر كذلك، فهذا يشير إلى أن $p = 5$، والخطوة التالية هي السؤال عن العضو $5$ لإنهاء اللعبة، بتكلفة إجمالية قدرها $2$. وإلا، يستمر في السؤال عما إذا كان العضو $3$ معروفًا لدى $p$، بتكلفة قدرها $2$. إذا كان $p = 3$، تنتهي اللعبة بتكلفة إجمالية قدرها $3$. وإلا، فهذا يشير إلى أن $p = 6$، وتكلف الخطوة التالية $1$ للسؤال عن العضو $6$، مما ينهي اللعبة بتكلفة إجمالية قدرها $4$. وبالتالي، تتطلب هذه الاستراتيجية تكلفة في أسوأ الحالات قدرها $4$. يمكن إثبات أنه لا توجد استراتيجية أخرى يمكنها تقليل تكلفة الاستعلام في أسوأ الحالات أكثر من ذلك.