Lavanya and Nikhil have K months of holidays ahead of them, and they want to go on exactly K road trips, one a month. They have a map of the various cities in the world with the roads that connect them. There are N cities, numbered from 1 to N. We say that you can reach city B from city A if there is a sequence of roads that starts from city A and ends at city B. Note that the roads are bidirectional. Hence, if you can reach city B from city A, you can also reach city A from city B. 
Lavanya first decides which city to start from. In the first month, they will start from that city, and they will visit every city that they can reach by road from that particular city, even if it means that they have to pass through cities that they have already visited previously. Then, at the beginning of the second month, Nikhil picks a city that they haven't visited till then. In the second month, they first fly to that city and visit all the cities that they can reach from that city by road. Then, in the third month, Lavanya identifies a city, and they fly there and visit all cities reachable from there by road. Then in the fourth month it is Nikhil's turn to choose an unvisited city to start a road trip, and they alternate like this. Note that the city that they fly to (that is, the city from where they start each month's road trip) is also considered as being visited.
Each city has some museums, and when they visit a city for the first time, Lavanya makes them visit each of the museums there. Lavanya loves going to museums, but Nikhil hates them. Lavanya always makes her decisions so that they visit the maximum number of museums possible that month, while Nikhil picks cities so that the number of museums visited that month is minimized.
Given a map of the roads, the number of museums in each city, and the number K, find the total number of museums that they will end up visiting at the end of K months. Print -1 if they will have visited all the cities before the beginning of the Kth month, and hence they will be left bored at home for some of the K months.

-----Input-----
- The first line contains a single integer, T, which is the number of testcases. The description of each testcase follows.
- The first line of each testcase contains three integers: N, M and K, which represents the number of cities, number of roads and the number of months.
- The ith of the next M lines contains two integers, ui and vi. This denotes that there is a direct road between city ui and city vi.
- The next line contains N integers, the ith of which represents the number of museums in city i.

-----Output-----
For each test case, if they can go on K road trips, output a single line containing a single integer which should be the total number of museums they visit in the K months. Output -1 if they can't go on K road trips.

-----Constraints-----
- 1 ≤ T ≤ 3
- 1 ≤ N ≤ 106
- 0 ≤ M ≤ 106
- 1 ≤ K ≤ 106
- 1 ≤ ui, vi ≤ N
- There is no road which goes from one city to itself. ie. ui ≠ vi.
- There is at most one direct road between a pair of cities.
- 0 ≤ Number of museums in each city ≤ 1000
- Sum of N over all testcases in a file will be ≤ 1.5 * 106

-----Subtasks-----
- Subtask 1 (11 points): M = 0
- Subtask 2 (21 points): Each city has at most two roads of which it is an end point. That is, for every i, there are at most two roads (u, v) in the input, such that u = i or v = i.
- Subtask 3 (68 points): Original constraints.

-----Example-----
Input:
3
10 10 3
1 3
3 5
5 1
1 6
6 2
5 6
2 5
7 10
4 7
10 9
20 0 15 20 25 30 30 150 35 20
10 10 2
1 3
3 5
5 1
1 6
6 2
5 6
2 5
7 10
4 7
10 9
20 0 15 20 25 30 30 150 35 20
10 10 5
1 3
3 5
5 1
1 6
6 2
5 6
2 5
7 10
4 7
10 9
20 0 15 20 25 30 30 150 35 20

Output:
345
240
-1

-----Explanation-----
Notice that in all the three testcases, everything is the same, except for the value of K. The following figure represents the road map in these testcases. Each node denotes a city, with a label of the form "n (m)", where n is the city number, between 1 and N, and m is the number of museums in this city.  For example, the node with label "5 (25)" represents city 5, which has 25 museums.

Testcase 1: Lavanya will first choose to fly to city 8. In the first month, they visit only that city, but they visit 150 museums.
Then in the second month, Nikhil could choose to fly to city 3, and they visit the cities 1, 2, 3, 5 and 6, and visit 20 + 0 + 15 + 25 + 30 = 90 museums that month. Note that Nikhil could have instead chosen to fly to city 1 or 2 or 5 or 6, and they would all result in the same scenario.
Then, Lavanya could choose city 7, and in the third month they will visit the cities 7, 4, 10 and 9. Note that Lavanya could have chosen to fly to city 4 or 10 or 9, and they would all result in the same scenario.
In total, they have visited 345 museums in the three months (which is in fact all the museums), and that is the answer.
Testcase 2: It is same as the previous testcase, but now they have only 2 months. So they visit only 150 + 90 = 240 museums in total.
Testcase 3: It is same as the previous testcase, but now they have 5 months of holidays. But sadly, they finish visiting all the cities within the first three months itself, and hence the answer is -1.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def merge(intervals, start, mid, end):
	al = mid - start + 1
	bl = end - mid
	A = intervals[start:mid + 1]
	B = intervals[mid + 1:end + 1]
	p = 0
	q = 0
	k = start
	while p < al and q < bl:
		if A[p] < B[q]:
			intervals[k] = A[p]
			k += 1
			p += 1
		else:
			intervals[k] = B[q]
			k += 1
			q += 1
	while p < al:
		intervals[k] = A[p]
		k += 1
		p += 1
	while q < bl:
		intervals[k] = B[q]
		k += 1
		q += 1

def mergesort(intervals, start, end):
	if start < end:
		mid = int((start + end) / 2)
		mergesort(intervals, start, mid)
		mergesort(intervals, mid + 1, end)
		merge(intervals, start, mid, end)
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	cities = [[0, []] for i in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		cities[a - 1][1].append(b - 1)
		cities[b - 1][1].append(a - 1)
	li = list(map(int, input().split()))

	def specialfunction():
		mergesort(li, 0, n - 1)
		if k > len(li):
			print(-1)
		else:
			sum = 0
			front = 0
			rear = len(li) - 1
			for i in range(k):
				if i % 2 == 0:
					sum += li[rear]
					rear -= 1
				else:
					sum += li[front]
					front += 1
			print(sum)
	if m == 0:
		specialfunction()
		continue
	for i in range(n):
		cities[i][0] = li[i]
	visited = [-1 for i in range(n)]
	count = 0
	museummonths = []

	def searchUnvisited():
		for i in range(n):
			if visited[i] == -1:
				return i
		return -1

	def bfs(ind, count):
		museumcount = 0
		queue = []
		queue.append(ind)
		visited[ind] = 1
		museumcount += cities[ind][0]
		count += 1
		front = 0
		rear = 0
		while front <= rear:
			noe = len(cities[ind][1])
			for i in range(noe):
				if visited[cities[ind][1][i]] == -1:
					queue.append(cities[ind][1][i])
					rear += 1
					count += 1
					museumcount += cities[cities[ind][1][i]][0]
					visited[cities[ind][1][i]] = 1
			front += 1
			try:
				ind = queue[front]
			except:
				break
		museummonths.append(museumcount)
		return count
	while count < n:
		for i in range(n):
			if visited[i] == -1:
				count = bfs(i, count)
	mergesort(museummonths, 0, len(museummonths) - 1)
	if k > len(museummonths):
		print(-1)
	else:
		sum = 0
		front = 0
		rear = len(museummonths) - 1
		for i in range(k):
			if i % 2 == 0:
				sum += museummonths[rear]
				rear -= 1
			else:
				sum += museummonths[front]
				front += 1
		print(sum)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	graph = defaultdict(lambda : [])
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	museums = list(map(int, input().split()))
	visited = [0] * n
	lista = []
	for i in range(n):
		if visited[i] == 0:
			visited[i] = 1
			stack = [i]
			counter = museums[i]
			while len(stack) > 0:
				u = stack.pop()
				for v in graph[u]:
					if visited[v] == 0:
						counter += museums[v]
						stack.append(v)
						visited[v] = 1
			lista.append(counter)
	if len(lista) < k:
		print(-1)
	else:
		lista.sort()
		counter = 0
		id0 = 0
		id1 = len(lista) - 1
		for i in range(k):
			if i % 2 == 0:
				counter += lista[id1]
				id1 -= 1
			else:
				counter += lista[id0]
				id0 += 1
		print(counter)


def dfs(i):
	visited[i] = True
	musuemsPossible = musuems[i]
	for j in neighbours[i]:
		if not visited[j]:
			musuemsPossible += dfs(j)
	return musuemsPossible
t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().split()))
	neighbours = []
	visited = []
	for i in range(n):
		visited.append(False)
		neighbours.append([])
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		neighbours[a - 1].append(b - 1)
		neighbours[b - 1].append(a - 1)
	musuems = [int(x) for x in input().split()]
	mususeumsBigNode = []
	for i in range(n):
		if not visited[i]:
			mususeumsBigNode.append(dfs(i))
	if len(mususeumsBigNode) < k:
		print(-1)
	else:
		mususeumsBigNode.sort()
		if k % 2 == 0:
			k //= 2
			ans = sum(mususeumsBigNode[:k] + mususeumsBigNode[-k:])
		else:
			k //= 2
			ans = mususeumsBigNode[-k - 1]
			if k > 0:
				ans += sum(mususeumsBigNode[:k] + mususeumsBigNode[-k:])
		print(ans)


for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	l = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		l[a].append(b)
		l[b].append(a)
	m_l = [-1] + list(map(int, input().split()))
	visited = [False for _ in range(n + 1)]
	sum_l = []
	for i in range(1, n + 1):
		if visited[i] == False:
			summa = 0
			q = [i]
			while len(q) != 0:
				v = q[-1]
				del q[-1]
				if visited[v]:
					continue
				visited[v] = True
				summa += m_l[v]
				for vv in l[v]:
					q.append(vv)
			sum_l.append(summa)
	if len(sum_l) < k:
		print(-1)
	else:
		sum_l.sort()
		if k % 2 == 0:
			k //= 2
			ans = sum(sum_l[:k] + sum_l[-k:])
		else:
			k //= 2
			ans = sum_l[-k - 1]
			if k > 0:
				ans += sum(sum_l[:k] + sum_l[-k:])
		print(ans)


import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 6)

class graph:

	def __init__(self, N):
		self.N = N
		self.adjacent_list = [[] for i in range(N)]

	def add_road(self, a, b):
		self.adjacent_list[a].append(b)
		self.adjacent_list[b].append(a)

	def DFS_iterate(self, con_list, n, visited):
		visited[n] = True
		con_list.append(n)
		for i in self.adjacent_list[n]:
			if visited[i] == False:
				con_list = self.DFS_iterate(con_list, i, visited)
		return con_list

	def connected_groups(self):
		visited = [False for i in range(N)]
		con_groups = []
		for n in range(N):
			if visited[n] == False:
				con_list = []
				con_groups.append(self.DFS_iterate(con_list, n, visited))
		return con_groups
T = int(input())
for x in range(T):
	(N, M, K) = list(map(int, input().split()))
	city_map = graph(N)
	for i in range(M):
		road = list(map(int, input().split()))
		city_map.add_road(road[0] - 1, road[1] - 1)
	museums_city = list(map(int, input().split()))
	con_groups = city_map.connected_groups()
	if len(con_groups) < K:
		print('-1')
	else:
		museums_groups = []
		for group in con_groups:
			museums_group = 0
			for city in group:
				museums_group += museums_city[city]
			museums_groups.append(museums_group)
		total_museums = 0
		museums_groups.sort(reverse=True)
		Ladki = 0
		Nikhil = len(museums_groups) - 1
		for j in range(K):
			if j % 2 == 0:
				total_museums += museums_groups[Ladki]
				Ladki += 1
			else:
				total_museums += museums_groups[Nikhil]
				Nikhil -= 1
		print(total_museums)


def bfs(visited, musium, count, roads, explore):
	visited[explore - 1] = True
	count[0] += musium[explore]
	for _ in roads[explore]:
		if not visited[_ - 1]:
			bfs(visited, musium, count, roads, _)
t = int(input())
while t > 0:
	(n, m, k) = list(map(int, input().split()))
	roads = {i: [] for i in range(1, n + 1)}
	visited = [False for _ in range(n)]
	for _ in range(m):
		(s, e) = list(map(int, input().split()))
		roads[s].append(e)
		roads[e].append(s)
	musium = []
	hashm = {}
	mp = list(map(int, input().split()))
	for i in enumerate(mp, 1):
		musium.append(i)
		hashm.update({i[0]: i[1]})
	musium.sort(key=lambda x: x[1])
	(count, lavany, end, begin) = ([0], True, n - 1, 0)
	while k > 0:
		if lavany:
			while visited[musium[end][0] - 1] and end > begin:
				end -= 1
			bfs(visited, hashm, count, roads, musium[end][0])
			end -= 1
		else:
			while visited[musium[begin][0] - 1] and end > begin:
				begin += 1
			bfs(visited, hashm, count, roads, musium[begin][0])
			begin += 1
		k -= 1
		lavany = not lavany
		if all(visited) and k > 0:
			print(-1)
			break
	else:
		print(count[0])
	t -= 1


t = int(input())
while t:
	t -= 1
	(n, m, k) = list(map(int, input().split()))
	g = []
	for i in range(1000001):
		g.append([])
	while m:
		m -= 1
		(x, y) = list(map(int, input().split()))
		g[x].append(y)
		g[y].append(x)
	a = [0] + list(map(int, input().split()))
	ans = []
	vis = [0] * 1000001
	for i in range(1, n + 1):
		if vis[i] == 0:
			vis[i] = 1
			val = a[i]
			bfsQ = [i]
			while bfsQ:
				x = bfsQ[0]
				del bfsQ[0]
				for y in g[x]:
					if vis[y] == 0:
						val += a[y]
						vis[y] = 1
						bfsQ.append(y)
			ans.append(val)
	ans = sorted(ans)
	if k > len(ans):
		print(-1)
	else:
		print(sum(ans[:k // 2]) + sum(ans[len(ans) - (k - k // 2):]))


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
T = int(input())
for ti in range(T):
	(N, M, K) = list(map(int, input().split()))
	G = collections.defaultdict(list)
	for i in range(M):
		(u, v) = list(map(int, input().split()))
		G[u].append(v)
		G[v].append(u)
	museums = [0] + [int(x) for x in input().split()]
	vis = [False] * (N + 1)
	counts = []
	for s in range(1, N + 1):
		if vis[s]:
			continue
		vis[s] = True
		count = 0
		q = [s]
		while q:
			u = q.pop()
			count += museums[u]
			for v in G[u]:
				if not vis[v]:
					vis[v] = True
					q.append(v)
		counts.append(count)
	if len(counts) < K:
		print(-1)
	else:
		counts.sort(reverse=True)
		if K == 1:
			print(counts[0])
		elif K % 2 == 0:
			print(sum(counts[:K // 2]) + sum(counts[-(K // 2):]))
		else:
			print(sum(counts[:K // 2 + 1]) + sum(counts[-(K // 2):]))


t = int(input())
import sys
sys.setrecursionlimit(1000000)

def dfs(node):
	nonlocal l, vis
	st = True
	for i in adj[node]:
		if i in l:
			vis[a] += it[i]
			st = False
			l.remove(i)
			dfs(i)
	if st:
		return ''
for _ in range(t):
	(n, m, k) = list(map(int, input().split()))
	adj = [[] for i in range(n)]
	l = set(range(0, n))
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		adj[x - 1].append(y - 1)
		adj[y - 1].append(x - 1)
	it = list(map(int, input().split()))
	vis = {}
	cost = []
	while l != set():
		a = l.pop()
		vis[a] = it[a]
		dfs(a)
		cost.append(vis[a])
	cost.sort()
	if len(cost) < k:
		print(-1)
		continue
	mi = 0
	ma = len(cost)
	su = 0
	for i in range(k):
		if i % 2 == 0:
			su += cost[ma - 1]
			ma -= 1
		else:
			su += cost[mi]
			mi += 1
	print(su)