Problem:


Score : 600 points

Problem Statement

You are given a forest with N vertices and M edges. The vertices are numbered 0 through N-1.
The edges are given in the format (x_i,y_i), which means that Vertex x_i and y_i are connected by an edge.

Each vertex i has a value a_i.
You want to add edges in the given forest so that the forest becomes connected.
To add an edge, you choose two different vertices i and j, then span an edge between i and j.
This operation costs a_i + a_j dollars, and afterward neither Vertex i nor j can be selected again.

Find the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Constraints

1 ≤ N ≤ 100,000

0 ≤ M ≤ N-1

1 ≤ a_i ≤ 10^9

0 ≤ x_i,y_i ≤ N-1

The given graph is a forest.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M
a_0 a_1 .. a_{N-1}
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Sample Input 1

7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

Sample Output 1

7

If we connect vertices 0 and 5, the graph becomes connected, for the cost of 1 + 6 = 7 dollars.

Sample Input 2

5 0
3 1 4 1 5

Sample Output 2

Impossible

We can't make the graph connected.

Sample Input 3

1 0
5

Sample Output 3

0

The graph is already connected, so we do not need to add any edges.



Sample input:
7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6


Sample output:
7

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

Solution code:
# APC001D
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].add(v)
    ns[v].add(u)

score = 0
count = 0
others = []
seen = [False] * n
for start in range(n):
    if seen[start]:
        continue
    count += 1
    q = [start]
    s = [a[start]]
    seen[start] = True
    while q:
        u = q.pop()
        for v in ns[u]:
            if not seen[v]:
                heapq.heappush(s, a[v])
                q.append(v)
                seen[v] = True
    score += heapq.heappop(s)
    others = heapq.merge(others, s)
    
if n<2*(count-1):
    print("Impossible")
elif count==1:
    print(0)
else:
    for _ in range(2*(count-1)-count):
        if len(others)==0:
            print("Impossible")
            break
        score += heapq.heappop(others)
    else:
        print(score)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].add(v)
    ns[v].add(u)

score = 0
count = 0
others = []
seen = [False] * n
for start in range(n):
    if seen[start]:
        continue
    count += 1
    q = [start]
    s = [a[start]]
    seen[start] = True
    while q:
        u = q.pop()
        for v in ns[u]:
            if not seen[v]:
                heapq.heappush(s, a[v])
                q.append(v)
                seen[v] = True
    score += heapq.heappop(s)
    others = heapq.merge(others, s)
if n<2*(count-1):
    print("Impossible")
elif count==1:
    print(0)
else:
    for _ in range(2*(count-1)-count):
        score += heapq.heappop(others)
    print(score)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
for i in range(n):
  ai = a[i]
  i = root(i)
  heappush(d[i],ai)

ans = 0
forest = []
for i in set(par):
  p = heappop(d[i])
  heappush(forest,(p,i))

for i in range(len(set(par))-1):  
  if len(forest) < 2:
    ans = "Impossible"
    break
  p1,i1 = heappop(forest)
  p2,i2 = heappop(forest)
  ans += p1 + p2
  union(i1,i2)
  if i1 == root(i1):
    for di2 in d[i2]:
      heappush(d[i1],di2)
  else:
    for di1 in d[i1]:
      heappush(d[i2],di1)
  i1 = root(i1)
  heappush(forest,(heappop(d[i1]),i1))

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import defauldict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(n):
  a,b = map(int,input().split())
  union(a,b)
d = defaultdict(list)
for i in range(n):
  ai = a[i]
  i = root(i)
  heappush(d[i],ai)

ans = 0
forest = []
for i in set(par):
  p = heappop(d[i])
  heappush(forest,(p,i))

for i in range(len(set(par))-1):
  p1,i1 = heappop(forest)
  p2,i2 = heappop(forest)
  ans += p1 + p2
  if d[i1]:
    heappush(forest,(heappop(d[i1]),i1))
  if d[i2]:
    heappush(forest,(heappop(d[i2]),i2))
  if len(forest) < 2:
    ans = "Impossible"
    break
print(ans)

Submission status: Runtime Error

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 += heappush(pq)
print(ans)

Submission status: Runtime Error

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]
        try:
            uf.roots()
        except:
            return
        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 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: Runtime Error

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():
            try:
                if uf.same(god, r):
                    continue
                uf.union(god, r)
            except:
                return
            try:
                yield next(c)
                yield next(aa[r])
            except StopIteration:
                raise Impossible
            try:
                c = merge(c, aa[r])
            except:
                return
    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: Runtime Error

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():
            try:
                if uf.same(god, r):
                    continue
                uf.union(god, r)
            except:
                return
            try:
                yield next(c)
                yield next(aa[r])
            except StopIteration:
                raise Impossible
            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: Runtime Error

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 Impossible:
        return NO
    except IndexError:
        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: Runtime Error

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

            try:
                c = merge(c, aa[r])
            except:
                return 

    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: Runtime Error

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 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: Runtime Error

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)
        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
            tmp = merge(aa[god], aa[r])
            god = uf.find(god)
            aa[god] = tmp
    
    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()