Vlad and Nastya live in a city consisting of $n$ houses and $n-1$ road. From each house, you can get to the other by moving only along the roads. That is, the city is a tree.

Vlad lives in a house with index $x$, and Nastya lives in a house with index $y$. Vlad decided to visit Nastya. However, he remembered that he had postponed for later $k$ things that he has to do before coming to Nastya. To do the $i$-th thing, he needs to come to the $a_i$-th house, things can be done in any order. In $1$ minute, he can walk from one house to another if they are connected by a road.

Vlad does not really like walking, so he is interested what is the minimum number of minutes he has to spend on the road to do all things and then come to Nastya. Houses $a_1, a_2, \dots, a_k$ he can visit in any order. He can visit any house multiple times (if he wants).


-----Input-----

The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of input test cases. There is an empty line before each test case.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2\cdot 10^5$) — the number of houses and things, respectively.

The second line of each test case contains two integers $x$ and $y$ ($1 \le x, y \le n$) — indices of the houses where Vlad and Nastya live, respectively.

The third line of each test case contains $k$ integers $a_1, a_2, \dots, a_k$ ($1 \le a_i \le n$) — indices of houses Vlad need to come to do things.

The following $n-1$ lines contain description of city, each line contains two integers $v_j$ and $u_j$ ($1 \le u_j, v_j \le n$) — indices of houses connected by road $j$.

It is guaranteed that the sum of $n$ for all cases does not exceed $2\cdot10^5$.


-----Output-----

Output $t$ lines, each of which contains the answer to the corresponding test case of input. As an answer output single integer — the minimum number of minutes Vlad needs on the road to do all the things and come to Nastya.


-----Examples-----

Input
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
Output
3
7
2


-----Note-----

Tree and best path for the first test case:

$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$

Tree and best path for the second test case:

$3 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 5 \rightarrow 6 \rightarrow 5$

Tree and best path for the third test case:

$3 \rightarrow 5 \rightarrow 2$

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal

Greedy algorithms


Solutions:
def solve(n, k, x, y, a, graph):
	a.add(x)
	a.add(y)
	stack = [(x, 0)]
	parent = (n + 1) * [-1]
	y_height = None
	while stack:
		(node, height) = stack.pop()
		if node == y:
			y_height = height
		for child in graph[node]:
			if child != parent[node]:
				parent[child] = node
				stack.append((child, height + 1))
	lst = list(a)
	edge_ct = 0
	for node in lst:
		if node != x and parent[node] not in a:
			a.add(parent[node])
			lst.append(parent[node])
		if node != x:
			edge_ct += 2
	return edge_ct - y_height
t = int(input())
for case in range(t):
	input()
	(n, k) = map(int, input().split())
	(x, y) = map(int, input().split())
	a = set(map(int, input().split()))
	graph = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	print(solve(n, k, x, y, a, graph))


import sys
input = sys.stdin.readline
import math
sys.setrecursionlimit(200020)
import threading
threading.stack_size(2 ** 27)

def main():
	for _ in range(int(input())):
		line = input()
		(N, K) = map(int, input().split())
		(X, Y) = map(int, input().split())
		Nodes = set(map(int, input().split()))
		Nodes.add(X)
		Nodes.add(Y)
		Graph = []
		for i in range(N + 1):
			Graph.append([])
		for i in range(N - 1):
			(A, B) = map(int, input().split())
			Graph[A].append(B)
			Graph[B].append(A)
		visited = [False] * (N + 1)
		dist = [10 ** 6] * (N + 1)
		total = [0]

		def DFS(node):
			visited[node] = True
			found = False
			for nie in Graph[node]:
				if not visited[nie]:
					dist[nie] = min(dist[nie], dist[node] + 1)
					good = DFS(nie)
					if good:
						total[0] = total[0] + 2
					found = found or good
			if node in Nodes:
				return True
			else:
				return found
		dist[X] = 0
		DFS(X)
		print(total[0] - dist[Y])
threading.Thread(target=main).start()


from collections import defaultdict, Counter

def ri():
	return int(input())

def rs():
	return input()

def rl():
	return list(map(int, input().split()))

def rls():
	return list(input().split())

def main():
	for test in range(ri()):
		rs()
		(n, k) = rl()
		(x, y) = rl()
		a = rl()
		g = defaultdict(list)
		for e in range(n - 1):
			(u, v) = rl()
			g[u].append(v)
			g[v].append(u)
		to_vis = set([x, y])
		for i in a:
			to_vis.add(i)
		st = [(x, 0)]
		to_y = None
		par = [-1] * (n + 1)
		while st:
			(cn, cd) = st.pop()
			if cn == y:
				to_y = cd
			for nn in g[cn]:
				if nn != par[cn]:
					par[nn] = cn
					st.append((nn, cd + 1))
		ls = list(to_vis)
		res = 0
		for cn in ls:
			if cn != x and par[cn] not in to_vis:
				to_vis.add(par[cn])
				ls.append(par[cn])
			if cn != x:
				res += 2
		print(res - to_y)
	pass
main()


import sys
input = sys.stdin.readline
import math
sys.setrecursionlimit(200020)
import threading
threading.stack_size(2 ** 27)

def main():
	for _ in range(int(input())):
		input()
		(n, k) = map(int, input().split())
		(x, y) = map(int, input().split())
		z = list(map(int, input().split()))
		g = [[] for i in range(n)]
		x -= 1
		y -= 1
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			g[a].append(b)
			g[b].append(a)
		a = [False] * n
		for i in z:
			a[i - 1] = True
		depth = [0] * n
		found = [False] * n

		def Dfs(v, p):
			if a[v] or y == v:
				found[v] = True
			for to in g[v]:
				if to == p:
					continue
				depth[to] = depth[v] + 1
				Dfs(to, v)
				if found[to]:
					found[v] = True
		Dfs(x, -1)
		ans = 0
		for i in range(n):
			if i != x and found[i]:
				ans += 2
		ans -= depth[y]
		print(ans)
threading.Thread(target=main).start()


t = int(input())
for case in range(t):
	input()
	(n, k) = list(map(int, input().split()))
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	things = list(map(int, input().split()))
	things = set([i - 1 for i in things])
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	pre = [-1] * n
	qu = [x]
	vis_node = set()
	vis_node.add(x)
	while qu:
		nq = []
		for i in qu:
			vis_node.add(i)
			for u in adj[i]:
				if u not in vis_node:
					nq.append(u)
					pre[u] = i
		qu = nq
	res = 0
	vis_node = set()
	vis_node.add(x)
	tmp = y
	while tmp not in vis_node:
		vis_node.add(tmp)
		tmp = pre[tmp]
		res += 1
	for i in things:
		tmp = i
		while tmp not in vis_node:
			vis_node.add(tmp)
			tmp = pre[tmp]
			res += 2
	print(res)


def solve(N, K, vlad, nast, to_do, g):
	to_do.add(vlad)
	to_do.add(nast)
	S = [(vlad, 0)]
	prnt = (N + 1) * [-1]
	time = None
	while S:
		(cur, t) = S.pop()
		if cur == nast:
			time = t
		for nxt in g[cur]:
			if nxt != prnt[cur]:
				prnt[nxt] = cur
				S.append((nxt, t + 1))
	hwss = list(to_do)
	edge_ct = 0
	for hws in hwss:
		if hws != vlad and prnt[hws] not in to_do:
			to_do.add(prnt[hws])
			hwss.append(prnt[hws])
		if hws != vlad:
			edge_ct += 2
	return edge_ct - time

def get_input():
	input()
	(N, K) = map(int, input().split())
	(vlad, nast) = map(lambda x: int(x) - 1, input().split())
	todo = set(map(lambda x: int(x) - 1, input().split()))
	g = [[] for _ in range(N)]
	for _ in range(N - 1):
		(frm, to) = map(lambda x: int(x) - 1, input().split())
		g[frm].append(to)
		g[to].append(frm)
	return (N, K, vlad, nast, todo, g)
for _ in range(int(input())):
	(N, K, vlad, nast, todo, g) = get_input()
	ans = solve(N, K, vlad, nast, todo, g)
	print(ans)


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	for _ in range(int(input())):
		input()
		(n, k) = map(int, input().split())
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		arr = list(map(int, input().split()))
		arr = set([el - 1 for el in arr])
		graph = [[] for _ in range(n)]
		for _ in range(n - 1):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			graph[a].append(b)
			graph[b].append(a)
		d = [[False, False] for _ in range(n)]

		def helper(node, par):
			if node in arr:
				d[node][0] = True
			if node == y:
				d[node][1] = True
			for nie in graph[node]:
				if nie != par:
					(a, b) = helper(nie, node)
					d[node][0] |= a
					d[node][1] |= b
			return (d[node][0], d[node][1])
		helper(x, -1)

		def dfs(node, par):
			temp = 0
			for nie in graph[node]:
				if nie != par:
					if not d[nie][0] and (not d[nie][1]):
						pass
					elif d[nie][1]:
						temp += 1 + dfs(nie, node)
					elif d[nie][0]:
						temp += 2 + dfs(nie, node)
			return temp
		print(dfs(x, -1))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()