Дано дерево\(^{\text{∗}}\) из \(n\) вершин. Вы можете один раз выбрать две вершины \(a\) и \(b\) и удалить все вершины на пути из \(a\) в \(b\), включая сами вершины. Если вы выберете \(a=b\), то будет удалена только одна вершина.
Ваша задача — найти максимальное количество компонент связности\(^{\text{†}}\), которое может образоваться после удаления пути из дерева.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное число компонент связности, которого можно добиться с помощью описанной операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2
1 2
5
1 2
2 3
3 4
3 5
4
1 2
2 3
3 4
5
2 1
3 1
4 1
5 4
6
2 1
3 1
4 1
5 3
6 3
6
2 1
3 2
4 2
5 3
6 4
|
1
3
2
3
4
3
|