D. Сжатие дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кагари готовится архивировать дерево, и она знает, что стоимость этого процесса будет зависеть от его диаметра$$$^{\text{∗}}$$$. Чтобы сократить расходы, её цель — сначала уменьшить диаметр как можно больше. Она может выполнить следующую операцию над деревом:

  1. Выбрать две вершины $$$s$$$ и $$$t$$$. Пусть последовательность вершин на простом пути$$$^{\text{†}}$$$ от $$$s$$$ до $$$t$$$ будет $$$v_0, v_1, \dots, v_k$$$, где $$$v_0 = s$$$ и $$$v_k = t$$$.
  2. Удалить все рёбра вдоль пути. Другими словами, удалить рёбра $$$(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$$$.
  3. Соединить вершины $$$v_1, v_2, \dots, v_k$$$ напрямую с $$$v_0$$$. Другими словами, добавить рёбра $$$(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$$$.

Можно показать, что граф всё ещё является деревом после выполнения операции.

Помогите ей определить минимальное количество операций, необходимых для достижения минимального диаметра.

$$$^{\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 \neq v$$$), которые указывают на ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что эти рёбра образуют дерево.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество операций для минимизации диаметра.

Пример
Входные данные
4
4
1 2
1 3
2 4
2
2 1
4
1 2
2 3
2 4
11
1 2
1 3
2 4
3 5
3 8
5 6
5 7
7 9
7 10
5 11
Выходные данные
1
0
0
4
Примечание

В первом примере диаметр исходного дерева равен $$$3$$$. Кагари может выполнить операцию на $$$s = 3$$$ и $$$t = 4$$$. Как показано на рисунке, операции включают следующие шаги:

  1. Удалить рёбра $$$(3, 1)$$$, $$$(1, 2)$$$ и $$$(2, 4)$$$.
  2. Добавить рёбра $$$(3, 1)$$$, $$$(3, 2)$$$ и $$$(3, 4)$$$.

После операции диаметр уменьшается до $$$2$$$. Можно показать, что $$$2$$$ — это минимальный диаметр.

Во втором примере диаметр дерева равен $$$1$$$. Можно показать, что $$$1$$$ уже является минимумом, поэтому Кагари не может выполнить никаких операций.