Влад и Настя живут в городе, состоящем из \(n\) домов и \(n-1\) дороги. Из каждого дома можно добраться до другого передвигаясь только по дорогам. То есть город представляет собой дерево.
Влад живёт в доме с номером \(x\), а Настя в доме с номером \(y\). Влад решил пойти к Насте в гости. Однако он вспомнил, что отложил на потом \(k\) дел, которые он должен сделать прежде чем прийти к Насте. Чтобы сделать \(i\)-е дело ему необходимо прийти в \(a_i\)-й дом, дела можно делать в любом порядке. За \(1\) минуту он может пройти от одного дома до другого, если их соединяет дорога.
Влад не очень любит пешие прогулки, поэтому его интересует, какое минимальное количество минут он должен потратить на дорогу, чтобы сделать все дела и после этого прийти к Насте. Дома \(a_1, a_2, \dots, a_k\) он может посетить в любом порядке. Любые Дома он может посещать многократно (если захочет).
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите единственное число — минимальное количество минут, необходимых Владу на дорогу, чтобы сделать все дела и прийти к Насте.
Примечание
Дерево и оптимальный путь для первого теста:
\(1 \rightarrow 2 \rightarrow 1 \rightarrow 3\) Дерево и оптимальный путь для второго теста:
\(3 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 5 \rightarrow 6 \rightarrow 5\) Дерево и оптимальный путь для третьего теста:
\(3 \rightarrow 5 \rightarrow 2\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1
1 3
2
1 3
1 2
6 4
3 5
1 6 2 1
1 3
3 4
3 5
5 6
5 2
6 2
3 2
5 3
1 3
3 4
3 5
5 6
5 2
|
3
7
2
|