Вам дано дерево из \(n\) вершин.
Ваша задача — найти такое максимальное число \(x\), что можно удалить из этого дерева ровно \(k\) ребер так, чтобы размер каждой оставшейся компоненты связности\(^{\dagger}\) был не менее \(x\).
\(^{\dagger}\) Две вершины \(v\) и \(u\) находятся в одной компоненте связности, если существует такая последовательность чисел \(t_1, t_2, \ldots, t_k\) произвольной длины \(k\), такая что \(t_1 = v\), \(t_k = u\), и для каждого \(i\) от \(1\) до \(k - 1\) вершины \(t_i\) и \(t_{i+1}\) соединены ребром.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите такое максимальное число \(x\), что можно удалить ровно \(k\) ребер дерева так, чтобы размер каждой оставшейся компоненты связности был равен не менее \(x\).
Примечание
Дерево в первом наборе входных данных:
После удаления ребра \(1\) — \(3\) дерево будет выглядеть следующим образом:
Дерево распалось на две компоненты связности. Первая компонента состоит из двух вершин: \(1\) и \(2\). Вторая компонента связности состоит из трех вершин: \(3, 4\) и \(5\). В обоих компонентах связности не менее двух вершин. Можно показать, что ответ \(3\) не достижим, поэтому ответ \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 1
1 2
1 3
3 4
3 5
2 1
1 2
6 1
1 2
2 3
3 4
4 5
5 6
3 1
1 2
1 3
8 2
1 2
1 3
2 4
2 5
3 6
3 7
3 8
6 2
1 2
2 3
1 4
4 5
5 6
|
2
1
3
1
1
2
|