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

Недавно Маленький Джон получил дерево от своей тёти, чтобы украсить свой дом. Но, как кажется, одного дерева недостаточно, чтобы украсить весь дом. У Маленького Джона появилась идея. Может быть, он сможет удалить несколько вершин из дерева. Это превратит его в большее количество деревьев! Верно?

Вам дано дерево$$$^{\text{∗}}$$$, состоящее из $$$n$$$ вершин. Вы должны выполнить следующую операцию ровно дважды.

  • Выберите вершину $$$v$$$;
  • Удалите все рёбра, соединённые с вершиной $$$v$$$, а также саму вершину $$$v$$$.

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

Две вершины $$$x$$$ и $$$y$$$ находятся в одной компоненте связности тогда и только тогда, когда существует путь от $$$x$$$ до $$$y$$$. Граф с $$$0$$$ вершинами имеет $$$0$$$ компонент связности по определению.$$$^{\text{†}}$$$

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

$$$^{\text{†}}$$$Но считается ли такой граф связным?..

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$, обозначающие две вершины, соединённые ребром ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$). Гарантируется, что данные рёбра образуют дерево.

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

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

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

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

В первом примере удаление вершины дважды сделает граф пустым. По определению количество компонент связности в графе с $$$0$$$ вершинами равно $$$0$$$. Поэтому ответ равен $$$0$$$.

Во втором примере удаление двух вершин $$$1$$$ и $$$2$$$ оставляет $$$2$$$ компоненты связности. Поскольку невозможно создать $$$3$$$ компоненты связности с $$$2$$$ вершинами, ответ равен $$$2$$$.

В третьем примере удаление двух вершин $$$1$$$ и $$$5$$$ оставляет $$$4$$$ компоненты связности, которые являются $$$\left\{ 2,4\right\}$$$, $$$\left\{ 3\right\}$$$, $$$\left\{ 6\right\}$$$ и $$$\left\{ 7\right\}$$$. Можно показать, что невозможно получить $$$5$$$ компонент связности. Поэтому ответ равен $$$4$$$.