Дано дерево (связный граф без циклов) на \(n\) вершинах.
Зафиксируем число \(k\). Назовем графом \(G_k\) граф на \(n\) вершинах, в котором между вершинами \(u\) и \(v\) есть ребро тогда и только тогда, когда расстояние между вершинами \(u\) и \(v\) в данном дереве не меньше \(k\).
Для каждого \(k\) от \(1\) до \(n\) выведите количество компонент связности в графе \(G_k\).
Выходные данные
Выведите \(n\) целых чисел — количество компонент связности в графе \(G_k\) для каждого \(k\) от \(1\) до \(n\).
Примечание
В первом примере: При \(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\) каждая вершина является отдельной компонентой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2
1 3
2 4
2 5
3 6
|
1 1 2 4 6 6
|
|
2
|
5
1 2
2 3
3 4
3 5
|
1 1 3 5 5
|