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:
from heapq import heappop
from collections import defaultdict

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


N, M, *L = map(int, open(0).read().split())
A, XY = L[:N], L[N:]

uf = UnionFind(N)
for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y)

C = defaultdict(list)
for i, a in enumerate(A):
    C[uf.find(i)].append(a)

if len(C) < 2:
    print(0)
    quit()

D = [sorted(c) for c in C.values()]
s = sum(heappop(d) for d in D)

L = []
for d in D:
    L += d

if len(L) < len(D) - 2:
    print("Impossible")
else:
    print(s + sum(sorted(D)[:-2]))

Submission status: Runtime Error

Solution code:
import heapq
from collections import deque

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

info = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]

for b, c in info:
    tree[b].append(c)
    tree[c].append(b)

visited = [False] * n
group = []
for i in range(n):
    if visited[i]:
        continue
    q = deque([i])
    visited[i] = True
    tmp = [a[i]]
    while q:
        pos = q.pop()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            q.append(next_pos)
            tmp.append(a[next_pos])
    group.append(tmp)

for i in range(len(group)):
    group[i] = sorted(group[i])
    
ans = 0
cnt = len(group)*2 - 2

if cnt == 0:
    print(0)
    exit()
    
for i in range(len(group)):
    ans += group[i][0]
    cnt -= 1
    group[i][0] = 10**9 + 7

q = []
for i in range(len(group)):
    for num in group[i]:
        if num != 10**9 +7:
            heapq.heappush(q, num)

for i in range(cnt):
    if not q:
        print("Impossible")
        exit()
    ans += heapq.heappush(q)
print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
using namespace std;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

template<typename ...Ts>
void show(Ts... ts){
  cout<<"#:";
  auto print=[](auto v){cout<<v<<" ";};
  initializer_list<int>{(void(print(ts)),0)...};
  cout<<endl;
}



int main(void){
    ll n,m,x,y,ans=0,cmp=0;
    cin>>n>>m;
    vector<ll> a(n,0);
    vector<ll> v(n,-1);
    vector<vector<ll>> g(n);
    rep(i,n)cin>>a[i];
    rep(i,m){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    priority_queue<ll,vector<ll>,greater<ll>> rest;
    
    rep(i,n){
        if(v[i]>0)continue;
        vector<ll> p;
        priority_queue<ll,vector<ll>,greater<ll>> cost;

        p.push_back(i);
        cost.push(a[i]);
        while(!p.empty()){
            ll c=p.back();
            p.pop_back();
            v[c]=a[c];
            for(ll nb:g[c]){
                if(v[nb]==-1){
                    p.push_back(nb);
                    v[nb]=a[nb];
                    cost.push(a[nb]);
                }
            }
        }
        ans+=cost.top();
        cmp+=1;
        cost.pop();
        while(!cost.empty()){
            rest.push(cost.top());
            cost.pop();
        }
    }
    
    if (cmp==1){
        cout<<0<<endl;
    }else if (rest.size()<cmp-2){
        cout<<"Impossible";
    }else{
        rep(i,2*(cmp-1)-cmp){
            ans+=rest.top();
            rest.pop();
        }
        cout<<ans;
    }
}

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(10**7)

show_flg=False
show_flg=True


n,m=LI()
a=LI()
g=[[] for _ in range(n)]
ans=0
cmp=0
for i in range(m):
    x,y=LI()
    g[x].append(y)
    g[y].append(x)

rest=[]
q=[]
v=[-1]*n

for i in range(n):
    if v[i]!=-1:
        continue
    p=[]
    cost=[]
    p.append(i)
    heappush(cost,a[i])
    while p:
        c=p.pop()
        v[c]=a[c]
        for nb in g[c]:
            if v[nb]==-1:
                p.append(nb)
                v[nb]=a[nb]
                heappush(cost,a[nb])
    ans+=heappop(cost)
    cmp+=1
    while cost:
        heappush(rest,heappop(cost))

if cmp==1:
    ans=0
elif len(rest)<cmp-1:
    ans="Impossible"
    a[10**100]
else:# cmp=n-m, n-m-1 edges needed, 2n-2m-2 vers, 2n-2m-2-cmp=n-m-2=cmp-2
    for i in range(cmp-2):
        ans+=heappop(rest)

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(10**7)

show_flg=False
show_flg=True

n,m=LI()
a=LI()
g=[[] for _ in range(n)]
ans=0
cmp=0
for i in range(m):
    x,y=LI()
    g[x].append(y)
    g[y].append(x)

rest=[]
q=[]
v=[-1]*n

for i in range(n):
    if v[i]>0:
        continue
    p=[]
    cost=[]
    p.append(i)
    heappush(cost,a[i])
    while p:
        c=p.pop()
        v[c]=a[c]
        for nb in g[c]:
            if v[nb]==-1:
                p.append(nb)
                v[nb]=a[nb]
                heappush(cost,a[nb])
    ans+=heappop(cost)
    cmp+=1
    while cost:
        heappush(rest,heappop(cost))
    
if len(rest)<cmp-1:
    ans="Impossible"
    a=[0]
    a[1]
elif cmp==1:
    ans=0
    a=[0]
    a[1]
else:
    for i in range(cmp-2):
        ans+=heappop(rest)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import*
def main():
  n,m,*a=map(int,open(0).read().split())
  table=[-1]*n
  def root(x):
    while table[x]>=0:x=table[x]
    return x
  def unite(x,y):
    s1=root(x)
    s2=root(y)
    if s1!=s2:
      if table[s1]>table[s2]:s1,s2=s2,s1
      table[s1]+=table[s2]
      table[s2]=s1
  d=defaultdict(list)
  for x,y in zip(*[iter(a[n:])]*2):unite(x,y)
  for i,v in enumerate(a[:n]):d[root(i)]+=v,
  if len(d)<2:
    print(0)
    return
  *d,=map(sorted,d.values())
  c=sum(heappop(t)for t in d)
  l=[]
  for t in d:l+=t
  i=len(d)-2
  if len(l)<i:
    print('Impossible')
  else:
    print(c+sum(sorted(l)[:i]))
main()

Submission status: Runtime Error

Solution code:
class UnionFind():
  def __init__(self,size):
    self.table=[-1]*size
  def root(self,x):
    while self.table[x]>=0:
      x=self.table[x]
    return x
  def unite(self,x,y):
    s1=self.root(x)
    s2=self.root(y)
    if s1!=s2:
      if self.table[s1]>self.table[s2]:
        s1,s2=s2,s1
      self.table[s1]+=self.table[s2]
      self.table[s2]=s1
  def same(self,x,y):
    return self.root(x)==self.root(y)
  def size(self,x):
    return -self.table[self.root(x)]
from collections import*
from heapq import*
def main():
  n,m,*a=map(int,open(0).read().split())
  u=UnionFind(n)
  d=defaultdict(list)
  for x,y in zip(*[iter(a[n:])]*2):u.unite(x,y)
  for i,v in enumerate(a[:n]):d[u.root(i)]+=v,
  *h,=map(sorted,d.values())
  heapify(h)
  p=heappop
  c=0
  while len(h)>1:
    x,y=p(h),p(h)
    if not x or not y:
      1/0
    c+=p(x)+p(y)
    heappush(h,list(merge(x,y)))
  print(c)
main()

Submission status: Runtime Error

Solution code:
from collections import*
from heapq import*
def main():
  n,m,*a=map(int,open(0).read().split())
  table=[-1]*n
  def root(x):
    while table[x]>=0:x=table[x]
    return x
  def unite(x,y):
    s1=root(x)
    s2=root(y)
    if s1!=s2:
      if table[s1]>table[s2]:s1,s2=s2,s1
      table[s1]+=table[s2]
      table[s2]=s1
  d=defaultdict(list)
  for x,y in zip(*[iter(a[n:])]*2):unite(x,y)
  for i,v in enumerate(a[:n]):d[root(i)]+=v,
  h=sorted(map(sorted,d.values()))
  p=heappop
  c=0
  while len(h)>1:
    x,y=p(h),p(h)
    if len(h)>2:
      if len(x)<2>len(y):
        t=[]
        while len(y)<2:
          t+=y,
          y=p(h)
        for u in t:heappush(h,u)
    if not x or not y:
      print('Impossible')
      exit()
    c+=p(x)+p(y)
    heappush(h,list(merge(x,y)))
  print(c)
main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


parent_data = []

def union(ind):
    global parent_data
    if parent_data[ind] != ind:
        parent_data[ind] = union(parent_data[ind])
    return parent_data[ind]


def main():
    node_num, edge_num = map(int, input().split())
    cost_data = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    global parent_data
    parent_data = [i for i in range(node_num)]

    for i in range(edge_num):
        a, b = data[i]
        parent_a = union(a)
        parent_b = union(b)
        parent_data[min(parent_a, parent_b)] = max(parent_a, parent_b)

    parent_count = defaultdict(int)
    cost_heap = defaultdict(list)
    for i in range(node_num):
        parent_i = union(i)
        parent_count[parent_i] += 1
        heapq.heappush(cost_heap[parent_i], cost_data[i])

    parent_count = list(sorted(parent_count.items(), key=lambda x:-x[1]))

    ans = 0
    ori_ind, ori_count = parent_count[0]
    for i in range(len(parent_count) - 1):
        now_ind, now_count = parent_count[i + 1]
        if len(cost_heap[ori_ind]) == 0:
            print('Impossible')
            sys.exit()
        ori_cost = heapq.heappop(cost_heap[ori_ind])
        now_cost = heapq.heappop(cost_heap[now_ind])
        ans += ori_cost + now_cost
        cost_heap[ori_ind] = heapq.merge(cost_heap[ori_ind], cost_heap[now_ind])

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    uft = UnionFindTree(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uft.unite(x, y)
    groups = uft.groups()
    if len(groups) == 1:
        print(0)
        return
    single = 0
    ans = 0
    h = []
    for g in groups:
        if len(g) == 1:
            single += 1
            ans += A[g[0]]
        else:
            if len(h) == 0:
                for cost in [A[x] for x in g]:
                    heappush(h, cost)
            else:
                costs = [A[x] for x in g]
                costs.sort()
                ans += costs[0]
                for cost in costs[1:]:
                    heappush(h, cost)
    if len(groups) == 2 and N == 2:
        print(ans)
        return
    if len(h) < single:
        print("Impossible")
        return
    for _ in range(len(groups)-1):
        ans += heappop(h)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 0
        if len(self.costs[px]) == 0 or len(self.costs[py]) == 0:
            print("Impossible")
            exit()
        cost = heapq.heappop(self.costs[px])+heapq.heappop(self.costs[py])
        self.union(px, py)
        return cost

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


if M == N-1:
    print(0)
elif N < 2*(N-M-1):
    print("Impossible")
else:
    cost = 0
    for l in Un.get_parents():
        cost += heapq.heappop(Un.costs[l])

    remain_l = []
    for l in Un.get_parents():
        for v in Un.costs[l]:
            heapq.heappush(remain_l, v)
    for _ in range(2*(N-M-1)):
        cost += heapq.heappop(remain_l)
    print(cost)

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 0
        if len(self.costs[px]) == 0 or len(self.costs[py]) == 0:
            print("Impossible")
            exit()
        cost = heapq.heappop(self.costs[px])+heapq.heappop(self.costs[py])
        self.union(px, py)
        return cost

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


cost = 0
for l in Un.get_parents():
    cost += heapq.heappop(Un.costs[l])

remain_l = []
for l in Un.get_parents():
    for v in Un.costs[l]:
        heapq.heappush(remain_l, v)
for _ in range(2*(N-M-1)):
    cost += heapq.heappop(remain_l)
print(cost)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

P=[i for i in range(N)]
size=[1 for i in range(N)]

def find(x):
    if x==P[x]:
        return x
    else:
        return find(P[x])
    
def union(y,z):
    Y=find(y)
    Z=find(z)
    if size[y]>=size[z]:
        P[Z]=P[Y]
        size[Y]+=size[Z]
    else:
        P[Y]=P[Z]
        size[Z]+=size[Y]

for i in range(M):
    x,y=map(int,input().split())
    if find(x)!=find(y):
        union(x,y)
#print(P)
S=[]
for i in range(N):
    S.append(find(i))
#print(S)
D={}
O={}
for i in range(N):
    if S[i] not in D:
        D[S[i]]=V[i]
        O[S[i]]=1
    else:
        O[S[i]]+=1
        if D[S[i]]>V[i]:
            D[S[i]:V[i]]
#print(D,O)
One=0
#print("S",S)
for i in O:
    #print(O[i])
    if O[i]==1:
        One+=1
#print("One",One)
if (One-1)*2>N:
    print("Impossible")
    exit()
W=[]
for i in range(N):
    W.append([V[i],S[i]])
W.sort()
#print(W)
ans=sum(D.values())
#print(ans)
#print(D)
if len(D)==1:
    print(0)
    exit()
for i in range(len(D)-1):
    if W[i][1] in D:
        if D[W[i][1]]==W[i][0]:
            continue
        else:
            ans+=W[i][0]
    else:
        ans+=W[i][0]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

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

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

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

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

for i in D:
    D[i] = sorted(D[i])

j = 0
for i in D:
    if len(D[i]) == 1:
        j += 1

if j >= 3:
    print("Impossible")
elif N == 1:
    print(0)
else:
    if j == 2:
        ans = 0
        for i in D:
            if len(D[i]) == 1:
                ans += D[i][0]
            else:
                ans += D[i][0] + D[i][1]
        print(ans)
    elif j == 1:
        ans = 0
        d = []
        for i in D:
            if len(D[i]) == 1:
                ans += D[i][0]
            else:
                ans += D[i][0] + D[i][1]
                d.append(D[i][1])
        print(ans - max(d))
    else:
        ans = 0
        d = []
        for i in D:
            if len(D[i]) == 1:
                ans += D[i][0]
            else:
                ans += D[i][0] + D[i][1]
                d.append(D[i][1])
        d = sorted(d)
        print(ans - d[-1] - d[-2])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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

UF.all_find()

D = defaultdict(list)
for i in range(N):
    D[UF.par[i]].append(A[i])

ans = 0
for key in D.keys():
    heapq.heapify(D[key])

ans = 0
if N // 2 < len(D):
    print("Impossible")
    exit()

while len(D) > 1:
    target = [(-float('inf'), -1), (-float('inf'), -1)]

    for key, value in D.items():
        heapq.heappushpop(target, (-value[0], key))

    ans += heapq.heappop(D[target[0][1]]) + heapq.heappop(D[target[1][1]])
    D[target[0][1]].append(D[target[1][1]])
    del D[target[1][1]]

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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

UF.all_find()

D = defaultdict(list)
for i in range(N):
    D[UF.par[i]].append(A[i])

ans = 0
for key in D.keys():
    heapq.heapify(D[key])

ans = 0
while len(D) > 1:
    target = [(-float('inf'), -1), (-float('inf'), -1)]
    if [[]] in D.values():
        print("Impossible")
        break

    for key, value in D.items():
        heapq.heappushpop(target, (-value[0], key))

    ans += heapq.heappop(D[target[0][1]]) + heapq.heappop(D[target[1][1]])
    D[target[0][1]].append(D[target[1][1]])
    del D[target[1][1]]

print(ans)

Submission status: Runtime Error

Solution code:
def f(L, x):
  if L[x]==x:
    return x
  L[x] = f(L, L[x])
  return L[x]

def u(L, x, y):
  if f(L, x)==f(L, y):
    return
  L[L[x]] = L[y]

N, M = map(int, raw_input().split())
a = map(int, raw_input().split())
x = [0]*M
y = [0]*M
L = range(N)
for i in range(M):
  x[i], y[i] = map(int, raw_input().split())
  u(L, x[i], y[i])
d = {}
for i in range(N):
  fi = f(L, i)
  d[fi] = d.get(fi, [])+[a[i]]
if N<2*(N-M-1):
  print "Impossible"
elif N-M==1:
  print 0
else:
  r = []
  l = []
  for k in d.keys():
    sd = sorted(d[k])
    r.append(sd[0])
    l.append(sd[1:])
  print r,l
  print sum(r+l[:N-M-2])

Submission status: Runtime Error

Solution code:
def f(L, x):
  if L[x]==x:
    return x
  L[x] = f(L, L[x])
  return L[x]

def u(L, x, y):
  if f(L, x)==f(L, y):
    return
  L[L[x]] = L[y]

N, M = map(int, raw_input().split())
a = map(int, raw_input().split())
x = [0]*M
y = [0]*M
L = range(N)
for i in range(M):
  x[i], y[i] = map(int, raw_input().split())
  u(L, x[i], y[i])
d = {}
for i in range(N):
  fi = f(L, i)
  d[fi] = d.get(fi, [])+[a[i]]
dl = len(d)
if N<2*dl-2:
  print "Impossible"
elif N==dl:
  print 0
else:
  r = []
  l = []
  for k in d.keys():
    sd = sorted(d[k])
    r.append(sd[0])
    l.append(sd[1:])
  print sum(r+l[:dl-2])

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
LF = len(F)
for i in range(LF - 1):
  for f in F:
    if len(list(f)) == 0:
      ans = 'Impossible'
  if ans == 'Impossible':
    break
  f0 = sorted([[heapq.heappop(f), j] for j, f in enumerate(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.heapify(list(heapq.merge(F[f0[0][1]], F[f0[1][1]])))
  F.pop(f0[1][1])
print(ans)

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 F:
      if len(list(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:
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 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)