D. Чёрный, серый и белый
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Изначально все вершины белые.

Вы должны выбрать одно целое число $$$k$$$ от $$$1$$$ до $$$2n$$$ включительно. После этого для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ в порядке возрастания, если в дереве существует вершина $$$k-i$$$ и $$$k-i \ne i$$$, выполняется следующая операция:

  1. вершины $$$i$$$ и $$$k-i$$$ перекрашиваются в чёрный цвет независимо от их текущего цвета;
  2. все белые вершины на простом пути между $$$i$$$ и $$$k-i$$$ перекрашиваются в серый цвет. Цвет остальных вершин на этом пути не меняется.

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

Выведите оптимальное значение $$$k$$$. Если подходящих значений $$$k$$$ несколько, выведите любое из них.

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

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

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

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$) — концы очередного ребра.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$;
  • в каждом наборе входных данных рёбра задают дерево.
Выходные данные

Для каждого набора входных данных выведите одно целое число $$$k$$$ ($$$1 \le k \le 2n$$$), удовлетворяющее требованиям задачи. Если оптимальных значений несколько, выведите любое из них.

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

В первом наборе входных данных выбрано $$$k=6$$$. После всех операций вершины $$$1$$$, $$$2$$$, $$$4$$$ и $$$5$$$ чёрные, а вершина $$$3$$$ серая.

Во втором наборе входных данных выбрано $$$k=7$$$. После всех операций все шесть вершин чёрные, серых вершин нет.