Влад и Настя живут в городе, состоящем из $$$n$$$ домов и $$$n-1$$$ дороги. Из каждого дома можно добраться до другого передвигаясь только по дорогам. То есть город представляет собой дерево.
Влад живёт в доме с номером $$$x$$$, а Настя в доме с номером $$$y$$$. Влад решил пойти к Насте в гости. Однако он вспомнил, что отложил на потом $$$k$$$ дел, которые он должен сделать прежде чем прийти к Насте. Чтобы сделать $$$i$$$-е дело ему необходимо прийти в $$$a_i$$$-й дом, дела можно делать в любом порядке. За $$$1$$$ минуту он может пройти от одного дома до другого, если их соединяет дорога.
Влад не очень любит пешие прогулки, поэтому его интересует, какое минимальное количество минут он должен потратить на дорогу, чтобы сделать все дела и после этого прийти к Насте. Дома $$$a_1, a_2, \dots, a_k$$$ он может посетить в любом порядке. Любые Дома он может посещать многократно (если захочет).
В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Перед каждым набором входных данных в тесте содержится пустая строка.
Первая строка набора входных данных содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2\cdot 10^5$$$) — количество домов и дел соответственно.
Вторая строка набора входных данных содержит два числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$) — номера домов, в которых живут Влад и Настя, соответственно.
Третья строка набора входных данных содержит $$$k$$$ целых чисел $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_i \le n$$$) — номера домов, в которые нужно зайти по дороге.
Следующие $$$n-1$$$ строк содержат описание города, по два числа на строку $$$v_j$$$ и $$$u_j$$$ ($$$1 \le u_j, v_j \le n$$$) — номера домов, которые соединяет дорога $$$j$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2\cdot10^5$$$.
Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите единственное число — минимальное количество минут, необходимых Владу на дорогу, чтобы сделать все дела и прийти к Насте.
33 11 321 31 26 43 51 6 2 11 33 43 55 65 26 23 25 31 33 43 55 65 2
3 7 2
Дерево и оптимальный путь для первого теста:
$$$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$$$
| Codeforces Round 787 (Div. 3) |
|---|
| Закончено |
