D. Широкий-преширокий граф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево (связный граф без циклов) на $$$n$$$ вершинах.

Зафиксируем число $$$k$$$. Назовем графом $$$G_k$$$ граф на $$$n$$$ вершинах, в котором между вершинами $$$u$$$ и $$$v$$$ есть ребро тогда и только тогда, когда расстояние между вершинами $$$u$$$ и $$$v$$$ в данном дереве не меньше $$$k$$$.

Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ выведите количество компонент связности в графе $$$G_k$$$.

Входные данные

В первой строке дано целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество вершин в графе.

В каждой из следующих $$$n-1$$$ строк содержатся два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), обозначающие ребро между вершинами $$$u$$$ и $$$v$$$ в дереве. Гарантируется, что данные ребра задают корректное дерево.

Выходные данные

Выведите $$$n$$$ целых чисел — количество компонент связности в графе $$$G_k$$$ для каждого $$$k$$$ от $$$1$$$ до $$$n$$$.

Примеры
Входные данные
6
1 2
1 3
2 4
2 5
3 6
Выходные данные
1 1 2 4 6 6
Входные данные
5
1 2
2 3
3 4
3 5
Выходные данные
1 1 3 5 5
Примечание

В первом примере: При $$$k=1$$$ в графе будет ребро между каждой парой вершин, поэтому в нём будет одна компонента. При $$$k=4$$$ в графе будут только рёбра $$$4 \leftrightarrow 6$$$ и $$$5 \leftrightarrow 6$$$, поэтому в графе будет $$$4$$$ компоненты.

Во втором примере: при $$$k=1$$$ и $$$k=2$$$ в графе одна компонента. При $$$k=3$$$ граф $$$G_k$$$ разбивается на $$$3$$$ компоненты: в одной компоненте вершины $$$1$$$, $$$4$$$ и $$$5$$$, а ещё две компоненты содержат по одной вершине. При $$$k=4$$$ и $$$k=5$$$ каждая вершина является отдельной компонентой.