Treeland is a country in which there are n towns connected by n - 1 two-way road such that it's possible to get from any town to any other town. 

In Treeland there are 2k universities which are located in different towns. 

Recently, the president signed the decree to connect universities by high-speed network.The Ministry of Education understood the decree in its own way and decided that it was enough to connect each university with another one by using a cable. Formally, the decree will be done! 

To have the maximum sum in the budget, the Ministry decided to divide universities into pairs so that the total length of the required cable will be maximum. In other words, the total distance between universities in k pairs should be as large as possible. 

Help the Ministry to find the maximum total distance. Of course, each university should be present in only one pair. Consider that all roads have the same length which is equal to 1. 


-----Input-----

The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n / 2) — the number of towns in Treeland and the number of university pairs. Consider that towns are numbered from 1 to n. 

The second line contains 2k distinct integers u_1, u_2, ..., u_2k (1 ≤ u_{i} ≤ n) — indices of towns in which universities are located. 

The next n - 1 line contains the description of roads. Each line contains the pair of integers x_{j} and y_{j} (1 ≤ x_{j}, y_{j} ≤ n), which means that the j-th road connects towns x_{j} and y_{j}. All of them are two-way roads. You can move from any town to any other using only these roads. 


-----Output-----

Print the maximum possible sum of distances in the division of universities into k pairs.


-----Examples-----
Input
7 2
1 5 6 2
1 3
3 2
4 5
3 7
4 3
4 6

Output
6

Input
9 3
3 2 1 6 5 9
8 9
3 2
2 7
3 4
7 6
4 5
2 1
2 8

Output
9



-----Note-----

The figure below shows one of possible division into pairs in the first test. If you connect universities number 1 and 6 (marked in red) and universities number 2 and 5 (marked in blue) by using the cable, the total distance will equal 6 which will be the maximum sum in this example. 

 [Image]

Difficulty: competition

Starter code:

Solutions:
def bfs(source):
    q = [0] * (n + 1);
    fa = [-1] * n
    l, r = [1] * 2
    fa[source] = source
    q[1] = source
    while l <= r:
        x = q[l]
        l += 1
        for y in e[x]:
            if  fa[y] == -1:
                fa[y] = x
                r += 1
                q[r] = y
    i = r;
    while i >= 1:
        x = q[i]
        for y in e[x]:
            if fa[y] == x:
                sum[x] += sum[y]
                dp[x] += dp[y] + min(sum[y], m - sum[y])
        i -= 1

n, m =[int(x) for x in input().split()]
m <<= 1
t = [int(x) for x in input().split()]
e = [list() for i in range(n)]
sum = [0] * n
dp = [0] * n
#print(len(e), e)
for i in range(n - 1):
    x, y = [int(a) for a in input().split()]
    e[x - 1].append(y - 1)
    e[y - 1].append(x - 1)
for x in t:
    sum[x - 1] = 1
bfs(0)
print(dp[0])

def main():
    n, k = list(map(int, input().split()))
    s = [0] * n
    for i in map(int, input().split()):
        s[i - 1] = 1
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = (int(s) - 1 for s in input().split())
        e[x].append(y)
        e[y].append(x)
    q, fa = [0], [-1] * n
    fa[0] = 0
    for i in range(n):
        x = q[i]
        for y in e[x]:
            if fa[y] == -1:
                fa[y] = x
                q.append(y)
    dp, k2 = [0] * n, k * 2
    for x in reversed(q):
        for y in e[x]:
            if fa[y] == x:
                i = s[y]
                s[x] += i
                dp[x] += dp[y] + (k2 - i if i > k else i)
    print(dp[0])


def __starting_point():
    main()

__starting_point()

n, k = list(map(int, input().split()))
s = [0] * n
for i in map(int, input().split()):
    s[i - 1] = 1
e = [[] for _ in range(n)]
for _ in range(n - 1):
    x, y = (int(s) - 1 for s in input().split())
    e[x].append(y)
    e[y].append(x)
q, fa = [0], [-1] * n
fa[0] = 0
for i in range(n):
    x = q[i]
    for y in e[x]:
        if fa[y] == -1:
            fa[y] = x
            q.append(y)
dp, k2 = [0] * n, k * 2
for x in reversed(q):
    for y in e[x]:
        if fa[y] == x:
            i = s[y]
            s[x] += i
            dp[x] += dp[y] + (k2 - i if i > k else i)
print(dp[0])


def bfs(source):

    q = [0] * (n + 1);

    fa = [-1] * n

    l, r = [1] * 2

    fa[source] = source

    q[1] = source

    while l <= r:

        x = q[l]

        l += 1

        for y in e[x]:

            if  fa[y] == -1:

                fa[y] = x

                r += 1

                q[r] = y

    i = r;

    while i >= 1:

        x = q[i]

        for y in e[x]:

            if fa[y] == x:

                sum[x] += sum[y]

                dp[x] += dp[y] + min(sum[y], m - sum[y])

        i -= 1



n, m =[int(x) for x in input().split()]

m <<= 1

t = [int(x) for x in input().split()]

e = [list() for i in range(n)]

sum = [0] * n

dp = [0] * n

#print(len(e), e)

for i in range(n - 1):

    x, y = [int(a) for a in input().split()]

    e[x - 1].append(y - 1)

    e[y - 1].append(x - 1)

for x in t:

    sum[x - 1] = 1

bfs(0)

print(dp[0])



# Made By Mostafa_Khaled


from collections import defaultdict
def put(): return map(int, input().split())

def dfs():
    s = [(1,0)]
    ans = 0
    vis = [0]*(n+1)
    while s:
        i,p = s.pop()
        if vis[i]==0:
            vis[i]=1
            s.append((i,p))
            for j in tree[i]:
                if j!=p:
                    s.append((j,i))
        elif vis[i]==1:
            vis[i]=2
            for j in tree[i]:
                if j != p:
                    mark[i]+= mark[j]
            ans += min(mark[i], 2*k - mark[i])
    print(ans)
        




n,k = put()
l = list(put())

edge = defaultdict()
tree = [[] for i in range(n+1)]
mark = [0]*(n+1)
for i in l:
    mark[i]=1
for _ in range(n-1):
    x,y = put()
    tree[x].append(y)
    tree[y].append(x)
dfs()

from collections import defaultdict
from sys import stdin

def put(): return map(int, stdin.readline().split())

def dfs():
    s = [(1,0)]
    ans = 0
    vis = [0]*(n+1)
    while s:
        i,p = s.pop()
        if vis[i]==0:
            vis[i]=1
            s.append((i,p))
            for j in tree[i]:
                if j!=p:
                    s.append((j,i))
        elif vis[i]==1:
            vis[i]=2
            for j in tree[i]:
                if j != p:
                    mark[i]+= mark[j]
            ans += min(mark[i], 2*k - mark[i])
    print(ans)
        




n,k = put()
l = list(put())

edge = defaultdict()
tree = [[] for i in range(n+1)]
mark = [0]*(n+1)
for i in l:
    mark[i]=1
for _ in range(n-1):
    x,y = put()
    tree[x].append(y)
    tree[y].append(x)
dfs()

def parser():
    return [int(x) for x in input().split(" ")]

def DFS():
    visited[0]=True
    stack=[]
    intruduction_order=[]
    stack.append(0)
    while len(stack)>0:
        v=stack.pop()
        for u in adjacents_list[v]:
            if not visited[u]:
                pi[u]=v
                visited[u]=True
                if university_in_city[u]:
                    count_universities_subtree[u]+=1
                stack.append(u)
                intruduction_order.append(u)
    for v in intruduction_order[::-1]:
        count_universities_subtree[pi[v]]+=count_universities_subtree[v]


n,k=parser()
visited=[False for x in range(n)]
pi=[0 for x in range(n)]
count_universities_subtree=[0 for x in range(n)]
university_in_city=[False for x in range(n)]

cities_universities=parser()
for i in range(2*k):
    university_in_city[cities_universities[i]-1]=True

adjacents_list=[[] for x in range(n)]
for i in range(n-1):
    edge=parser()
    adjacents_list[edge[0]-1].append(edge[1]-1)
    adjacents_list[edge[1]-1].append(edge[0]-1)

DFS()

total=0

for i in range(1,n):
    total+=min(count_universities_subtree[i],2*k-count_universities_subtree[i])

print(total)

#parsea una línea
def parser():
    return [int(x) for x in input().split()]

#Método usado para contar las universidades en cada subárbol
def DFS():
    visited[0]=True
    stack=[]
    introduction_order=[]
    stack.append(0)
    while len(stack)>0:
        v=stack.pop()
        for u in adjacents_list[v]:
            if not visited[u]:
                pi[u]=v
                visited[u]=True
                if university_in_city[u]:
                    count_universities_subtree[u]+=1
                stack.append(u)
                introduction_order.append(u)
    
    #Recorriendo para saber la cantidad de universidades que hay en el subarbol de cada vertice
    for v in introduction_order[::-1]:
        count_universities_subtree[pi[v]]+=count_universities_subtree[v]

#Recibiendo los valores de n y k
n,k=parser()
#visitados
visited=[False for x in range(n)]
#padres
pi=[0 for x in range(n)]
#universidades en el subarbol
count_universities_subtree=[0 for x in range(n)]
#universidad en la ciudad
university_in_city=[False for x in range(n)]

#Recibiendo las ciudades que tienen universidades
cities_universities=parser()
for i in cities_universities:
    university_in_city[i-1]=True

#Armando el árbol que representa a Treeland
adjacents_list=[[] for x in range(n)]
for i in range(n-1):
    #Leyendo una arista
    edge=parser()
    adjacents_list[edge[0]-1].append(edge[1]-1)
    adjacents_list[edge[1]-1].append(edge[0]-1)

DFS()

#Calculando el total
total=0
for i in range(1,n):
    total+=min(count_universities_subtree[i],2*k-count_universities_subtree[i])

#Imprimiendo el resultado
print(total)