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: Wrong Answer

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)
  tmp=[]
  for root in groups:
    tc,tv=heapq.heappop(qs[root])
    heapq.heappush(qs[root],(tc,tv))
    tmp.append((root,tc))
  groups=sorted(tmp,key=lambda x:x[1])
  root=groups[0][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: Wrong Answer

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: Wrong Answer

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,*b=n+~m<<1,
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or(k>n)*'Impossible'or exec('for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];k-=p>[]')or c+sum(sorted(b)[:k]))

Submission status: Wrong Answer

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
for v in a:d[r(i)]+=v,;i+=1
print([[exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]),0][k<1],'Impossible'][k>n])

Submission status: Wrong Answer

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
for v in a:d[r(i)]+=v,;i+=1
print(int(k>0)and k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Wrong Answer

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;f=print
for v in a:d[r(i)]+=v,;i+=1
print(k>0and k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Wrong Answer

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;f=print
for v in a:d[r(i)]+=v,;i+=1
print(k<1and k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Wrong Answer

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
for v in a:d[r(i)]+=v,;i+=1
if k<1:exit(print(0))
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>n and'Impossible'or c+sum(sorted(b)[:k]))

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N,M = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
  print(0)
  exit()
Cost = []
for i in range(N):
  heappush(Cost,[A[i],i]) #コスト、IDという順で保存。
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())
  #a-=1;b-=1 #既に0index
  uf.union(a,b)
ans = 0
L = [[] for _ in range(N-M)]
dic = {}
num = 0
for i in range(N):
  par = uf.find(i)
  if par not in dic:
    dic[par] = num
    heappush(L[dic[par]],[A[i],i])
    num +=1
  else:
    heappush(L[dic[par]],[A[i],i])
#print(L)
Selected = set([])
for x in L:
  ans += x[0][0] #最小のコスト
  Selected.add(x[0][1]) #頂点
ima = N-M
while ima < 2*(N-M-1) and Cost:
  cost, ID = heappop(Cost)
  if ID in Selected:
    continue
  else:
    ans += cost
    ima += 1
if ima < 2*(N-M-1):
  print("Impossible")
else:
  print(ans)

Submission status: Wrong Answer

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_min = []
    second_min = []
    INF = 10**10
    # roots = uf.roots()

    one_cnts = 0
    one_vals = []
    
    all_members = uf.get_all_members()
    # print(all_members)
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        c_first_min = INF
        c_second_min = INF
        # members = uf.members(r)
        if len(members) == 1: 
            one_cnts += 1
            one_vals.append(al[members[0]])
            continue

        vs = []
        for m in members:
            vs.append(al[m])
            # v = al[m]
            # if v < c_first_min:
            #     c_second_min = c_first_min
            #     c_first_min = v
            # elif v < c_second_min:
            #     c_second_min = v
        vs.sort()
        # first_min.append(c_first_min)
        # second_min.append(c_second_min)
        first_min.append(vs[0])
        second_min.append(vs[1])

    # print(first_min)
    # print(second_min)
    if one_cnts == 0:
        ans = sum(first_min)
        second_min.sort(reverse=True)
        ans += sum(second_min[2:])
        print(ans)
    elif one_cnts == 2:
        ans = one_vals[0] + one_vals[1]
        ans += sum(first_min)
        ans += sum(second_min)
        print(ans)
    elif one_cnts == 1:
        ans = one_vals[0]
        ans += sum(first_min)
        second_min.sort(reverse=True)
        ans += sum(second_min[1:])
        print(ans)
    else:        
        print('Impossible')
        exit()



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N,M = map(int,input().split())
A = list(map(int,input().split()))
Cost = []
for i in range(N):
  heappush(Cost,[A[i],i]) #コスト、IDという順で保存。
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())
  #a-=1;b-=1 #既に0index
  uf.union(a,b)
ans = 0
f_cost,first = heappop(Cost)
Nakama = []
heappush(Nakama,[f_cost,first])
while Cost and M < N-1: #辺の数がN-1よりも小さいなら
  n_cost,nxt = heappop(Cost)
  if uf.is_same(first, nxt): #同じグループなら仲間に追加
    heappush(Nakama,[n_cost,nxt])
  else: #違うグループならこいつと仲間の最小を出して足す。
    if not Nakama: #違うグループが出てきたがすでに仲間は全員選択済み
      break
    nakama_cost,nakama = heappop(Nakama)
    #print(n_cost,nxt,nakama_cost,nakama)
    ans += n_cost + nakama_cost #コストの足し算
    uf.union(nxt,first) #nxtを仲間に入れる。
    M += 1 #辺の数を足す。
#print(M,ans)
if M < N-1:
  print("Impossible")
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N,M = map(int,input().split())
A = list(map(int,input().split()))
Cost = []
for i in range(N):
  heappush(Cost,[A[i],i]) #コスト、IDという順で保存。
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())
  #a-=1;b-=1 #既に0index
  uf.union(a,b)
ans = 0
f_cost,first = heappop(Cost)
Nakama = []
heappush(Nakama,[f_cost,first])
while Cost and Nakama and M < N-1: #辺の数がN-1よりも小さいなら
  n_cost,nxt = heappop(Cost)
  if uf.is_same(first, nxt): #同じグループなら仲間に追加
    heappush(Nakama,[n_cost,nxt])
  else: #違うグループならこいつと仲間の最小を出して足す。
    nakama_cost,nakama = heappop(Nakama)
    #print(n_cost,nxt,nakama_cost,nakama)
    ans += n_cost + nakama_cost #コストの足し算
    uf.union(nxt,nakama) #nxtを仲間に入れる。
    M += 1 #辺の数を足す。
if M < N-1:
  print("Impossible")
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N,M = map(int,input().split())
A = list(map(int,input().split()))
Cost = []
for i in range(N):
  heappush(Cost,[A[i],i]) #コスト、IDという順で保存。
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())
  #a-=1;b-=1 #既に0index
  uf.union(a,b)
ans = 0
f_cost,first = heappop(Cost)
Nakama = []
heappush(Nakama,[f_cost,first])
while Cost and Nakama and M < N-1: #辺の数がN-1よりも小さいなら
  n_cost,nxt = heappop(Cost)
  if uf.is_same(first, nxt): #同じグループなら仲間に追加
    heappush(Nakama,[n_cost,nxt])
  else: #違うグループならこいつと仲間の最小を出して足す。
    nakama_cost,nakama = heappop(Nakama)
    print(n_cost,nxt,nakama_cost,nakama)
    ans += n_cost + nakama_cost #コストの足し算
    uf.union(nxt,nakama) #nxtを仲間に入れる。
    M += 1 #辺の数を足す。
if M < N-1:
  print("Impossible")
else:
  print(ans)

Submission status: Wrong Answer

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_min = []
    second_min = []
    INF = 10**10
    # roots = uf.roots()

    one_cnts = 0
    one_vals = []
    
    all_members = uf.get_all_members()
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        c_first_min = INF
        c_second_min = INF
        # members = uf.members(r)
        if len(members) == 1: 
            one_cnts += 1
            one_vals.append(al[members[0]])
            continue

        for m in members:
            v = al[m]
            if v < c_first_min:
                c_second_min = c_first_min
                c_first_min = v
            elif v < c_second_min:
                c_second_min = v
        first_min.append(c_first_min)
        second_min.append(c_second_min)

    # print(first_min)
    # print(second_min)
    if one_cnts == 0:
        ans = sum(first_min)
        second_min.sort(reverse=True)
        ans += sum(second_min[2:])
        print(ans)
    elif one_cnts == 2:
        ans = one_vals[0] + one_vals[1]
        ans += sum(first_min)
        ans += sum(second_min)
        print(ans)
    elif one_cnts == 1:
        ans = one_vals[0]
        ans += sum(first_min)
        second_min.sort(reverse=True)
        ans += sum(second_min[1:])
        print(ans)
    else:        
        print('Impossible')
        exit()



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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_min = []
    second_min = []
    INF = 10**10
    # roots = uf.roots()

    one_cnts = 0
    one_vals = []
    
    all_members = uf.get_all_members()
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        c_first_min = INF
        c_second_min = INF
        # members = uf.members(r)
        if len(members) == 1: 
            one_cnts += 1
            one_vals.append(al[members[0]])
            continue

        for m in members:
            v = al[m]
            if v < c_first_min:
                c_second_min = c_first_min
                c_first_min = v
            elif v < c_second_min:
                c_second_min = v
        first_min.append(c_first_min)
        second_min.append(c_second_min)

        if one_cnts > 2:
            print('Impossible')
            exit()

    # print(first_min)
    # print(second_min)
    if one_cnts == 0:
        ans = sum(first_min)
        second_min.sort(reverse=True)
        ans += sum(second_min[2:])
        print(ans)
    elif one_cnts == 2:
        ans = one_vals[0] + one_vals[1]
        ans += sum(first_min)
        ans += sum(second_min)
        print(ans)
    elif one_cnts == 1:
        ans = one_vals[0]
        ans += sum(first_min)
        second_min.sort(reverse=True)
        ans += sum(second_min[1:])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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_min = []
    second_min = []
    INF = 10**10
    # roots = uf.roots()



    one_cnts = 0
    all_members = uf.get_all_members()
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        c_first_min = INF
        c_second_min = INF
        # members = uf.members(r)
        if len(members) == 1: one_cnts += 1
        for m in members:
            v = al[m]
            if v < c_first_min:
                c_second_min = c_first_min
                c_first_min = v
            elif v < c_second_min:
                c_second_min = v
        first_min.append(c_first_min)
        second_min.append(c_second_min)

    if one_cnts > 2:
        print('Impossible')
        exit()

    # print(first_min)
    # print(second_min)
    ans = sum(first_min)
    second_min.sort(reverse=True)
    ans += sum(second_min[2:])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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_min = []
    second_min = []
    INF = 10**10
    # roots = uf.roots()



    one_cnts = 0
    all_members = uf.get_all_members()
    if len(all_members) == 1:
        print(0)
        exit()
        
    for members in all_members:
        c_first_min = INF
        c_second_min = INF
        # members = uf.members(r)
        if len(members) == 1: one_cnts += 1
        for m in members:
            v = al[m]
            if v < c_first_min:
                c_second_min = c_first_min
                c_first_min = v
            elif v < c_second_min:
                c_second_min = v
        first_min.append(c_first_min)
        if c_second_min != INF:
            second_min.append(c_second_min)

    if one_cnts > 2:
        print('Impossible')
        exit()

    # print(first_min)
    # print(second_min)
    ans = sum(first_min)
    second_min.sort(reverse=True)
    ans += sum(second_min[2:])
    print(ans)

if __name__ == "__main__":
    main()