Пусть \(G\) — простой граф, а \(W\) — непустое подмножество множества вершин этого графа. Назовем \(W\) почти-\(k\)-единым, если для каждой пары различных вершин \(u,v \in W\) расстояние между \(u\) и \(v\) равно либо \(k\), либо \(k+1\).
Вам задано дерево из \(n\) вершин. Для каждого \(i\) от \(1\) до \(n\) найдите максимальный размер почти-\(i\)-единого множества вершин.
Выходные данные
Выведите одну строку, содержащую \(n\) целых чисел \(a_i\), где \(a_i\) — максимальный размер почти-\(i\)-единого множества.
Примечание
Рассмотрим первый пример.
- Единственное максимальное почти-\(1\)-единое множество вершин — это \(\{1, 2, 3, 4\}\).
- Одно из максимальных почти-\(2\)-единых множеств — \(\{2, 3, 5\}\), также таким множеством является \(\{2, 3, 4\}\).
- Максимальное почти-\(3\)-единое множество — любые две вершины на расстоянии \(3\).
- Почти-\(k\)-единое множество может состоять из единственной (любой) вершины для любого \(k \geq 1\).
Во втором примере существует почти-\(2\)-единое множество размера \(4\): \(\{2, 3, 5, 6\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
1 3
1 4
4 5
|
4 3 2 1 1
|
|
2
|
6
1 2
1 3
1 4
4 5
4 6
|
4 4 2 1 1 1
|