Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

У 378QAQ есть дерево с $$$n$$$ вершинами. Изначально все вершины белые.

На дереве есть две шахматные фигуры с названиями $$$P_A$$$ и $$$P_B$$$. $$$P_A$$$ и $$$P_B$$$ изначально расположены на вершинах $$$a$$$ и $$$b$$$ соответственно. За один шаг 378QAQ выполняет следующие действия по порядку:

  1. Переместить $$$P_A$$$ в соседнюю вершину. Если вершина, в которую переместилась фигура, белая, то перекрасить эту вершину в красный цвет.
  2. Переместить $$$P_B$$$ в соседнюю вершину. Если вершина, в которую переместилась фигура, красная, то перекрасить эту вершину в синий цвет.

Изначально вершина $$$a$$$ окрашена в красный цвет. Если $$$a=b$$$, то вместо этого вершина $$$a$$$ окрашена в синий цвет. Обратите внимание, что на каждом шаге обе шахматные фигуры должны быть перемещены. Две фигуры могут находиться в одной вершине в любой момент времени.

378QAQ хочет узнать минимальное количество шагов, которое требуется, чтобы покрасить все вершины в синий цвет.

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

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

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

Вторая строка каждого набора входных данных содержит два целых числа $$$a$$$ и $$$b$$$ ($$$1\leq a,b\leq n$$$).

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

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

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

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

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

В первом наборе входных данных 378QAQ может покрасить все вершины в синий цвет следующим образом:

  • Изначально $$$P_A$$$ находится в вершине $$$1$$$, а $$$P_B$$$ — в вершине $$$2$$$. Вершина $$$1$$$ окрашена в красный цвет, а вершина $$$2$$$ — в белый.
  • 378QAQ перемещает $$$P_A$$$ в вершину $$$2$$$ и красит ее в красный цвет. Затем 378QAQ перемещает $$$P_B$$$ в вершину $$$1$$$ и красит её в синий цвет.
  • 378QAQ перемещает $$$P_A$$$ в вершину $$$1$$$. Затем 378QAQ перемещает $$$P_B$$$ в вершину $$$2$$$ и закрашивает её синим цветом.