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: Accepted

Solution code:
from heapq import heapify, heappop

N, M = map(int, input().split())
As = [(A, i) for i, A in enumerate(map(int, input().split()))]

if 2 * (N - M - 1) > N:
    print('Impossible')
    exit()
elif N - M == 1:
    print(0)
    exit()


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

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y: return
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


parent = [i for i in range(N)]
rank = [0] * N

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)

for i in range(N):
    find(i)

# 各々の木の中で、最小のaiを持つ頂点iを求める（辺の追加時に使用する）
minAs = {}
for A, i in As:
    p = parent[i]
    minAs[p] = min(minAs.get(p, (float('inf'), 0)), (A, i))

done = [False] * N
ans = 0
for (A, i) in minAs.values():
    done[i] = True
    ans += A

# 残りの頂点のうち、aiが小さい方から、(N - M - 2)個を選ぶ
heapify(As)
rest = N - M - 2
while rest > 0:
    A, i = heappop(As)
    if not done[i]:
        ans += A
        rest -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind(object):

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

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

    def union(self, x1, x2):
        root1 = self.find(x1)
        root2 = self.find(x2)
        if root1 < root2:
            self.table[root1] += self.table[root2]
            self.table[root2] = root1
        else:
            self.table[root2] += self.table[root1]
            self.table[root1] = root2

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
xy = [[int(x) for x in input().split()] for i in range(M)]

def solve(N, M, A, xy):

    uf = UnionFind(N)
    for x, y in xy:
        uf.union(x, y)

    groups = defaultdict(list)
    for i in range(N):
        groups[uf.find(i)].append(A[i])

    groups = [sorted(g, reverse=True) for g in groups.values()]

    if len(groups) == 1:
        return 0

    r = 0

    xs = []
    for group in groups:
        r += group.pop()
        xs += group

    if len(groups) == 2:
        return r

    if len(groups) - 2 > len(xs):
        return "Impossible"

    xs.sort()
    r += sum(xs[:len(groups) - 2])

    return r

print(solve(N, M, A, xy))

Submission status: Accepted

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(a_list[:(connec - 2)]))

Submission status: Accepted

Solution code:
def dfs(i):
    global ns,flags,a
    if flags[i]:
        return []
    flags[i]=True
    out=[a[i]]
    for n in ns[i]:
        out.extend(dfs(n))
    return out
        

line=input().split()
N=int(line[0])
M=int(line[1])
a=input().split()
ns={}
for i in range(N):
    a[i]=int(a[i])
    ns[i]=[]


for i in range(M):
    line=input().split()
    x=int(line[0])
    y=int(line[1])
    ns[x].append(y)
    ns[y].append(x)

flags=[False for i in range(N)]
sets=[]
for i in range(N):
    if not flags[i]:
        sets.append(dfs(i))

if len(sets)==1:
    print ("0")
    exit(0)
if (len(sets)-1)*2>N:
    print ("Impossible")
    exit(0)

        
tot=0
for s in sets:
    s.sort()
    tot+=s[0]
more=(len(sets)-1)*2-len(sets)
al=[]
for s in sets:
    for p in s[1:]:
        al.append(p)
al.sort()
for i in range(more):
    tot+=al[i]
print(tot)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
*A, = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

from collections import deque
used = set()
ans = 0
cnt = 0
R = []
for i in range(N):
    if i in used:
        continue
    tmp = [A[i]]
    deq = deque([i])
    used.add(i)
    while deq:
        v = deq.popleft()
        for w in G[v]:
            if w in used:
                continue
            tmp.append(A[w])
            deq.append(w)
            used.add(w)
    tmp.sort()
    ans += tmp[0]
    R += tmp[1:]
    cnt += 1
if len(R) + 2 < cnt:
    print("Impossible")
    exit(0)
if cnt == 1:
    print(0)
    exit(0)
R.sort()
ans += sum(R[:cnt-2])
print(ans)

Submission status: Runtime Error

Solution code:
#unionfind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n


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


    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)


        if x == y:
            return


        if self.parents[x] > self.parents[y]:
            x, y = y, x


        self.parents[x] += self.parents[y]
        self.parents[y] = x


    def size(self, x):
        return -self.parents[self.find(x)]


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


    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


    def group_count(self):
        return len(self.roots())


    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=(a[i],i)
a.sort()
uf=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x,y)
s=set()
for i in range(n):
    s.add(uf.find(i))
if len(s)>n//2 and n>=2:
    print("Impossible")
    exit()
flag=set()
ans=0
j=0
for i in range(1,n):
    c1,idx1=a[i]
    c2,idx2=a[j]
    if uf.same(idx1,idx2):
        continue
    else:
        uf.union(i,j)
        flag.add(idx1)
        flag.add(idx2)
        ans+=c1+c2
        while a[j][1] in flag:
            j+=1
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
cost=list(map(int,input().split()))
if n==1:
  print(0)
  exit()
if n==2:
  if m==0:
    print(cost[0]+cost[1])
    exit()
  if m==1:
    print(0)
    exit()
edges=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
for a,b in edges:
  uf.Unite(a,b)
isolates=set()
isolates_cnt=0
groups=set()
groups_cnt=2
qs=[[] for _ in range(n)]
for i in range(n):
  root=uf.FindRoot(i)
  cnt=uf.Count(i)
  if cnt==1:
    isolates_cnt+=1
    isolates.add(root)
    heapq.heappush(qs[root],(cost[i],i))
  else:
    if root not in groups:
      groups_cnt+=cnt-2
    groups.add(root)
    heapq.heappush(qs[root],(cost[i],i))
if groups_cnt<isolates_cnt:
  print('Impossible')
else:
  ans=0
  isolates=list(isolates)
  groups=list(groups)
  root=groups[0]
  for tmp_root in groups[1:]:
    cv,v=heapq.heappop(qs[root])
    cu,u=heapq.heappop(qs[tmp_root])
    ans+=(cv+cu)
    while len(qs[tmp_root])!=0:
      tc,tv=heapq.heappop(qs[tmp_root])
      heapq.heappush(qs[root],(tc,tv))
  for tmp_root in isolates:
    cv,v=heapq.heappop(qs[root])
    cu,u=heapq.heappop(qs[tmp_root])
    ans+=(cv+cU)
  print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # 要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # {根: [グループに含まれる要素のリスト], ...}の辞書を返す
        return {root: self.members(root) for root in self.roots()}

# ---------------------- #

from heapq import heappop, heappush

class DeletableHeap:
    def __init__(self):
        self.size = 0
        self.del_heap = []
        self.heap = []

    def push(self, x):
        heappush(self.heap, x)
        self.size += 1

    def delete(self, x):
        heappush(self.del_heap, x)
        self.size -= 1

    def top(self):
        while self.del_heap and self.heap[0] == self.del_heap[0]:
            heappop(self.heap)
            heappop(self.del_heap)
        if not self.heap:
            return None
        else:
            return self.heap[0]

    def pop(self):
        while self.del_heap and self.heap[0] == self.del_heap[0]:
            heappop(self.heap)
            heappop(self.del_heap)
        if not self.heap:
            return None
        else:
            self.size -= 1
            return self.heap

# ---------------------- #


n, m = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
XY = [tuple(int(x) for x in input().split()) for _ in range(m)]

uf = UnionFind(n)
for x, y in XY:
    uf.union(x, y)

k = uf.group_count()
if k == 1:
    print(0)
    exit()
if n < 2 * k - 2:
    print("Impossible")
    exit()

heap = DeletableHeap()
ans = 0
for root, members in uf.all_group_members().items():
    tmp = 10**18
    for x in members:
        tmp = min(tmp, A[x])
        heap.push(A[x])
    ans += tmp
    heap.delete(tmp)

for _ in range(k - 2):
    ans += heap.pop()

print(ans)

Submission status: Runtime Error

Solution code:
s=sorted
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
*map(u,q),
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=s(p);c+=x;b+=y;j-=1
print(1%k*(c+sum(s(b)[:j]),'Impossible')[k>n])

Submission status: Runtime Error

Solution code:
(n,m),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k=j=n+~m<<1
b,*d=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];j-=p>[]
print(k<1and'0'or(k>n)*'Impossible'or c+sum(sorted(b)[:j]))

Submission status: Runtime Error

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(x,y):
 x,y=r(x),r(y)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for x,y in q:u(x,y)
i=c=0;b=[];k=(n+~m)*2;p=print
for v in a:d[r(i)]+=v,;i+=1
if k<1:p(0)
elif k>n:p('Impossible')
else:
 for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
 p(c+sum(sorted(b)[:k]))

Submission status: Runtime Error

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

    first_mins = []
    other_vals = []
    
    # all_members = uf.get_all_members()
    all_members = list(uf.all_group_members())
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        vs = []
        for m in members:
            vs.append(al[m])
        vs.sort()
        first_mins.append(vs[0])
        for i,v in enumerate(vs[1:]):
            # if i > 0:
            other_vals.append(v)

    # print(first_mins)
    ans = 0
    ans += sum(first_mins)
    rem = len(all_members)-2
    if len(other_vals) < rem:
        print('Impossible')
        exit()
    other_vals.sort()
    ans += sum(other_vals[:rem])
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  if len(f[gk])==0:
    dg1c.append(a[gk])
    continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
#print(dg)
#print(f)
#print(dg1c)
for k in dg.keys():
  dg[k].sort()
  heapify(dg[k])
  heappush(topheap,[dg[k][0],k])
for _ in range(ren-1):
  c1,k1=heappop(topheap)
  c2,k2=heappop(topheap)
  ans+=c1+c2
  heappop(dg[k1])
  heappop(dg[k2])
  while dg[k1]:
    heappush(dg[k2],dg[k1].pop())
  dg.pop(k1)
  if dg[k2]:
    heappush(topheap,[dg[k2][0],k2])
# 頂点2個以上の連結成分は一個だけになっている
# そのコストはtopheapに一個、のこりはdg[k]にある
for i in range(len(dg1c)):
  c=heappop(dg[k2])
  ans+=c
#print(dg1c)
print(ans+sum(dg1c))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

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

    def find(self,x):
        if(self.parents[x] < 0):
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

    def same(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        return (x_root == y_root)

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        # others += hqs[i]
        others.axtend(hqs[i])

others.sort()
rem = p - len(ans)
# ans += others[:rem]
ans.extend(others[:rem])

print(sum(ans))

Submission status: Runtime Error

Solution code:
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x, y)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    if N - 1 == M:
        print(0)
        return
    node = [0] * N
    q = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(q, (A[i], i))
    ans = 0
    for i in range(N-M-1):
        a, n = heappop(q)
        tmpa, tmpn = heappop(q)
        while union.is_same_group(tmpn, n):
            tmpa, tmpn = heappop(q)
        ans += a + tmpa
        union.unite(tmpn, n)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x, y)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    if n - 1 == m:
        print(0)
        return
    node = [0] * N
    q = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(q, (A[i], i))
    ans = 0
    for i in range(N-M-1):
        a, n = heappop(q)
        tmpa, tmpn = heappop(q)
        while union.is_same_group(tmpn, n):
            tmpa, tmpn = heappop(q)
        ans += a + tmpa
        union.unite(tmpn, n)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x, y)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    node = [0] * N
    q = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(q, (A[i], i))
    ans = 0
    for i in range(N-M-1):
        a, n = heappop(q)
        tmpa, tmpn = heappop(q)
        while union.is_same_group(tmpn, n):
            tmpa, tmpn = heappop(q)
        ans += a + tmpa
        union.unite(tmpn, n)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x-1, y-1)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    node = [0] * N
    q = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(q, (A[i], i))
    ans = 0
    for i in range(N-M-1):
        a, n = heappop(q)
        tmpa, tmpn = heappop(q)
        while union.is_same_group(tmpn, n):
            tmpa, tmpn = heappop(q)
        ans += a + tmpa
        union.unite(tmpn, n)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x-1, y-1)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    node = [0] * N
    q = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(q, (A[i], i))
    ans = 0
    for i in range(N-M-1):
        a, n = heappop(q)
        tmpa, tmpn = q.pop()
        while union.is_same_group(tmpn, n):
            tmpa, tmpn = q.pop()
        ans += a + tmpa
        union.unite(tmpn, n)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
if n == 1:
  print(0)
  exit()
if m*2 < n:
    print("Impossible")
    exit()

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

u = Unionfind(n)
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    u.union(x,y)

l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        heapq.heappush(l[i],a[i])
    else:
        heapq.heappush(l[x],a[i])

h = []
for i in range(n):
    if l[i]:
        x = heapq.heappop(l[i])
        heapq.heappush(h,[x,i])
ans = 0
while len(h) > 1:
    a = heapq.heappop(h)
    b = heapq.heappop(h)
    ans += a[0]+b[0]
    heapq.merge(l[a[1]],l[b[1]])
    x = heapq.heappop(l[a[1]])
    heapq.heappush(h,[x,a[1]])
    
print(ans)