Деревоподібне пасовище

Limits: 2 sec., 256 MiB

Зеник з Марічкою хочуть продати своє старе пасовище.

Старе пасовище складається з $n$ ділянок, пронумерованих від $1$ до $n$. Ділянки пасовища з’єднані між собою $n-1$ доріжками. Між кожною парою ділянок пасовища можна дістатися доріжками. Іншими словами, пасовище має деревоподібну структуру.

Зеник і Марічка виберуть деяку ділянку $w$ та набір з $k$ ділянок $(w = a_1, a_2, \dots, a_k)$, де для всіх $i$ від $1$ до $k-1$ ділянки $a_i$ та $a_{i+1}$ з’єднані доріжкою. Усі $a_i$ в наборі повинні бути різними. Ділянка $w$ є першою ділянкою в наборі. Зеник обгородить парканом ділянки з вибраного набору.

Після цього пасовище розділиться на кілька частин, одна з яких буде відгороджена парканом від інших.

Для всіх $w$ від $1$ до $n$ знайдіть, на яку найбільшу кількість частин Зеник з Марічкою можуть розділити пасовище, обгородивши парканом деякий набір ділянок $(w = a_1, a_2, \dots, a_k)$.

Input

У першому рядку задано ціле число $n$ — кількість ділянок пасовища.

У наступних $n-1$ рядках задано по два цілих числа $u_i$ та $v_i$ — номери ділянок, з’єднаних доріжками.

Output

В одному рядку виведіть $n$ цілих чисел — відповідь на задачу для всіх $w$ від $1$ до $n$.

Constraints

$3 \le n \le 2 \cdot 10^5$,

$1 \le a_i, b_i \le n$.

Samples

Input (stdin) сopy	Output (stdout) сopy
12 1 2 1 3 1 4 5 4 6 4 4 9 9 10 11 12 4 11 6 8 6 7	8 7 7 7 6 8 7 7 7 6 7 6

Notes

На рисунку зображено приклад. Для $w=1$ оптимально вибрати набір ділянок $(1, 4, 6)$ та обгородити ділянки з набору парканом (позначено синім прямокутником на рисунку). Пасовище розділиться на вісім частин, позначених на рисунку різними кольорами.