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:
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in enumerate(F):
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[heapq.heappop(F[j]), j] for j in range(len(F))])
    ans += f0[0][0] + f0[1][0]
    for f in f0[2:]:
      heapq.heappush(F[f[1]], f[0])
    F[f0[0][1]] = heapq.merge(F[f0[0][1]], F[f0[1][1]])
    F.pop(f0[1][1])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(i):
  if R[i] == A[i]:
    return A[i]
  else:
    R[i] = root(R[i])
    return R[i]
def union(i, j):
  Ri = root(i)
  Rj = root(j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(i)
F = sorted([A[i] for i in list(set(R))])
ans = 0
for a in A[1:]:
  ans += A[0] + a
print(ans)

Submission status: Runtime Error

Solution code:
n = input().split()
num_of_vertice = int(n[0])
num_of_edges   = int(n[1])
costs = list(map(int, input().split()))

islands = []
flag = 0
for e in range(num_of_edges):
    edge = list(map(int, input().split()))
    flag = 0
    for island in islands:
        if (edge[0] in island) or (edge[1] in island):
            island.add(edge[0])
            island.add(edge[1])
            flag = 1
    if flag != 1:
        islands.append({edge[0], edge[1]})


# simplify
simplified = []
flag = 0
for island in islands:
    flag = 1
    for s_is in simplified:
        if len((s_is.intersection(island))) != 0:
            s_is = s_is.union(island)
            flag = 0
            break
    if flag == 1:
        simplified.append(island)
print(simplified)

# islations
isolation = set(list(range(num_of_vertice)))
for island in simplified:
    isolation = isolation.discard(island)

# biggest island
size = 1
for island in simplified:
    size = max(size, len(island))

if (size < len(isolation) + len(simplified)):
    print(size, len(isolation), len(simplified))
    print("Impossible")
else:
    print("Possible")

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict
import heapq

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

if M==N-1:
	print 0
	quit()

nl=[ [] for i in range(N) ]

for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

group_cost=defaultdict(lambda: [])

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	heapq.heappush(group_cost[start],cost[start])
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)
				heapq.heappush(group_cost[start],cost[i])

for i in range(N):
	if V[i] is None:
		dfs(i)

edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1


nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	nokori_cost=heapq.merge(*group_cost.values())

	if len(list(nokori_cost))<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict
import heapq

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

if M==N-1:
	print 0
	quit()

nl=[ [] for i in range(N) ]

for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

group_cost=defaultdict(lambda: [])

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	heapq.heappush(group_cost[start],cost[start])
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)
				heapq.heappush(group_cost[start],cost[i])

for i in range(N):
	if V[i] is None:
		dfs(i)


edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1

nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	nokori_cost=heapq.merge(*group_cost.values())

	if len(nokori_cost)<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict
import heapq

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

if M==N-1:
	print 0
	quit()

nl=[ [] for i in range(N) ]

for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

group_cost=defaultdict(lambda: [])

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	heapq.heappush(group_cost[start],cost[start])
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)
				heapq.heappush(group_cost[start],cost[i])

while None in V:
	i=V.index(None)
	dfs(i)



edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1

nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	nokori_cost=heapq.merge(*group_cost.values())

	if len(nokori_cost)<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict
import heapq

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

if M==N-1:
	print 0
	quit()

nl=[ [] for i in range(N) ]

for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

group_cost=defaultdict(lambda: [])

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	heapq.heappush(group_cost[start],cost[start])
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)
				heapq.heappush(group_cost[start],cost[i])

while None in V:
	i=V.index(None)
	dfs(i)


edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1

nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	for i in group_cost.values():
		nokori_cost+=i

	if len(nokori_cost)<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans

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(10**7)
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 = [] # single

for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))
 
heapify(H)
heapify(S)
 
res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    

    
    A = heappop(H)
    B = heappop(H)
    
    if len(S) > 0:
        D = heappop(S)    
        if D[0] < B[0]:
            heappush(H, B)
            B = D
        else:
            heappush(S, D)
 
    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))
 
    if len(C) == 1:
        heappush(S, C)
    else:
        heappush(H, C)
 
ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0][0]+S[1][0]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

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(10**7)
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 = [] # single

for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))
 
heapify(H)
heapify(S)
 
res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 0:
        D = heappop(S)
    
    A = heappop(H)
    B = heappop(H)
    
    if D[0] < B[0]:
        heappush(H, B)
        B = D
    else:
        heappush(S, D)
 
    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))
 
    if len(C) == 1:
        heappush(S, C)
    else:
        heappush(H, C)
 
ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0][0]+S[1][0]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

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(10**7)
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 True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.popleft()
    else:
        A = heappop(H)

    B = heappop(H)

    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))[:len(H)+len(S)+3]

    if len(C) == 1:
        S.append(C)
    else:
        heappush(H, C)

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

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(10**7)
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 True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.popleft()
    else:
        if len(H) <= 1:
            break
        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)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

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

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(10**7)
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 True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.leftpop()
    else:
        if len(H) <= 1:
            break
        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)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

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

Submission status: Runtime Error

Solution code:
import sys
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")
    sys.exit()


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

    min_v = float("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)
        sys.exit()

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

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(10**5)
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 True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.leftpop()
    else:
        if len(H) <= 1:
            break
        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)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

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

Submission status: Runtime Error

Solution code:
import numpy as np

class Graph():
    def __init__(self, V, E):
        self.vertices = V
        self.edges = E
        self.n_vertices = len(V)
        self.n_edges = len(E)
        self.v_weight = None
        self.e_weight = None
        
        self.degree = np.zeros(self.n_vertices)
        self.adj_matrix = np.zeros((self.n_vertices, self.n_vertices))
        for e in self.edges:
            self.degree[e[0]] += 1
            self.degree[e[1]] += 1
            self.adj_matrix[e[0]][e[1]] = 1
            self.adj_matrix[e[1]][e[0]] = 1
    
        self.laplacian = - self.adj_matrix + np.diag(self.degree)
        self.lap_eigv, self.lap_eigvct = np.linalg.eig(self.laplacian)
        
        self.n_comp = 0
        self.components = []
        visit_flag = np.zeros(self.n_vertices)
        
        def visit(i, lst):
            visit_flag[i] = 1
            lst.append(self.vertices[i])
            for j in range(self.n_vertices):
                if self.adj_matrix[i, j] == 1 and visit_flag[j] == 0:
                    visit(j, lst)
        
        for i in range(self.n_vertices):
            if visit_flag[i] != 1:
                self.n_comp += 1
                c = []
                visit(i, c)
                self.components.append(c)
    
    def set_v_weight(self, W):
        self.v_weight = W
    
    def set_e_weight(self, W):
        self.e_weight = W

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)
V = list(range(N))

G = Graph(V, E)
G.set_v_weight(A)

n_comp = G.n_comp

if n_comp == 1:
    print(0)
    
else:
    subgraphs = G.components
    comp_vertices = [len(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 = subgraphs[i]
            lst = [(j, G.v_weight[j]) 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:
import sys
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")
    sys.exit()


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

    min_v = float("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)
        sys.exit()

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

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(10**10)
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 True:
    if len(H) == 0 or len(S) + len(H) <= 1:
        break   
    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) > 2:
    print("Impossible")
    exit()
elif len(S) == 2:
    res += S[0]+S[1]
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 math
min_v = math.inf

Submission status: Runtime Error

Solution code:
import math
import sys
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")
    sys.exit()


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

min_v = math.inf
result = None

Submission status: Runtime Error

Solution code:
import math
import sys
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")
    sys.exit()


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

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

Submission status: Runtime Error

Solution code:
import math
import sys
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")
    sys.exit()


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

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)
    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)

Submission status: Runtime Error

Solution code:
import math
import sys
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")
    sys.exit()


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

    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)
        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)
        sys.exit()
    # print(qs)
    # print(cost)