Chef's college is starting next week. There are $S$ subjects in total, and he needs to choose $K$ of them to attend each day, to fulfill the required number of credits to pass the semester. There are $N + 1$ buildings. His hostel is in building number $0$. Subject $i$ is taught in building $A_{i}$. After each subject, there is a break, during which he goes back to his hostel. There are $M$ bidirectional paths of length $1$ which connects building $u$ to building $v$. Find the minimum possible total distance Chef needs to travel each day if he chooses his subjects wisely.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contain $M + 2$ lines of input.
First line will contain $4$ space separated integers $N$, $M$, $S$, $K$, number of buildings other than hostel building, number of edges, total number of subjects taught, number of subjects required to pass the semester.
Next $M$ lines have $2$ space separated integers $u$, $v$ representing the path connecting buildings $u$ and $v$.
Next line has $S$ space separated integers $A_{1}, A_{2}, \ldots A_{S}$ representing the building in which $i^{th}$ subject is taught.

------ Output: ------
For each testcase, output in a single line answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 3$
$1 ≤ N, S ≤ 10^{5}$
$1 ≤ M ≤ 2*10^{5}$
$1 ≤ K ≤ S$
$1 ≤ A_{i} ≤ N$
$0 ≤ u, v ≤ N$

Its guaranteed that the graph is connected and has no self loops.

----- Sample Input 1 ------ 
3

2 3 2 2

0 1

1 2

2 0

1 2

2 2 2 2

0 1

1 2

1 2

6 7 5 3

0 1

0 2

0 4

1 3

1 4

2 5

2 6

1 2 3 5 6
----- Sample Output 1 ------ 
4

6

8
----- explanation 1 ------ 
TestCase 1: First Chef attends the subject in the building $2$ and he travels $1$ units to go there and $1$ units to come back during the break to the hostel.

Second subject he attends in the building $1$ and he travels $1$ unit to go there and $1$ unit to come back during the break to the hostel.

In total the total minimum distance to be travelled is $2 + 2  = 4$ units. 

TestCase 2: First Chef attends the subject in the building $2$ and he travels $2$ units to go there and $2$ units to come back during the break to the hostel.

Second subject he attends in the building $1$ and he travels $1$ unit to go there and $1$ unit to come back during the break to the hostel.

In total the total minimum distance to be travelled is $4 + 2  = 6$ units. 

TestCase 3: First Chef attends the subject in the building $3$ and he travels $2$ units to go there and $2$ units to come back during the break to the hostel.

Second subject he attends in the building $1$ and he travels $1$ unit to go there and $1$ unit to come back during the break to the hostel.

Final subject he attends in the building $2$ and he travels $1$ unit to go there and $1$ unit to come back during the break to the hostel.

In total the total minimum distance to be travelled is $4 + 2 + 2  = 8$ units.

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Graph algorithms

Graph traversal

Shortest paths


Solutions:
from collections import deque

def BFS(bldg, s):
	queue = deque()
	queue.append(s)
	cost = [-1 for i in range(n + 1)]
	cost[s] = 0
	while queue:
		s = queue.popleft()
		for i in bldg[s]:
			if cost[i] == -1:
				queue.append(i)
				cost[i] = cost[s] + 1
	return cost
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	buildings = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		buildings[u] += [v]
		buildings[v] += [u]
	sub = list(map(int, input().split()))
	costa = BFS(buildings, 0)
	for i in range(s):
		sub[i] = costa[sub[i]]
	sub.sort()
	print(2 * sum(sub[:k]))


from collections import deque

def bfs(ans_ll, v):
	Q = deque()
	dist = [-1 for i in range(n + 1)]
	dist[v] = 0
	Q.append(v)
	while Q:
		temp = Q.popleft()
		for i in ans_ll[temp]:
			if dist[i] == -1:
				Q.append(i)
				dist[i] = dist[temp] + 1
	return dist
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	ans_ll = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		ans_ll[u].append(v)
		ans_ll[v].append(u)
	temp_arr = list(map(int, input().split()))
	dist = bfs(ans_ll, 0)
	for i in range(len(temp_arr)):
		temp_arr[i] = dist[temp_arr[i]]
	temp_arr.sort()
	print(2 * sum(temp_arr[:k]))


from collections import deque
for i in range(int(input())):
	(n, m, s, k) = [int(x) for x in input().split()]
	vert = [[] for _ in range(n + 1)]
	dist = [-1 for i in range(n + 1)]
	for i in range(m):
		(u, v) = [int(x) for x in input().split()]
		vert[u].append(v)
		vert[v].append(u)
	build = [int(x) for x in input().split()]
	l = []
	q = deque()
	q.append(0)
	dist[0] = 0
	while q:
		u = q.popleft()
		for i in vert[u]:
			if dist[i] == -1:
				q.append(i)
				dist[i] = dist[u] + 1
	for i in build:
		l.append(dist[i])
	l.sort()
	print(2 * sum(l[:k]))


def minDistance(buildingCounter, requiredSubjects, createGraph):
	s = [(0, 0)]
	result = 0
	visited = set()
	while len(s) > 0:
		p = s.pop(0)
		if p[0] in visited:
			continue
		if p[0] in buildingCounter:
			x = min(buildingCounter[p[0]], requiredSubjects)
			result += x * p[1] * 2
			requiredSubjects -= x
		if requiredSubjects == 0:
			break
		visited.add(p[0])
		if p[0] in createGraph:
			for i in createGraph[p[0]]:
				s.append((i, p[1] + 1))
	return result
testCases = int(input())
for i in range(testCases):
	createGraph = {}
	(noOfBuildings, edges, noOfSubjects, requiredSubjects) = map(int, input().split())
	for i in range(edges):
		(buildingA, buildingB) = map(int, input().split())
		if buildingA not in createGraph:
			createGraph[buildingA] = [buildingB]
		else:
			createGraph[buildingA].append(buildingB)
		if buildingB not in createGraph:
			createGraph[buildingB] = [buildingA]
		else:
			createGraph[buildingB].append(buildingA)
	subjectTaughtAt = list(map(int, input().split()))
	buildingCounter = {}
	for i in subjectTaughtAt:
		if i not in buildingCounter:
			buildingCounter[i] = 1
		else:
			buildingCounter[i] += 1
	print(minDistance(buildingCounter, requiredSubjects, createGraph))


def bfs(n, g):
	q = []
	q.append([0, 0])
	dist = [0 for i in range(n + 1)]
	vis = {0}
	while q:
		(curr, mdist) = q.pop(0)
		dist[curr] = mdist
		for child in g[curr]:
			if not child in vis:
				vis.add(child)
				q.append([child, mdist + 1])
	return dist
ans = []
t = int(input())
for _ in range(t):
	(n, m, s, k) = map(int, input().split())
	g = {i: [] for i in range(n + 1)}
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	a = list(map(int, input().split()))
	dist = bfs(n, g)
	final_dist = [dist[i] for i in a]
	if s == k:
		ans.append(2 * sum(final_dist))
		continue
	final_dist.sort()
	ans.append(2 * sum(final_dist[:k]))
for i in ans:
	print(i)


from collections import deque, defaultdict
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	graph = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	a = list(map(int, input().split()))
	level = [0] * (n + 1)
	vis = [False] * (n + 1)
	queue = deque()
	queue.append(0)
	level[0] = 0
	vis[0] = True
	while queue:
		x = queue.popleft()
		for i in graph[x]:
			if not vis[i]:
				vis[i] = True
				level[i] = level[x] + 1
				queue.append(i)
	dist = []
	for i in a:
		dist.append(level[i])
	dist.sort()
	print(sum(dist[:k]) * 2)


from collections import defaultdict
for i in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	d = defaultdict(list)
	for j in range(m):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	sb = list(map(int, input().split()))
	sub = defaultdict(lambda : 0)
	visited = defaultdict(lambda : False)
	for j in sb:
		sub[j] += 1
	que = [0]
	visited[0] = True
	ans = 0
	level = 1
	while que:
		if k == 0:
			break
		lenofq = len(que)
		for l in range(lenofq):
			a = que.pop(0)
			for j in d[a]:
				if visited[j]:
					continue
				visited[j] = True
				que.append(j)
				if sub[j] > 0:
					req = min(k, sub[j])
					ans += 2 * level * req
					k -= req
				if k == 0:
					break
			if k == 0:
				break
		level += 1
	print(ans)


for t in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	adjlist = {i: [] for i in range(n + 1)}
	for i in range(m):
		(u, v) = map(int, input().split())
		adjlist[u].append(v)
		adjlist[v].append(u)
	s = list(map(int, input().split()))
	vis = [-1] * (n + 1)
	vis[0] = 0
	q = [0]
	while q != []:
		curr = q.pop(0)
		for i in adjlist[curr]:
			if vis[i] >= 0:
				continue
			else:
				vis[i] = vis[curr] + 1
				q.append(i)
	ans = []
	for i in range(len(s)):
		ans.append(vis[s[i]])
	ans.sort()
	print(sum(ans[:k]) * 2)


import queue

def bfs(graph, n):
	dis = [0] * n
	visited = [False] * n
	q = queue.Queue()
	q.put(0)
	visited[0] = True
	while not q.empty():
		x = q.get()
		for i in graph[x]:
			if not visited[i]:
				visited[i] = True
				dis[i] = dis[x] + 1
				q.put(i)
	return dis
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	dis = bfs(g, n + 1)
	l = []
	for i in map(int, input().split()):
		l.append(dis[i])
	l.sort()
	ans = 0
	for i in range(k):
		ans += l[i]
	print(2 * ans)


def graph(adj):
	queue = [0]
	visited = [0] * (N + 1)
	visited[0] = 1
	dist = [0] * (N + 1)
	while len(queue) > 0:
		u = queue[0]
		queue.pop(0)
		for child in adj[u]:
			if not visited[child]:
				visited[child] = 1
				dist[child] = dist[u] + 1
				queue.append(child)
	return dist

def addbiedge(g, a, b):
	if a not in g:
		g[a] = []
	if b not in g:
		g[b] = []
	g[a].append(b)
	g[b].append(a)

def solve(adj, builds, K):
	dists = graph(adj)
	mins = []
	for i in builds:
		mins.append(dists[i])
	mins.sort()
	ans = 0
	for i in range(K):
		ans += mins[i] * 2
	return ans
for _ in range(int(input())):
	[N, M, S, K] = [int(i) for i in input().rstrip().split(' ')]
	g = {}
	for _ in range(M):
		[a, b] = [int(i) for i in input().rstrip().split(' ')]
		addbiedge(g, a, b)
	builds = [int(i) for i in input().rstrip().split(' ')]
	print(solve(g, builds, K))


def bfs(arr, v):
	queue = []
	visited = [-1 for i in range(len(arr))]
	queue.append(v)
	visited[v] = 0
	while len(queue) > 0:
		x = queue.pop(0)
		for i in arr[x]:
			if visited[i] == -1:
				queue.append(i)
				visited[i] = visited[x] + 1
	return visited
t = int(input())
for _ in range(t):
	(N, M, S, K) = map(int, input().split())
	a = [[] for i in range(N + 1)]
	for _ in range(M):
		(u, v) = map(int, input().split())
		a[u].append(v)
		a[v].append(u)
	final = [int(i) for i in input().split()]
	res = bfs(a, 0)
	for i in range(len(final)):
		final[i] = res[final[i]]
	final.sort()
	print(2 * sum(final[:K]))


from collections import defaultdict

def dfs(adj, v):
	q = [v]
	dist = [-1 for i in range(n + 1)]
	dist[v] = 0
	while q:
		t = q.pop(0)
		for i in adj[t]:
			if dist[i] == -1:
				q.append(i)
				dist[i] = dist[t] + 1
	return dist
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	adj = defaultdict(list)
	for _ in range(m):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	build = list(map(int, input().split()))
	cost = dfs(adj, 0)
	for i in range(len(build)):
		build[i] = cost[build[i]]
	build.sort()
	print(2 * sum(build[:k]))


import sys
from collections import Counter
get_string = lambda : sys.stdin.readline().strip()
get_intmap = lambda : map(int, get_string().split())
for t in range(int(get_string())):
	(n, m, s, k) = get_intmap()
	adj = [[] for i in range(n + 1)]
	for ind in range(m):
		(a, b) = get_intmap()
		adj[a].append(b)
		adj[b].append(a)
	ls = list(get_intmap())
	ss = set(ls)
	frontier = [0]
	used = [0] * (n + 1)
	used[0] = 1
	nxt = []
	ldistance = [1000 * n] * (n + 1)
	distance = 0
	while len(frontier) > 0:
		distance += 1
		for u in frontier:
			for v in adj[u]:
				if not used[v]:
					used[v] = 1
					nxt.append(v)
					ldistance[v] = distance
		frontier = nxt
		nxt = []
	valid_distances = [ldistance[i] for i in ls]
	valid_distances.sort()
	print(2 * sum(valid_distances[:k]))


from collections import defaultdict
import heapq

def addEdge(u, v, weight):
	graph[u].append([v, weight])
	graph[v].append([u, weight])

def minDistance(graph, src):
	distances = defaultdict(lambda : float('inf'))
	distances[src] = 0
	pq = [(0, src)]
	heapq.heapify(pq)
	while pq:
		(currDis, currVer) = heapq.heappop(pq)
		if currDis > distances[currVer]:
			continue
		for (nbr, weight) in graph[currVer]:
			dist = currDis + weight
			if dist < distances[nbr]:
				distances[nbr] = dist
				heapq.heappush(pq, (dist, nbr))
	return distances
t = int(input())
while t:
	t -= 1
	(n, m, s, k) = list(map(int, input().strip().split()))
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = list(map(int, input().split()))
		addEdge(u, v, 1)
	k_arr = list(map(int, input().split()))
	distances = minDistance(graph, 0)
	ans = 0
	dist = []
	for i in k_arr:
		dist.append(distances[i])
	dist = sorted(dist)
	for i in range(k):
		ans += dist[i]
	print(ans * 2)


from collections import deque
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def bfs(p):
	q = deque([[p, 0]])
	v = [False] * (n + 1)
	v[0] = True
	while len(q):
		for i in child[q[0][0]]:
			if not v[i]:
				v[i] = True
				ans[i] = min(ans[i], q[0][-1] + 1)
				q.append([i, q[0][-1] + 1])
		q.popleft()
for T in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	child = [[] for i in range(m + 1)]
	for i in range(m):
		(u1, u2) = map(int, input().split())
		child[u1].append(u2)
		child[u2].append(u1)
	a = list(map(int, input().split()))
	c = [0] * (n + 1)
	for i in a:
		c[i] += 1
	ans = [10000000000.0] * (n + 1)
	bfs(0)
	ca = [0] * (n + 1)
	for i in range(n + 1):
		if ans[i] != 10000000000.0:
			ca[ans[i]] += c[i]
	answer = 0
	for i in range(n + 1):
		answer += min(ca[i], k) * (2 * i)
		k -= min(ca[i], k)
		if k == 0:
			break
	print(answer)


from collections import defaultdict, deque

def sol(n, m, s, k, dic):
	visited = [-1] * (n + 1)
	visited[0] = 0
	queue = deque()
	queue.append(0)
	while queue:
		u = queue.popleft()
		for v in dic[u]:
			if visited[v] == -1:
				queue.append(v)
				visited[v] = visited[u] + 1
	return visited
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	dic = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		dic[u].append(v)
		dic[v].append(u)
	subj = list(map(int, input().split()))
	dist = sol(n, m, s, k, dic)
	for i in range(len(subj)):
		subj[i] = dist[subj[i]]
	subj.sort()
	print(sum(subj[:k]) * 2)


from collections import deque

def bfs(i, a):
	paths = [-1 for i in range(n + 1)]
	q = deque()
	q.append(i)
	paths[i] = 0
	while q:
		temp = q[0]
		q.popleft()
		for j in a[temp]:
			if paths[j] == -1:
				paths[j] = paths[temp] + 1
				q.append(j)
	return paths
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	a = [[] for j in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		a[u].append(v)
		a[v].append(u)
	S = list(map(int, input().split()))
	paths = bfs(0, a)
	for i in range(len(S)):
		S[i] = paths[S[i]]
	S.sort()
	print(2 * sum(S[:k]))


from collections import defaultdict, deque

def BFS(graph, n, dist):
	visited = [False] * (n + 1)
	visited[0] = True
	queue = deque()
	dist[0] = 0
	queue.append(0)
	while queue:
		s = queue.popleft()
		for i in graph[s]:
			if visited[i] == False:
				queue.append(i)
				visited[i] = True
				if dist[i] == -1:
					dist[i] = dist[s] + 1
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	graph = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	cl = list(map(int, input().split()))
	dist = [-1] * (n + 1)
	BFS(graph, n, dist)
	for i in range(len(cl)):
		cl[i] = dist[cl[i]]
	cl.sort()
	print(2 * sum(cl[:k]))


def bfs(d, i, g, k):
	s = [(i, 0)]
	res = 0
	visited = set()
	while len(s) > 0:
		p = s.pop(0)
		if p[0] in visited:
			continue
		if p[0] in g:
			x = min(g[p[0]], k)
			res += x * p[1] * 2
			k -= x
		if k == 0:
			break
		visited.add(p[0])
		if p[0] in d:
			for i in d[p[0]]:
				s.append((i, p[1] + 1))
	return res
for _ in range(int(input())):
	(N, M, S, K) = map(int, input().split())
	d = {}
	for i in range(M):
		(u, v) = map(int, input().split())
		if u not in d:
			d[u] = [v]
		else:
			d[u].append(v)
		if v not in d:
			d[v] = [u]
		else:
			d[v].append(u)
	g = {}
	arr = list(map(int, input().split()))
	for i in arr:
		if i not in g:
			g[i] = 1
		else:
			g[i] += 1
	a = bfs(d, 0, g, K)
	print(a)


def dfs(d, st, bud, k):
	s = [(st, 0)]
	v = set()
	res = 0
	while len(s):
		p = s.pop(0)
		if p[0] in v:
			continue
		if bud[p[0]] > 0:
			if bud[p[0]] > k:
				res += p[1] * k
				k = 0
			else:
				res += p[1] * bud[p[0]]
				k -= bud[p[0]]
		if k == 0:
			break
		v.add(p[0])
		for i in d[p[0]]:
			s.append((i, p[1] + 1))
	return res * 2

def main():
	(n, m, s, k) = map(int, input().split())
	d = {}
	for i in range(m):
		(u, v) = map(int, input().split())
		if u in d:
			d[u].append(v)
		else:
			d[u] = [v]
		if v in d:
			d[v].append(u)
		else:
			d[v] = [u]
	bud = {}
	for i in range(n + 1):
		bud[i] = 0
	sub = list(map(int, input().split()))
	for i in range(s):
		bud[sub[i]] += 1
	print(dfs(d, 0, bud, k))
for _ in range(int(input())):
	main()


import math
import queue

def pl(graph, V, x):
	level = [0] * V
	marked = [False] * V
	que = queue.Queue()
	que.put(x)
	level[x] = 0
	marked[x] = True
	while not que.empty():
		x = que.get()
		for i in graph[x]:
			b = i
			if not marked[b]:
				que.put(b)
				level[b] = level[x] + 1
				marked[b] = True
	return level
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	graph = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	lev = pl(graph, n + 1, 0)
	ans = 0
	l = []
	for i in map(int, input().split()):
		l.append(lev[i])
	l.sort()
	for i in range(k):
		ans += 2 * l[i]
	print(ans)


from collections import defaultdict as dd
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m, s, k) = map(int, input().split())
	grp = dd(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		grp[u].append(v)
		grp[v].append(u)
	su = list(map(int, input().split()))
	dis = [0 for i in range(n + 1)]
	vis = [0 for i in range(n + 1)]
	q = [0]
	d = 0
	while q:
		sz = len(q)
		for i in range(sz):
			t = q.pop(0)
			vis[t] = 1
			dis[t] = d
			for j in grp[t]:
				if not vis[j]:
					q.append(j)
					vis[j] = 1
		d += 1
	res = []
	for i in range(s):
		res.append(dis[su[i]])
	ans = 0
	res = sorted(res)
	for i in range(k):
		ans += res[i]
	print(2 * ans)


for _ in range(int(input())):
	(n, m, st, k) = list(map(int, input().split()))
	a = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		a[x].append(y)
		a[y].append(x)
	b = list(map(int, input().split()))
	s = [[0, 0]]
	t = 1
	vis = [0 for i in range(n + 1)]
	d = {}
	vis[0] = 1
	while t != 0:
		x = s[0]
		s.pop(0)
		t -= 1
		for i in a[x[0]]:
			if vis[i] != 1:
				s.append([i, x[1] + 1])
				vis[i] = 1
				d[i] = x[1] + 1
				t += 1
	z = []
	for i in range(st):
		z.append(2 * d[b[i]])
	z.sort()
	ans = 0
	for i in range(k):
		ans += z[i]
	print(ans)


from collections import deque
for _ in range(int(input())):
	(n, m, s, k) = list(map(int, input().split()))
	gp = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		gp[u].append(v)
		gp[v].append(u)
	a = list(map(int, input().split()))
	q = []
	q.append(0)
	vis = [0] * (n + 1)
	level = [0] * (n + 1)
	vis[0] = 1
	while len(q) != 0:
		s = q.pop(0)
		for i in gp[s]:
			if vis[i] == 0:
				level[i] = level[s] + 1
				vis[i] = 1
				q.append(i)
	sub = []
	for i in range(len(a)):
		sub.append(level[a[i]])
	sub.sort()
	ans = 0
	for i in range(k):
		ans += sub[i]
	print(2 * ans)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt
import bisect
import sys
import copy

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
from itertools import permutations
for _ in range(int(input())):
	(n, m, s, k) = get_ints()
	d = defaultdict(list)
	for i in range(m):
		(x, y) = get_ints()
		d[x].append(y)
		d[y].append(x)
	s = get_array()
	vis = [False] * (n + 1)
	q = []
	q.append(0)
	vis[0] = True
	dist = [0] * (n + 1)
	while len(q) != 0:
		ele = q.pop(0)
		for x in d[ele]:
			if vis[x] == False:
				q.append(x)
				vis[x] = True
				dist[x] = dist[ele] + 1
	ans = []
	for i in range(len(s)):
		ans.append(dist[s[i]])
	ans.sort()
	fi = 0
	for i in range(k):
		fi += ans[i]
	print(2 * fi)