Problem:


Score : 600 points

Problem Statement

You are given a forest with N vertices and M edges. The vertices are numbered 0 through N-1.
The edges are given in the format (x_i,y_i), which means that Vertex x_i and y_i are connected by an edge.

Each vertex i has a value a_i.
You want to add edges in the given forest so that the forest becomes connected.
To add an edge, you choose two different vertices i and j, then span an edge between i and j.
This operation costs a_i + a_j dollars, and afterward neither Vertex i nor j can be selected again.

Find the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Constraints

1 ≤ N ≤ 100,000

0 ≤ M ≤ N-1

1 ≤ a_i ≤ 10^9

0 ≤ x_i,y_i ≤ N-1

The given graph is a forest.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M
a_0 a_1 .. a_{N-1}
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Sample Input 1

7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

Sample Output 1

7

If we connect vertices 0 and 5, the graph becomes connected, for the cost of 1 + 6 = 7 dollars.

Sample Input 2

5 0
3 1 4 1 5

Sample Output 2

Impossible

We can't make the graph connected.

Sample Input 3

1 0
5

Sample Output 3

0

The graph is already connected, so we do not need to add any edges.



Sample input:
7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6


Sample output:
7

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import  deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)]# [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))
heapify(H)

res = 0 
while len(H) > 1:
    if S:
        A = S.leftpop()
    else:
        A = heappop(H)
    B = heappop(H)
    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))
    if len(C) == 1:
        S.append(C)
    else:
        heappush(H, C)

if len(S) > 1:
    print("Impossible")
    exit()
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
print(res)

Submission status: Runtime Error

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))

qs = {}
graph = [[] for x in range(n)]
for i in range(m):
    _from, _to = map(int, input().split())
    graph[_from].append(_to)
    graph[_to].append(_from)

visited = [False for x in range(n)]
# print(graph)

for i in range(n):
    first = i
    if visited[i]:
        continue
    que = [[first]]
    q_target = qs.get(first) or []
    while que:
        targets = que.pop()
        for next_target in targets:
            if not visited[next_target]:
                q_target.append(a[next_target])
                visited[next_target] = True
                que.append(graph[next_target])

    q_target.sort()
    qs[first] = q_target
    # print(i)
    # print(visited)
    # print(qs[first])

# print("====")
# print(qs)
# print("====")
cost = 0
first = 0
def impossible():
    print("Impossible")
    __import__("sys").exit()


while True:
    qsf = qs[first]
    if not qsf:
        impossible()

    import math
    min_v = math.inf
    result = None
    for key, value in qs.items():
        if key == first:
            continue
        v = value[0]
        if min_v > v:
            result = key, v
            min_v = v

    if result is None:
        print(0)
        __import__("sys").exit()

    cost += result[1] + qsf[0]
    qs[first] = list(heapq.merge(qs[first][1:], qs[result[0]][1:]))
    del qs[result[0]]
    if len(qs.keys()) == 1:
        print(cost)
        __import__("sys").exit()
    # print(qs)
    # print(cost)

Submission status: Runtime Error

Solution code:
x,y = list(map(int,input().split()))
cost = list(map(int,input().split()))
brid = []
for i in range(y):
	brid.append(list(map(int,input().split())))
target = [[]for n in range(x)]
for lis in brid:
	target[lis[0]].append(lis[1])
	target[lis[1]].append(lis[0])
novis = [i for i in range(x)]
now = []
island = []
queue = []

def dps(t):
	novis.remove(t)
	now.append(t)
	for item in target[t]:
		if item in novis:
			queue.append(item)
	if queue:
		dps(queue.pop(0))
		
while novis:
	now = []
	dps(novis[0])
	island.append(now)
	
lensum = 2
for items in island:
	lensum += (len(items)-1)

if lensum < len(island):
	print("Impossible")
else:
	island.sort(key=len)

	ans = 0 
	while len(island) != 1:
		lis1 = island.pop()
		lis2 = island.pop()
		min1 = 0
		post1 = None
		for num in lis1:
			if min1 == 0:
				min1 = cost[num]
				post1 = num
			else:
				min1 = min(min1,cost[num])
				if min1 == cost[num]:
					post1 = num
		ans += min1
		lis1.remove(post1)
		
		
		min2 = 0
		post2 = None
		for num in lis2:
			if min2 == 0:
				min2 = cost[num]
				post2 = num
			else:
				min2 = min(min2,cost[num])
				if min2 == cost[num]:
					post2 = num
		ans += min2
		lis2.remove(post2)
		
		
		island.append(lis1+lis2)
	print (ans)

Submission status: Runtime Error

Solution code:

import numpy as np
N, M = (int(num) for num in input().split(" "))
a = [int(num) for num in input().split(" ")]
node = []
flag = True
for i in range(M):
    data = [int(num) for num in input().split(" ")]
    data = sorted(data)
    node.append([data[0],data[1],False])

node = sorted(node, key=lambda x:x[0])
route = {}
count = 0
num = 0
route_data = []
route_set = []

for i in range(M):
    if not node[i][2]:
        route['%s' %count] = [node[i][0]]
        for j in range(M):
            if node[j][0] in route['%s' %count]:
                route['%s' %count].append(node[j][1])
                node[j][2] = True
                num += 1
        target_set = set(route["%s" %count])
        r_flag = True

        for k in route_data:
            if target_set & route_set[k]:
                route_set[k] = route_set[k] | target_set
                r_flag = False
        if r_flag:
            route_data.append(count)
            route_set.append(set(route["%s" %count]))

    count += 1
    if num == M:
        break

mini_data = []
cost = 0
for i,r_set in enumerate(route_set):
    mini_d = a[min(r_set):max(r_set)+1]
    mini_d.sort()
    mini_data.append([i,mini_d])

edge = 0
for k in range(len(route_set)-1):
    m = 1000000
    sm = 100000
    for i in mini_data:
        if m > i[1][0]:
            m = i[1][0]
            memory = i[0]

        elif sm > i[1][0]:
            sm = i[1][0]
            smemory = i[0]
    edge += 1
    cost += m
    cost += sm
    mini_data[memory][1] = mini_data[memory][1][1:]
    mini_data[smemory][1] = mini_data[smemory][1][1:]

s = 0

for i in range(len(route_set)):
    s += len(route_set[i])

if s == 0 and N == 1:

    s = 1

if s != N:
    print("Impossible")
else:
    print(cost)

Submission status: Runtime Error

Solution code:
x,y = list(map(int,input().split()))
cost = list(map(int,input().split()))
brid = []
for i in range(y):
	brid.append(list(map(int,input().split())))
target = [[]for n in range(x)]
for lis in brid:
	target[lis[0]].append(lis[1])
	target[lis[1]].append(lis[0])
novis = [i for i in range(x)]
now = []
island = []
queue = []

def dps(t):
	novis.remove(t)
	now.append(t)
	for item in target[t]:
		if item in novis:
			queue.append(item)
	if queue:
		dps(queue.pop(0))
		
while novis:
	now = []
	dps(novis[0])
	island.append(now)
	
lensum = 2
for items in island:
	lensum += (len(items)-1)

if lensum < len(island):
	print("Impossible")
else:
	island.sort(key=len)

	ans = 0 
	while len(island) != 1:
		lis1 = island.pop()
		lis2 = island.pop()
		min1 = 0
		post1 = None
		for num in lis1:
			if min1 == 0:
				min1 = cost[num]
				post1 = num
			else:
				min1 = min(min1,cost[num])
				if min1 == cost[num]:
					post1 = num
		print (min1)
		ans += min1
		lis1.remove(post1)
		
		
		min2 = 0
		post2 = None
		for num in lis2:
			if min2 == 0:
				min2 = cost[num]
				post2 = num
			else:
				min2 = min(min2,cost[num])
				if min2 == cost[num]:
					post2 = num
		print (min2)
		ans += min2
		lis2.remove(post2)
		
		
		island.append(lis1+lis2)
	print (ans)

Submission status: Runtime Error

Solution code:
import networkx as nx
import numpy as np

N, M = map(int, input().split())
A = list(map(int, input().split()))
E = []

for _ in range(M):
    (x, y) = map(int, input().split())
    E.append((x,y))
    
E = list(E)

G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(E)
for i in range(N):
    G.nodes[i]['weight'] = A[i]

n_comp = nx.number_connected_components(G)

if n_comp == 1:
    print(0)
    
else:
    subgraphs = list(nx.connected_component_subgraphs(G))
    comp_vertices = [nx.number_of_nodes(g) for g in subgraphs]
    if max(comp_vertices) <  n_comp - 1:
        print("Impossible")
    else:
        subgraph_v_weight = []
        for i in range(n_comp):
            v_subgraph = list(nx.nodes(subgraphs[i]))
            lst = [(j, subgraphs[i].nodes[j]['weight']) for j in v_subgraph]
            subgraph_v_weight.append(sorted(lst, key=lambda tup:tup[1]))
        
        # initialize
        val = 0
        
        for _ in range(n_comp-1):
            cand = np.array([lst[0][1] for lst in subgraph_v_weight])
            arg = np.argsort(cand)
            val += cand[arg[0]] + cand[arg[1]]
            subgraph_v_weight[arg[0]].pop(0)
            subgraph_v_weight[arg[1]].pop(0)
        
        print(val)

Submission status: Runtime Error

Solution code:
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()


n, m = LI()
a = LI()
d = dict([(i, [i])for i in range(n)])
#print(d)
for i in range(m):
    x, y = LI()
    d[x].append(y)
    d[y].append(x)

        
pow = [1]*n

def mori(num, mori_list):
    for c in d[num]:
        if pow[c] == 1:
            mori_list.append(a[c])
            pow[c] = 0
            mori(c, mori_list)

zen_mori = []
for i in range(n):
    if pow[i] == 1:
        mori_list = []
        mori(i, mori_list)
        zen_mori.append(sorted(mori_list)[::-1])


l = len(zen_mori)
check_list = [0]*l

if n - l < l - 2:
    print("Impossible")
    exit()
ans = 0
for cnt in range(l-1):
    pos = 0
    one, two = 0, 0
    use = []
    while True:
        min_list = [[zen_mori[i][-1] if len(zen_mori[i]) > 0 else (10**9 + 1), i] for i in range(l)]
        use = sorted(min_list)
        one, two = use[pos][1], use[pos+1][1]
        if check_list[one] == 1 and check_list[two] == 1:
            pos += 1
            continue
        if len(zen_mori[one]) == 1 and len(zen_mori[two]) == 1:
            pos += 1
            continue
        break
    ans += use[pos][0] + use[pos+1][0]
    try:
        zen_mori[one].pop()
    except:
        pass
    try:
        zen_mori[two].pop()
    except:
        pass
    check_list[one] = 1
    check_list[two] = 1
print(ans)

Submission status: Runtime Error

Solution code:
    def LI(): return list(map(int, input().split()))
    def LS(): return input().split()
    def I(): return int(input())
    def S(): return input()
     
    n, m = LI()
    a = LI()
    d = dict([(i, [i])for i in range(n)])
    for i in range(m):
        x, y = LI()
        d[x].append(y)
        d[y].append(x)
     
            
    pow = [1]*n
     
    def mori(num, mori_list):
        for c in d[num]:
            if pow[c] == 1:
                mori_list.append(a[c])
                pow[c] = 0
                mori(c, mori_list)
     
    zen_mori = []
    for i in range(n):
        if pow[i] == 1:
            mori_list = []
            mori(i, mori_list)
            zen_mori.append(sorted(mori_list)[::-1])
     
     
    l = len(zen_mori)
    check_list = [0]*l
     
    if n - l < l - 2:
        print("Impossible")
        exit()
     
    ans = 0
    for cnt in range(l-1):
        pos = 0
        one, two = 0, 0
        use = []
        while True:
            min_list = [[zen_mori[i][-1] if len(zen_mori[i]) > 0 else (10**9 + 1), i] for i in range(l)]
            use = sorted(min_list)
            one, two = use[pos][1], use[pos+1][1]
            if check_list[one] == 1 and check_list[two] == 1:
                pos += 1
                continue
            if len(zen_mori[one]) == 1 and len(zen_mori[two]) == 1:
                pos += 1
                continue
            break
        ans += use[pos][0] + use[pos+1][0]
        try:
            zen_mori[one].pop()
        except:
            pass
        try:
            zen_mori[two].pop()
        except:
            pass
        check_list[one] = 1
        check_list[two] = 1
    print(ans)

Submission status: Runtime Error

Solution code:
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()

n, m = LI()
a = LI()
d = dict([(i, [i])for i in range(n)])
for i in range(m):
    x, y = LI()
    d[x].append(y)
    d[y].append(x)

        
pow = [1]*n

def mori(num, mori_list):
    for c in d[num]:
        if pow[c] == 1:
            mori_list.append(a[c])
            pow[c] = 0
            mori(c, mori_list)

zen_mori = []
for i in range(n):
    if pow[i] == 1:
        mori_list = []
        mori(i, mori_list)
        zen_mori.append(sorted(mori_list)[::-1])


l = len(zen_mori)
check_list = [0]*l

if n - l < l - 2:
    print("Impossible")
    exit()

ans = 0
for cnt in range(l-1):
    pos = 0
    one, two = 0, 0
    use = []
    while True:
        min_list = [[zen_mori[i][-1] if len(zen_mori[i]) > 0 else (10**9 + 1), i] for i in range(l)]
        use = sorted(min_list)
        one, two = use[pos][1], use[pos+1][1]
        if check_list[one] == 1 and check_list[two] == 1:
            pos += 1
            continue
        if len(zen_mori[one]) == 1 and len(zen_mori[two]) == 1:
            pos += 1
            continue
        break
    ans += use[pos][0] + use[pos+1][0]
    check_list[one] = 1
    check_list[two] = 1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import insort
from collections import deque
from heapq import heapify, heappop, merge, heapreplace, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    queue = []
    for l in roots.values():
        l.sort()
        queue.append(deque(l))
    queue.sort()
    queue = deque(queue)
    ans = 0
    while len(queue) > 1:
        # print(queue)
        buf = []
        dq1 = queue.popleft()
        dq2 = queue.popleft()
        if len(dq1) == 1:
            while len(dq2) == 1 and len(queue) > 0:
                buf.append(dq2)
                dq2 = queue.popleft()
        ans += dq1.popleft() + dq2.popleft()
        insort(queue, deque(merge(dq1, dq2)))
        if buf:
            queue.extendleft(reversed(buf))
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
import heapq
n, m = map(int, input().split())
costs = list(enumerate(list(map(int, input().split()))))
que = deque(range(n))
vortexs = [[] for i in range(n)]
if n == 1:
    print("0")
    exit()
for i in range(m):
    l, r = map(int, input().split())
    vortexs[r].append(l)
    vortexs[l].append(r)
trees = []
def dfs(now, li, queue = deque()):
    if not li:
        li = []
    if now in que:
        que.remove(now)
        li.append(costs[now])
        for j in vortexs[now]:
            if j in que:
                queue.append(j)
        while queue:
            dfs(queue.popleft(), li, queue)
        return sorted(li, key=lambda x: x[1])
for i in range(n):
    if i in que:
        trees.append(dfs(i, []))
ans = 0
if len(trees) == 1:
    print("0")
for i in range(len(trees) - 1):
    ans += trees[i][0][1]
    ans += trees[i + 1][0][1]
    trees[i].pop(0)
    trees[i + 1].pop(0)
    if len(trees[i]) == 1:
        print("Impossible")
        exit()
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import insort
from collections import deque
from heapq import heapify, heappop, merge, heapreplace, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    queue = []
    for l in roots.values():
        l.sort()
        queue.append(deque(l))
    queue.sort()
    queue = deque(queue)
    ans = 0
    while len(queue) > 1:
        # print(queue)
        buf = []
        dq1 = queue.popleft()
        dq2 = queue.popleft()
        if len(dq1) == 1:
            while len(dq2) == 1 and len(queue) > 1:
                buf.append(dq2)
                dq2 = queue.popleft()
        ans += dq1.popleft() + dq2.popleft()
        insort(queue, deque(merge(dq1, dq2)))
        if buf:
            queue = deque(merge(queue, buf))
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split(' '))
A=[]
Q=list(map(int,input().split(' ')))
q=0
while q<N:
    A.append([0,0,0])
    A[q][1]=Q[q]
    A[q][2]=q
    q+=1
m=1
while m < M+1:
    x,y=map(int,input().split(' '))
    if A[x][0]==0 and A[y][0]==0:
        A[x][0]=m
        A[y][0]=m
        m+=1
    elif A[x][0]!=0 and A[y][0]!=0:
        i=N-1
        Ma=max(A[x][0],A[y][0])
        Ac=A.copy()
        Ac.sort()
        while i>0:
            if Ac[i][0]<Ma:
                break
            if Ac[i][0] == Ma:
                q=Ac[i][2]
                A[q][0]=Ma
            i+=1
        m += 1
    else:
        A[x][0]=max(A[x][0],A[y][0])
        A[y][0]=max(A[x][0],A[y][0])
        m+=1
A.sort()
if N==1 or (N==2 and M!=1):
    print('0')
elif N==2:
    if M==0:
        print(str(A[0][1]+A[1][1]))
elif A[1][0]==0:
    print('Impossible')
else:
    p=1
    pcount=0
    tot=0
    tot2=0
    while p < N:
        if A[p-1][0]==0 and p==1:
            tot+=A[p-1][1]
        elif p==1:
            tot+=A[p-1][1]+A[p][1]
        if A[p-1][0]!=A[p][0]:
            tot+=A[p][1]+A[p+1][1]
            pcount+=1
            tot2=A[p][1]+A[0][1]
        p+=1
    if pcount < 2:
        print(tot2)
    else:
        print(tot)

Submission status: Runtime Error

Solution code:
from bisect import insort
from collections import deque
from heapq import heapify, heappop, merge, heapreplace, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    queue = []
    for l in roots.values():
        l.sort()
        queue.append(deque(l))
    queue.sort()
    queue = deque(queue)
    ans = 0
    while len(queue) > 1:
        buf = []
        dq1 = queue.popleft()
        dq2 = queue.popleft()
        if len(dq1) == 1:
            while len(dq2) == 1 and len(queue) > 1:
                buf.append(dq2)
                dq2 = queue.popleft()
        ans += dq1.popleft() + dq2.popleft()
        insort(queue, deque(merge(dq1, dq2)))
        queue = deque(merge(queue, buf))
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))

Submission status: Runtime Error

Solution code:
# D
import numpy as np

N, M = map(int, input().split())
a_list = list(map(int, input().split()))

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    conn_ = [st]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                conn_.append(t)
                
    args = np.argsort(conn)
    res += conn[args[0]]
    a_list[conn_[args[0]]] = 2000000000

a_list.sort()

if connec == 1:
    print(0)
elif len(a_list) < 2*connec - 2:
    print('Impossible')
else:
    print(res + sum(conn_list[:(connec - 2)]))

Submission status: Runtime Error

Solution code:
class DisjointSet:
  def __init__(self, size):
    self.parent = list(range(size))
    self.rank = [0]*size
  
  def find(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]

  def union(self, x, y):
    xr, yr = self.find(x), self.find(y)
    
    if self.rank[xr] > self.rank[yr]:
      self.parent[yr] = xr
    elif self.rank[xr] < self.rank[yr]:
      self.parent[xr] = yr
    elif xr != yr:
      self.parent[yr] = xr
      self.rank[xr] += 1


from sys import stdin
import heapq as hq

N,M = map(int,stdin.readline().split())
if (N-1-M)*2 > N:
  print('Impossible')
  exit()


A = tuple(map(int,stdin.readline().split()))

ds = DisjointSet(N)
lines = stdin.readlines()
for line in lines:
  x,y = map(int,line.split())
  ds.union(x,y)

memo = [[] for _ in range(N)]

for i,a in enumerate(A):
  memo[ds.find(i)].append(a)

del ds
for t in memo:
  hq.heapify(t)



Q = [(t[0],i) for i,t in enumerate(memo) if t]
hq.heapify(Q)

cost = 0

while len(Q) > 1:
  a,i = hq.heappop(Q)
  b,j = hq.heappop(Q)
  cost += a+b
  hq.heappop(memo[i])
  hq.heappop(memo[j])
  del memo[j]
  memo[i] += memo[j]
  if memo:
    hq.heapify(memo[i])
    hq.heappush(Q,(memo[i][0],i))

print(cost)

Submission status: Runtime Error

Solution code:
from collections import deque
from heapq import heapify, heappop, heappush, merge


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    queue = []
    for l in roots.values():
        l.sort()
        queue.append(deque(l))
    heapify(queue)
    ans = 0
    while len(queue) > 1:
        dq1 = heappop(queue)
        dq2 = heappop(queue)
        ans += dq1.popleft() + dq2.popleft()
        heappush(queue, deque(merge(dq1, dq2)))
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append((a, x))
    queue = []
    for l in roots.values():
        heapify(l)
        queue.append((l[0][0], l))
    heapify(queue)
    ans = 0
    while len(queue) > 1:
        a1, q1 = heappop(queue)
        a2, q2 = heappop(queue)
        ans += a1 + a2
        heappop(q1)
        heappop(q2)
        q1 += q2
        heapify(q1)
        heappush(queue, (q1[0][0], q1))
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))