У 378QAQ есть дерево с \(n\) вершинами. Изначально все вершины белые.
На дереве есть две шахматные фигуры с названиями \(P_A\) и \(P_B\). \(P_A\) и \(P_B\) изначально расположены на вершинах \(a\) и \(b\) соответственно. За один шаг 378QAQ выполняет следующие действия по порядку:
- Переместить \(P_A\) в соседнюю вершину. Если вершина, в которую переместилась фигура, белая, то перекрасить эту вершину в красный цвет.
- Переместить \(P_B\) в соседнюю вершину. Если вершина, в которую переместилась фигура, красная, то перекрасить эту вершину в синий цвет.
Изначально вершина \(a\) окрашена в красный цвет. Если \(a=b\), то вместо этого вершина \(a\) окрашена в синий цвет. Обратите внимание, что на каждом шаге обе шахматные фигуры должны быть перемещены. Две фигуры могут находиться в одной вершине в любой момент времени.
378QAQ хочет узнать минимальное количество шагов, которое требуется, чтобы покрасить все вершины в синий цвет.
Выходные данные
Для каждого набора входных данных выведите минимальное количество шагов, которое требуется, чтобы покрасить все вершины в синий цвет.
Примечание
В первом наборе входных данных 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\) и закрашивает её синим цветом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|