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

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)\) та обгородити ділянки з набору парканом (позначено синім прямокутником на рисунку). Пасовище розділиться на вісім частин, позначених на рисунку різними кольорами.