H. Опавшие листья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юсефу дано дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$.

Пусть $$$S$$$ — множество всех листьев$$$^{\text{†}}$$$ данного дерева (это множество определяется по исходному дереву и не изменяется).

Юсеф повторяет следующий процесс, пока количество невыбранных вершин не станет не более одной:

  • Выбрать две различные вершины $$$u, v \in S$$$, которые ранее не были выбраны.
  • Прибавить $$$d(u, v)$$$ к общей стоимости, где $$$d(u, v)$$$ — это количество рёбер на простом пути между $$$u$$$ и $$$v$$$.
  • Пометить $$$u$$$ и $$$v$$$ как выбранные.

Ваша задача — помочь Юсефу определить минимально возможную общую стоимость, достижимую после завершения процесса.

$$$^{\text{∗}}$$$Дерево — это неориентированный связный граф, в котором нет циклов.

$$$^{\text{†}}$$$Лист дерева — это вершина, которая соединена не более чем с одной вершиной.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных состоит из нескольких строк. Первая строка набора входных данных содержит целое число $$$n$$$ ($$$3 \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$$$.

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

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

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

В первом наборе входных данных множество листьев $$$S$$$ содержит $$$\{1, 3, 4\}$$$. Юсеф может сделать следующее:

  • Выбрать $$$u = 1$$$, $$$v = 3$$$, при этом $$$d(1, 3) = 2$$$. Юсеф прибавляет $$$2$$$ к общей стоимости и помечает вершины $$$1$$$ и $$$3$$$ как выбранные.

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

Данное дерево в первом наборе входных данных.

Во втором наборе входных данных множество листьев $$$S$$$ содержит $$$\{1, 3, 5, 6\}$$$. Юсеф может сделать следующее:

  • Выбрать $$$u = 1$$$, $$$v = 3$$$, при этом $$$d(1, 3) = 2$$$. Юсеф прибавляет $$$2$$$ к общей стоимости и помечает вершины $$$1$$$ и $$$3$$$ как выбранные.
  • Выбрать $$$u = 5$$$, $$$v = 6$$$, при этом $$$d(5, 6) = 2$$$. Юсеф прибавляет $$$2$$$ к общей стоимости и помечает вершины $$$5$$$ и $$$6$$$ как выбранные.

Поскольку не осталось невыбранных вершин, процесс останавливается, и общая стоимость равна $$$4$$$.

Данное дерево во втором наборе входных данных.