Chef has entered the politics of Byteland. He is a minister in the coal department of the government. Recently, he has been assigned a project on constructing special bidirectional roads for transferring coals in such a way that the whole country is connected by a road network.

Different companies submitted their proposal of roads that they could build along with their estimated cost of the road. Chef has to select a subset of these proposed roads so that all cities of the country are connected.

Chef, corrupt as he is, managed to submit bids by his own company for certain roads. If some of his proposed roads are selected, he'd use low grade material. We can safely assume that the cost of building these roads is nothing to him. He would still receive the price he has quoted in the bid and hence, would make as much profit. He wants to choose some subset of proposed roads so that his own profit is maximised.

Byteland consists of N cities. There are M1 proposals to build roads by companies other than Chef's. Chef's company has proposed to build M2 roads. Chef wants to choose a subset of these roads in such a way that for each pair of cities, there is exactly one path of roads connecting them. The profit Chef will gain is equal to the sum of costs of the roads chosen from among those made by Chef's company.

Help Chef choose the roads in such a way that his profit is maximized. If there are multiple ways to achieve that, choose the way where the sum of costs of all chosen roads is minimized.

------ Input ------ 

The first line of the input contains a number T, the number of test cases. This is followed by the input for each test case one by one. The first line of each test case contains three space-separated integers N, M1, and M2. Then M1 lines follow, each containing a description of a road proposed by other companies. Each of these lines contains three space-separated integers u, v, and c, where u and v denote the end points of the road and c denotes the associated cost. Then M2 lines follow, each containing a description of a road proposed by Chef's company in the same format.

------ Output ------ 

Output a single line for each test case. If it is impossible to choose a subset of the roads in such a way that for each pair of cities, there is exactly one path of roads connecting them, output a single line containing "Impossible" (quotes for clarity and starts with an uppercase 'I') for that test case. Otherwise, output a single line containing two space-separated integers: the maximum profit Chef can gain and the minimum total cost of the chosen roads that yields the maximum profit.

------ Constraints ------ 

1 ≤ T ≤ 5

2 ≤ N ≤ 5,000

1 ≤ M1 ≤ 20,000

1 ≤ M2 ≤ 20,000

For each proposed road, the end points will be two different cities.

There may be several proposed roads between the same pair of cities.

For each proposed road, 0 ≤ c ≤ 1,000,000,000

Each input file will not be larger than 4 MB (4,000,000,000 bytes) in size.

----- Sample Input 1 ------ 
2
3 2 1
0 1 5
1 2 4
0 1 10
3 1 1
0 1 1
0 1 3
----- Sample Output 1 ------ 
10 14
Impossible

Source: codechef | Difficulty: HARD
Tags: Tree algorithms

Graph algorithms

Spanning trees


Solutions:
from collections import defaultdict
from collections import Counter
import math
import bisect

class dsu:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [0] * (n + 1)

	def start(self):
		for i in range(1, n + 1):
			self.parent[i] = i

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u != v:
			self.parent[v] = u

	def treeinput():
		adj = [[] for i in range(n + 1)]
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			adj[u].append(v)
			adj[v].append(u)

	def check(self, n):
		cnt = 0
		for i in range(n):
			if self.parent[i] == i:
				cnt += 1
		return cnt > 1

def setbit(arr):
	mask = 1
	bit = [0] * 32
	for i in range(32):
		for k in arr:
			if k & mask:
				bit[i] += 1
		mask <<= 1
	return bit

def prefix_sum(nums):
	prefix = [0]
	for i in range(len(nums)):
		prefix.append(prefix[-1] + nums[i])
	return prefix

def mx_lensubarray(nums):
	res = 0
	j = 0
	mp = defaultdict(int)
	prefix = prefixsum(nums)
	mxSum = 0
	for i in range(len(nums)):
		if nums[i] in mp:
			temp = mp[nums[i]]
		else:
			temp = 0
		j = max(temp, j)
		mp[nums[i]] = i + 1
		res = max(res, i - j + 1)
		mxSum = max(mxSum, prefix[i + 1] - prefix[j])
	return res

def lenOfLongSubarr(self, A, N, k):
	mp = {}
	sm = 0
	mxlen = 0
	for i in range(N):
		sm += A[i]
		if sm == k:
			mxlen = i + 1
		if sm - k in mp:
			mxlen = max(mxlen, i - mp[sm - k])
		if sm not in mp:
			mp[sm] = i
	return mxlen

def no_of_factor(s):
	cnt = 0
	x = int(s ** 0.5)
	for i in range(1, x + 1):
		if not s % i:
			cnt = cnt + 1 if s / i == i else cnt + 2
		i += 1
	return cnt

def primes(n):
	arr = []
	i = 2
	while i * i <= n:
		if not n % i:
			cnt = 0
			while not n % i:
				cnt += 1
				n //= i
			arr.append([i, cnt])
		i += 1
	if n > 1:
		arr.append([n, 1])
	return arr

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	res = []
	for i in range(2, n + 1):
		if prime[i]:
			res.append(i)
	return res

def treeinput(n):
	adj = []
	for i in range(n):
		(u, v, w) = map(int, input().split())
		adj.append([w, u, v])
	return adj

def dfs_size(node, parent):
	sum_size[node] = 1
	for child in adj[node]:
		if child != parent:
			dfs_size(child, node)
			sum_size[node] += sum_size[child]

def anda(arr):
	res = arr[0]
	for i in arr:
		res &= i
	return res

def ora(arr):
	res = arr[0]
	for i in arr:
		res |= i
	return res

def xora(arr):
	res = 0
	for i in arr:
		res ^= i
	return res
for _ in range(int(input())):
	(n, m1, m2) = map(int, input().split())
	company_adj = treeinput(m1)
	company_adj.sort()
	chef_adj = treeinput(m2)
	chef_adj.sort(reverse=True)
	d = dsu(n)
	(chef_cost, company_cost) = (0, 0)
	for (w, u, v) in chef_adj:
		if d.find(u) != d.find(v):
			d.union(u, v)
			chef_cost += w
	for (w, u, v) in company_adj:
		if d.find(u) != d.find(v):
			d.union(u, v)
			company_cost += w
	if d.check(n):
		print('Impossible')
		continue
	print(chef_cost, company_cost + chef_cost)