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:
#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(idx1,idx2)
        flag.add(idx1)
        flag.add(idx2)
        ans+=c1+c2
        while a[j][1] in flag:
            j+=1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
class SkewHeap:
    # https://qiita.com/lowking/items/89b9346fe90aa3775983
  def __init__(self, init_val = None):
    self.val = init_val
    self.left = None
    self.right = None
    self.root = None
  def heapmeld(self, h1, h2):
    if h1 == None: return h2
    if h2 == None: return h1
    if h1.val == None: return h2
    if h2.val == None: return h1
    if h1.val > h2.val:
      h1.val, h1.left, h1.right, h2.val, h2.left, h2.right = h2.val, h2.left, h2.right, h1.val, h1.left, h1.right
    h1.right = self.heapmeld(h2, h1.right)
    h1.left, h1.right = h1.right, h1.left
    return h1
  def heappop(self):
    res = self.root.val
    self.root = self.heapmeld(self.root.left, self.root.right)
    return res
  def heappush(self, x):
    h = SkewHeap(x)
    self.root = self.heapmeld(self.root, h)
  def heaptop(self):
    if self.root == None:
      return None
    return self.root.val
  
N,M=map(int,input().split())
*A,=map(int,input().split())
uf = UnionFind(N)
for i in range(M):
  x,y=map(int,input().split())
  uf.unite(x,y)
  
group = {}
for i in range(N):
  g = uf.find(i)
  if not group.get(g):
    group[g] = SkewHeap()
  group[g].heappush(A[i])
  
if len(group)==1:
  print(0)
  exit()
    
def kruskal():
    from heapq import heappush, heappop
    que = []
    score = 0
    while len(group.keys())>1:
        que = []
        for g in group.keys():
          try:
            heappush(que,(group[g].heappop(),g))
          except:
            return -1
        dist1,g1 = heappop(que)
        dist2,g2 = heappop(que)
        score += dist1+dist2
        group[g1] = group[g1].heapmeld(group[g1],group[g2])
        del group[g2]
    return score
  
score = kruskal()

print(score if score > 0 else "Impossible")

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    def solve():
        from collections import deque, defaultdict
        N, M = map(int, readline().split())
        a = list(map(int, readline().split()))
        edge = defaultdict(list)
        ans = 0

        for _ in range(M):
            x, y = map(int, readline().split())
            edge[x].append(y)
            edge[y].append(x)

        visited = [False] * N

        def bfs(s):
            que = deque()
            pq = PriorityQueue()
            que.append(s)
            visited[s] = True
            while que:
                cur = que.popleft()
                pq.push(a[cur])
                for nx in edge[cur]:
                    if not visited[nx]:
                        visited[nx] = True
                        que.append(nx)
            return pq

        costs = bfs(0)

        for i in range(1, N):
            if not visited[i]:
                next_costs = bfs(i)
                if not costs:
                    return -1
                ans += costs.pop()
                ans += next_costs.pop()

                while next_costs:
                    costs.push(next_costs.pop())
        return ans

    ans = solve()
    if ans == -1:
        print("Impossible")
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


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


def main():
    def solve():
        N, M = map(int, readline().split())
        a = list(map(int, readline().split()))
        pq = PriorityQueue()
        uf = UnionFind(N)

        for _ in range(M):
            x, y = map(int, readline().split())
            uf.union(x, y)

        for x in uf.members(0):
            pq.push(a[x])

        ans = 0

        for y in range(N):
            if not uf.same(0, y):
                costs = []
                for z in uf.members(y):
                    costs.append(a[z])
                if not pq:
                    return -1
                else:
                    mn = min(costs)
                    ans += pq.pop()
                    ans += mn
                    costs.remove(mn)
                    for z in costs:
                        pq.push(z)
                uf.union(0, y)

        return ans

    ans = solve()
    if ans == -1:
        print("Impossible")
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


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


def main():
    def solve():
        N, M = map(int, readline().split())
        a = list(map(int, readline().split()))
        pq = PriorityQueue()
        uf = UnionFind(N)

        for _ in range(M):
            x, y = map(int, readline().split())
            uf.union(x, y)

        for x in uf.members(0):
            pq.push(a[x])

        ans = 0

        for y in range(N):
            if not uf.same(0, y):
                costs = []
                for z in uf.members(y):
                    costs.append(a[z])
                if not pq:
                    return -1
                else:
                    mn = min(costs)
                    ans += pq.pop()
                    ans += mn
                    costs.remove(mn)
                    for z in costs:
                        pq.push(z)
                uf.union(x, y)

        return ans

    ans = solve()
    if ans == -1:
        print("Impossible")
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

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

uf = UnionFind(n)

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

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0

all_costs=[]
for r in uf.roots():
    costs=[]
    for mem in uf.members(r):
        pass

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

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

uf = UnionFind(n)

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

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0

all_costs=[]
for r in uf.roots():
    costs=[]
    for mem in uf.members(r):
        costs.append(a[mem])

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

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

uf = UnionFind(n)

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

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0

all_costs=[]
for r in uf.roots():
    costs=[]
    for mem in uf.members(r):
        costs.append(a[mem])
    costs.sort()
    ans+=costs[0]

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

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

uf = UnionFind(n)

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

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

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
  groups=list(groups)
  roots=[]
  for tmp_root in groups:
    tc,tv=heapq.heappop(qs[tmp_root])
    heapq.heappush(qs[tmp_root],(tc,tv))
    heapq.heappush(roots,(tc,tv))
  for _ in range(len(groups)-1):
    cv,v=heapq.heappop(roots)
    cu,u=heapq.heappop(roots)
    ans+=(cv+cu)
    rootv=uf.FindRoot(v)
    heapq.heappop(qs[rootv])
    rootu=uf.FindRoot(u)
    heapq.heappop(qs[rootu])
    uf.Unite(v,u)
    newroot=uf.FindRoot(v)
    if rootu==newroot:
      while len(qs[rootv])!=0:
        tc,tv=heapq.heappop(qs[rootv])
        heapq.heappush(qs[newroot],(tc,tv))
      tc,tv=heapq.heappop(qs[newroot])
      heapq.heappush(qs[newroot],(tc,tv))
      heapq.heappush(roots,(tc,tv))
    else:
      while len(qs[rootu])!=0:
        tc,tv=heapq.heappop(qs[rootu])
        heapq.heappush(qs[newroot],(tc,tv))
      tc,tv=heapq.heappop(qs[newroot])
      heapq.heappush(qs[newroot],(tc,tv))
      heapq.heappush(roots,(tc,tv))
  remains=[]
  for v in range(n):
    if v in isolates:
      continue
    while len(qs[v])!=0:
      tc,tv=heapq.heappop(qs[v])
      heapq.heappush(remains,(tc,tv))
  for tmp_root in isolates:
    cv,v=heapq.heappop(remains)
    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
  groups=list(groups)
  roots=[]
  for tmp_root in groups:
    tc,tv=heapq.heappop(qs[tmp_root])
    heapq.heappush(qs[tmp_root],(tc,tv))
    heapq.heappush(roots,(tc,tv))
  for _ in range(len(groups)-1):
    cv,v=heapq.heappop(roots)
    cu,u=heapq.heappop(roots)
    ans+=(cv+cu)
    rootv=uf.FindRoot(v)
    heapq.heappop(qs[rootv])
    rootu=uf.FindRoot(u)
    heapq.heappop(qs[rootu])
    uf.Unite(v,u)
    newroot=uf.FindRoot(v)
    if rootu==newroot:
      while len(qs[rootv])!=0:
        tc,tv=heapq.heappop(qs[rootv])
        heapq.heappush(qs[newroot],(tc,tv))
      tc,tv=heapq.heappop(qs[newroot])
      heapq.heappush(qs[newroot],(tc,tv))
      heapq.heappush(roots,(tc,tv))
    else:
      while len(qs[rootu])!=0:
        tc,tv=heapq.heappop(qs[rootu])
        heapq.heappush(qs[newroot],(tc,tv))
      tc,tv=heapq.heappop(qs[newroot])
      heapq.heappush(qs[newroot],(tc,tv))
      heapq.heappush(roots,(tc,tv))
  remains=[]
  for v in range(n):
    root=uf.FindRoot(v)
    if root in isolates:
      continue
    while len(qs[root])!=0:
      tc,tv=heapq.heappop(qs[root])
      heapq.heappush(remains,(tc,tv))
  for tmp_root in isolates:
    cv,v=heapq.heappop(remains)
    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)
  roots=[]
  for tmp_root in groups:
    tc,tv=heapq.heappop(qs[tmp_root])
    heapq.heappush(qs[tmp_root],(tc,tv))
    heapq.heappush(roots,(tc,tv))
  for _ in range(len(groups)-1):
    cv,v=heapq.heappop(roots)
    cu,u=heapq.heappop(roots)
    ans+=(cv+cu)
    rootv=uf.FindRoot(v)
    heapq.heappop(qs[rootv])
    rootu=uf.FindRoot(u)
    heapq.heappop(qs[rootu])
    uf.Unite(v,u)
    newroot=uf.FindRoot(v)
    if rootu==newroot:
      while len(qs[rootv])!=0:
        tc,tv=heapq.heappop(qs[rootv])
        heapq.heappush(qs[newroot],(tc,tv))
      tc,tv=heapq.heappop(qs[newroot])
      heapq.heappush(qs[newroot],(tc,tv))
      heapq.heappush(roots,(tc,tv))
    else:
      while len(qs[rootu])!=0:
        tc,tv=heapq.heappop(qs[rootu])
        heapq.heappush(qs[newroot],(tc,tv))
      tc,tv=heapq.heappop(qs[newroot])
      heapq.heappush(qs[newroot],(tc,tv))
      heapq.heappush(roots,(tc,tv))
  remains=[]
  for _,v in roots:
    root=uf.FindRoot(v)
    while len(qs[root])!=0:
      tc,tv=heapq.heappop(qs[root])
      heapq.heappush(remains,(tc,tv))
  for tmp_root in isolates:
    cv,v=heapq.heappop(remains)
    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)
  roots=[]
  for tmp_root in groups:
    tc,tv=heapq.heappop(qs[tmp_root])
    heapq.heappush(qs[tmp_root],(tc,tv))
    heapq.heappush(roots,(tc,tv))
  for _ in range(len(groups)-1):
    cv,v=heapq.heappop(roots)
    cu,u=heapq.heappop(roots)
    ans+=(cv+cu)
    rootv=uf.FindRoot(v)
    heapq.heappop(qs[rootv])
    if len(qs[rootv])!=0:
      tc,tv=heapq.heappop(qs[rootv])
      heapq.heappush(qs[rootv],(tc,tv))
      heapq.heappush(roots,(tc,tv))
    rootu=uf.FindRoot(u)
    heapq.heappop(qs[rootu])
    if len(qs[rootu])!=0:
      tc,tv=heapq.heappop(qs[rootu])
      heapq.heappush(qs[rootu],(tc,tv))
      heapq.heappush(roots,(tc,tv))
  remains=[]
  for _,v in roots:
    root=uf.FindRoot(v)
    while len(qs[root])!=0:
      tc,tv=heapq.heappop(qs[root])
      heapq.heappush(remains,(tc,tv))
  for tmp_root in isolates:
    cv,v=heapq.heappop(remains)
    cu,u=heapq.heappop(qs[tmp_root])
    ans+=(cv+cu)
  print(ans)