D. Вам дано дерево
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Деревом называется связный неориентированный граф, в котором между любыми двумя вершинами существует ровно один простой путь. Будем говорить, что множество простых путей является $$$k$$$-допустимым, если каждая вершина дерева принадлежит не более чем одному из этих путей (включая концевые вершины) и каждый путь состоит ровно из $$$k$$$ вершин.

Вам дано дерево на $$$n$$$ вершинах. Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ включительно найдите максимально возможную мощность $$$k$$$-допустимого множества простых путей.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 100\,000$$$) — количество вершин в дереве.

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

Гарантируется, что заданный граф является деревом.

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

Выведите $$$n$$$ чисел, $$$i$$$-е из которых равно максимально возможной мощности $$$i$$$-допустимого множества путей.

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

Входные данные
6
1 2
2 3
2 4
1 5
5 6
Выходные данные
6
2
2
1
1
0

Примечание

Один из способов достичь наибольшего количества путей во втором примере изображён на следующей картинке: