I. Игра на дереве
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Айбек и Айгуль играют в игру на дереве. Напомним, что дерево это связный граф без циклов. Дерево состоит из $$$n$$$ $$$(n \geq 2)$$$ вершин. Первым ходит Айбек - он выбирает любую вершину дерева, обозначим ее $$$u$$$. После чего ходит Айгуль и выбирает любую другую вершину дерева, обозначим ее $$$v$$$. После того, как оба игрока сделали свой выбор, случайно равновероятно выбирается какая-то одна из вершин дерева $$$w$$$ и затем:

  • Если $$$d(u, w) \lt d(v, w)$$$ — то Айбек объявляется победителем;
  • Если $$$d(u, w) \gt d(v, w)$$$ — то Айгуль объявляется победительницей;
  • Если $$$d(u, w) = d(v, w)$$$ — то объявляется ничья.

Здесь $$$d(a, b)$$$ — это расстояние между двумя вершинами дерева, то есть количество ребер на простом пути между $$$a$$$ и $$$b$$$. Айбек не очень хорош в играх на деревьях, поэтому помогите ему найти такую вершину, при выборе которой он максимизирует свою вероятность выигрыша. Если же таких вершин несколько, найдите вершину с минимальным номером.

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

В первой строке входных данных содержится одно целое число $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — количество раундов игры, в которую будут играть Айбек и Айгуль.

Далее следуют описания каждого раунда игры — в первой строке содержится целое число $$$n$$$ $$$(2 \leq n \leq 2\cdot10^5)$$$ — число вершин в дереве.

В следующих $$$n - 1$$$ строках, описывающих раунд, содержится по 2 целых числа $$$u_i$$$ и $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$ — ребра дерева.

Гарантируется, что граф из каждого раунда игры образует структуру дерева.

Также гарантируется, что сумма $$$n$$$ по всем входными данными не превосходит $$$2\cdot10^5$$$

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

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

Пример
Входные данные
2
5
1 4
4 3
4 2
2 5
2
1 2
Выходные данные
4
1
Примечание
На картинке выше изображен граф из первого раунда игры первого набора входных данных. Как легко заметить, ни одна из вершин 1, 3, 5 не является оптимальной для Айбека, потому что тогда Айгуль возьмет себе её соседа. В таком случае Айбек победит только тогда, когда будет выбрана его вершина. Вероятность того, что будет выбрана его вершина  — 1/5. При выборе между вершинами 2 и 4 можно показать, что вершина 4 выгоднее. Действительно, если взять вершину 2, то Агуль выгодно взять вершину 4, и тогда её вероятность выиграть  — 1/3. Если же взять вершину 4, то Айгуль не может сделать свою вероятность выиграть выше 1/2.
На картинке выше изображен граф из второго раунда игры первого набора выходных данных. Из симметрии видно, что нет разницы, какую вершину взять  — 1-ю или 2-ю. Но так как из всех подходящих вершин требуется вывести вершину с наименьшим номером, то ответом является 1.