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:
from heapq import heappop, heappush
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


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

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

par = [uf.find(i) for i in range(N)]
d = {}
for i, p in enumerate(par):
  if p in d:
    heappush(d[p], A[i])
  else:
    d[p] = [A[i]]

ap = []
for p in d:
  heappush(ap, [heappop(d[p]), p])

ans = 0
while len(d) > 1:
  a1, p1 = heappop(ap)
  a2, p2 = heappop(ap)
  ans += a1 + a2
  if len(d[p1]) < len(d[p2]):
    for a in d[p1]:
      heappush(d[p2], a)
    del d[p1]
    if len(d[p2]) > 0:
      heappush(ap, [heappop(d[p2]), p2])
    else:
      if len(d) == 1:
        continue
      print('Impossible')
      quit()
  else:
    for a in d[p2]:
      heappush(d[p1], a)
    del d[p2]
    if len(d[p1]) > 0:
      heappush(ap, [heappop(d[p1]), p1])
    else:
      if len(d) == 1:
        continue
      print('Impossible')
      quit()

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, merge
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


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

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

par = [uf.find(i) for i in range(N)]
d = {}
for i, p in enumerate(par):
  if p in d:
    heappush(d[p], A[i])
  else:
    d[p] = [A[i]]

ap = []
for p in d:
  heappush(ap, [heappop(d[p]), p])

ans = 0
while len(d) > 1:
  a1, p1 = heappop(ap)
  a2, p2 = heappop(ap)
  ans += a1 + a2
  d[p1] = list(merge(d[p1], d[p2]))
  del d[p2]
  if d[p1]:
    heappush(ap, [heappop(d[p1]), p1])
  else:
    if len(d) == 1:
      continue
    print('Impossible')
    quit()

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


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

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

par = [uf.find(i) for i in range(N)]
d = {}
for i, p in enumerate(par):
  if p in d:
    heappush(d[p], A[i])
  else:
    d[p] = [A[i]]

ap = []
for p in d:
  heappush(ap, [heappop(d[p]), p])

ans = 0
while len(d) > 1:
  a1, p1 = heappop(ap)
  a2, p2 = heappop(ap)
  ans += a1 + a2
  if len(d[p1]) < len(d[p2]):
    for a in d[p1]:
      heappush(d[p2], a)
    del d[p1]
    if len(d[p2]) > 0:
      heappush(ap, [heappop(d[p2]), p2])
    else:
      print('Impossible')
      quit()
  else:
    for a in d[p2]:
      heappush(d[p1], a)
    del d[p2]
    if len(d[p1]) > 0:
      heappush(ap, [heappop(d[p1]), p1])
    else:
      print('Impossible')
      quit()

print(ans)

Submission status: Wrong Answer

Solution code:
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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
rest = []
dic = defaultdict(list)
for i in range(N):
  dic[U.find(i)].append(A[i])
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0]
  rest.extend(dic[k][1:])
if N==M-1:
  print(0)
  exit()
if N<2*(N-M-1):
  print('Impossible')
  exit()

rest.sort()
remain = 2*(N-M-1)-len(dic.keys())
ans += sum(rest[:remain])
print(ans)

Submission status: Wrong Answer

Solution code:
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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
rest = []
dic = defaultdict(list)
cnt = 2*(N-M-1)
for i in range(N):
  dic[U.find(i)].append(A[i])
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0]
  rest.extend(dic[k][1:])
if cnt==-1:
  print(0)
  exit()
if N<2*(N-M-1):
  print('Impossible')
  exit()

rest.sort()
remain = 2*(N-M-1)-len(dic.keys())
ans += sum(rest[:remain])
print(ans)

Submission status: Wrong Answer

Solution code:
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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
used = [False]*N
dic = defaultdict(list)
for i in range(N):
  dic[U.find(i)].append((A[i],i))
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0][0]
  used[dic[k][0][1]] = True
cnt = len(dic.keys())-2
if cnt==-1:
  print(0)
  import sys
  sys.exit()
if N<2*(N-M-1):
  print(0)
  import sys
  sys.exit()
for i in range(N):
  if cnt<=0:
    print(ans)
    break
  if used[i]:
    continue
  ans += A[i]
  cnt -= 1
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
used = [False]*N
dic = defaultdict(list)
cnt = 2*(N-M-1)
for i in range(N):
  dic[U.find(i)].append((A[i],i))
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0][0]
  used[dic[k][0][1]] = True
  cnt -= 1
if cnt==-1:
  print(0)
  import sys
  sys.exit()
for i in range(N):
  if cnt==0:
    print(ans)
    break
  if used[i]:
    continue
  ans += A[i]
  cnt -= 1
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
used = [False]*N
dic = defaultdict(list)
for i in range(N):
  dic[U.find(i)].append((A[i],i))
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0][0]
  used[dic[k][0][1]] = True
cnt = len(dic.keys())-2
if cnt==-1:
  print(0)
  import sys
  sys.exit()
for i in range(N):
  if cnt<=0:
    print(ans)
    break
  if used[i]:
    continue
  ans += A[i]
  cnt -= 1
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[x]

N,M,*L = map(int, open(0).read().split())
A = L[:N]
A = [(A[i],i) for i in range(N)]
A.sort()
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
a = 0
b = 1
ans = 0
used = [False]*N
while b<N:
  while U.same(A[a][1],A[b][1]):
    b += 1
    if b==N:
      break
  else:
    used[a] = True
    used[b] = True
    ans += A[a][0]+A[b][0]
    U.unit(A[a][1],A[b][1])
    while a<N and used[a]:
      a += 1
    while b<N and used[b]:
      b += 1
if U.count(U.find(0))==N:
  print(ans)
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
from heapq import *

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            return True
        else:
            return False

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
uf = UnionFind(n)
ans = 0
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x, y)
if n < 2*(n-m-1):
    print('Impossible')
    exit(0)
if m == n-1:
    print(0)
    exit(0)
tree = {}
pq = []
heapify(pq)
for i in range(n):
    p = uf.find(i)
    if not p in tree.keys():
        ans += a[i]
        tree[p] = a[i]
    else:
        if tree[p] <= a[i]:
            heappush(pq, a[i])
        else:
            ans += a[i] - tree[p]
            tree[p] = a[i]
            heappush(pq, tree[p])
l = len(tree)

for _ in range(2*(n-m-1) - l):
    ans += heappop(pq)
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            return True
        else:
            return False

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
uf = UnionFind(n)
ans = 0
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x, y)
A = [[0,0] for i in range(n)]
for i in range(n):
    A[i] = [a[i],i]
A.sort()
j = 1
flag = [True]*n
for i in range(n):
    if not flag[i]:
        continue
    while j < n:
        if i>=j:
            j += 1
            continue
        x = A[i][1]
        y = A[j][1]
        if flag[i] and flag[j] and not uf.same(x,y) :
            if not (uf.rank[uf.find(x)] == uf.rank[uf.find(y)] == 1) or n==2:
                uf.unite(x,y)
                flag[i] = False
                flag[j] = False
                ans += A[i][0]+A[j][0]
                j += 1
                break
        j+=1
check = uf.find(0)
for i in range(n):
    if check != uf.find(i):
        print('Impossible')
        exit(0)
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y
            return True
        else:
            return False

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
uf = UnionFind(n)
ans = 0
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x, y)
A = [[0,0] for i in range(n)]
for i in range(n):
    A[i] = [a[i],i]
A.sort()
j = 1
flag = [True]*n
for i in range(n):
    while j < n:
        x = A[i][1]
        y = A[j][1]
        if flag[x] and flag[y] and not uf.same(x,y):
            uf.unite(x,y)
            flag[x] = False
            flag[y] = False
            ans += A[i][0]+A[j][0]
            break
        j+=1
check = uf.find(0)
for i in range(n):
    if check != uf.find(i):
        print('Impossible')
        exit(0)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    d = defaultdict(list)
        
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(a):
        if I[a] == a:
            return a
        else:
            I[a] = root(I[a])
            return I[a]
            
    def unite(a,b):
        pa,pb = root(a),root(b)
        ra,rb = rank[a],rank[b]
        if ra > rb:
            I[pb] = pa
        else:
            I[pa] = pb
            if ra == rb:
                rank[pb] += 1
    
    for _ in range(M):
        x,y = map(int,input().split())
        unite(x,y)
        parent = root(x)
    
    for i,num in enumerate(I):
        parent = root(num)
        d[parent].append(a[i])

    separated = len(d.keys())-1
    ans = 0
    for cl in d.values():
        if len(cl) < separated:
            print("Impossible")
            exit()
        else:
            cl.sort()
            ans += sum(cl[:separated])
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

NO = "Impossible"  # type: str

class Impossible(Exception):
    pass

def solve(N: int, M: int, a: "List[int]", x: "List[int]", y: "List[int]"):
    from heapq import merge
    uf = UnionFind(N)
    for xx, yy in zip(x, y):
        uf.union(xx, yy)

    def f():
        aa = {r:iter(sorted(map(lambda x: a[x], m))) for r, m in uf.all_group_members().items()}
        god = uf.find(0)
        c = aa[god]
        for r in uf.roots():
            if uf.same(god, r):
                continue
            uf.union(god, r)
            try:
                yield next(c)
                yield next(aa[r])
            except StopIteration:
                raise Impossible
            except:
                return
            c = merge(c, aa[r])

    try:
        return sum(f())
    except Impossible:
        return NO

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, M, a, x, y))

# https://note.nkmk.me/python-union-find/
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 __iter__(self):
        return iter(range(self.n))
    
    def all_group_members(self):
        ret = {r:[] for r in self.roots()}
        for n in self:
            ret[self.find(n)].append(n)
        return ret
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

NO = "Impossible"  # type: str

class Impossible(Exception):
    pass

def solve(N: int, M: int, a: "List[int]", x: "List[int]", y: "List[int]"):
    from heapq import merge
    uf = UnionFind(N)
    for xx, yy in zip(x, y):
        uf.union(xx, yy)

    def f():
        aa = {r:iter(sorted(map(lambda x: a[x], m))) for r, m in uf.all_group_members().items()}
        god = uf.find(0)
        c = aa[god]
        for r in uf.roots():
            if uf.same(god, r):
                continue
            uf.union(god, r)
            try:
                yield next(c)
                yield next(aa[r])
            except StopIteration:
                raise Impossible
            c = merge(c, aa[r])
    try:
        return sum(f())
    except:
        return NO

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, M, a, x, y))

# https://note.nkmk.me/python-union-find/
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 __iter__(self):
        return iter(range(self.n))
    
    def all_group_members(self):
        ret = {r:[] for r in self.roots()}
        for n in self:
            ret[self.find(n)].append(n)
        return ret
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

NO = "Impossible"  # type: str

class Impossible(Exception):
    pass

def solve(N: int, M: int, a: "List[int]", x: "List[int]", y: "List[int]"):
    from heapq import merge
    uf = UnionFind(N)
    for xx, yy in zip(x, y):
        uf.union(xx, yy)

    def f():
        aa = {r:iter(sorted(map(lambda x: a[x], m))) for r, m in uf.all_group_members().items()}
        god = uf.find(0)
        c = aa[god]
        for r in uf.roots():
            if uf.same(god, r):
                continue
            uf.union(god, r)
            try:
                yield next(c)
                yield next(aa[r])
            except StopIteration:
                raise Impossible
            c = merge(c, aa[r])
            god = uf.find(god)
    try:
        return sum(f())
    except Impossible:
        return NO
    except :
        return -1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, M, a, x, y))

# https://note.nkmk.me/python-union-find/
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 __iter__(self):
        return iter(range(self.n))
    
    def all_group_members(self):
        ret = {r:[] for r in self.roots()}
        for n in self:
            ret[self.find(n)].append(n)
        return ret
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

NO = "Impossible"  # type: str

class Impossible(Exception):
    pass

def solve(N: int, M: int, a: "List[int]", x: "List[int]", y: "List[int]"):
    from heapq import merge
    uf = UnionFind(N)
    for xx, yy in zip(x, y):
        uf.union(xx, yy)

    def f():
        aa = {r:iter(sorted(map(lambda x: a[x], m))) for r, m in uf.all_group_members().items()}
        god = uf.find(0)
        c = aa[god]
        for r in uf.roots():
            if uf.same(god, r):
                continue
            uf.union(god, r)
            try:
                yield next(aa[god])
                yield next(aa[r])
            except StopIteration:
                raise Impossible
            c = merge(aa[god], aa[r])
            god = uf.find(god)
    try:
        return sum(f())
    except Impossible:
        return NO
    except :
        return -1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, M, a, x, y))

# https://note.nkmk.me/python-union-find/
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 __iter__(self):
        return iter(range(self.n))
    
    def all_group_members(self):
        ret = {r:[] for r in self.roots()}
        for n in self:
            ret[self.find(n)].append(n)
        return ret
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == '__main__':
    main()