Деревом называется связный неориентированный граф, в котором между любыми двумя вершинами существует ровно один простой путь. Будем говорить, что множество простых путей является \(k\)-допустимым, если каждая вершина дерева принадлежит не более чем одному из этих путей (включая концевые вершины) и каждый путь состоит ровно из \(k\) вершин.
Вам дано дерево на \(n\) вершинах. Для каждого \(k\) от \(1\) до \(n\) включительно найдите максимально возможную мощность \(k\)-допустимого множества простых путей.
Выходные данные
Выведите \(n\) чисел, \(i\)-е из которых равно максимально возможной мощности \(i\)-допустимого множества путей.
Примечание
Один из способов достичь наибольшего количества путей во втором примере изображён на следующей картинке:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 2
2 3
3 4
4 5
5 6
6 7
|
7
3
2
1
1
1
1
|
|
2
|
6
1 2
2 3
2 4
1 5
5 6
|
6
2
2
1
1
0
|