Дано дерево\(^{\text{∗}}\) из \(n\) вершин. Вы можете один раз выбрать две вершины \(a\) и \(b\) и удалить все вершины на пути из \(a\) в \(b\), включая сами вершины. Если вы выберете \(a=b\), то будет удалена только одна вершина.
Ваша задача — найти максимальное количество компонент связности\(^{\text{†}}\), которое может образоваться после удаления пути из дерева.
\(^{\text{∗}}\)Деревом называется связный граф без циклов.
\(^{\text{†}}\)Компонента связности это такое множество вершин, в котором из каждой вершины можно попасть по рёбрам в любую другую (и нельзя попасть в вершины, не принадлежащие этому множеству)
Первая строка входных данных содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число \(n\) (\(2 \le n \le 2 \cdot 10^5\)) — размер дерева.
Следующие \(n-1\) строк содержат по два целых числа \(u\) и \(v\) (\(1 \le u, v \le n\), \(u \ne v\)) — вершины, соединённые ребром. Гарантируется, что рёбра образуют дерево.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — максимальное число компонент связности, которого можно добиться с помощью описанной операции.
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач