Деревом называется связный неориентированный граф, в котором между любыми двумя вершинами существует ровно один простой путь. Будем говорить, что множество простых путей является $$$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
Один из способов достичь наибольшего количества путей во втором примере изображён на следующей картинке:
