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: Time Limit Exceeded

Solution code:
class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素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が属するグループと要素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):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素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 {root: self.members(root) for root in self.roots()}

# ---------------------- #

n, m = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
XY = [tuple(int(x) for x in input().split()) for _ in range(m)]

uf = UnionFind(n)
for x, y in XY:
    uf.union(x, y)

k = n - m
if k == 1:
    print(0)
    exit()
if n < 2 * k - 2:
    print("Impossible")
    exit()

ans = 0
used = []
for root in uf.roots():
    tmp = min(A[x] for x in uf.members(root))
    used.append(tmp)
    ans += tmp

for x in used:
    A.remove(x)
A.sort()
ans += sum(A[:k - 2])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(L):
 x,y=map(r,L)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d={}
for l in q:u(l)
i=c=0;b=[];k=(n+~m)*2
for v in a:R=r(i);d[R]=d.get(R,[])+[v];i+=1
print(k<1and'0'or k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

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

    for members in all_members:
        vs = []
        for m in members:
            vs.append(al[m])
        vs.sort()
        first_mins.append(vs[0])
        other_vals = other_vals + vs[1:]

    # print(first_mins)
    ans = 0
    ans += sum(first_mins)
    rem = len(all_members)-2
    if len(other_vals) < rem:
        print('Impossible')
        exit()
    other_vals.sort()
    ans += sum(other_vals[:rem])
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

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

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
          x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

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

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
from bisect import *
def solve():
  ans = 0
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  uf = UnionFind(N)
  for _ in range(M):
    x,y = map(int, input().split())
    uf.union(x,y)
  if N>2*(M+1):
    return 'Impossible'
  if N-M==1:
    return 0
  roots = uf.roots()
  lis1 = []
  for i,r in enumerate(roots):
    lis = uf.members(r)
    for j in range(len(lis)):
      lis[j] = A[lis[j]]
    mini = min(lis)
    ans += mini
    lis.remove(mini)
    for l in lis:
      insort_right(lis1,l)
  lis1.sort()
  ans += sum(lis1[:(N-M-2)])
  return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

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

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
          x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

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

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def solve():
  ans = 0
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  uf = UnionFind(N)
  for _ in range(M):
    x,y = map(int, input().split())
    uf.union(x,y)
  if N>2*(M+1):
    return 'Impossible'
  if N-M==1:
    return 0
  roots = uf.roots()
  lis1 = []
  for i,r in enumerate(roots):
    lis = uf.members(r)
    for j in range(len(lis)):
      lis[j] = A[lis[j]]
    mini = min(lis)
    ans += mini
    lis.remove(mini)
    lis1.extend(lis)
  lis1.sort()
  ans += sum(lis1[:(N-M-2)])
  return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

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

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
          x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

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

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def solve():
  ans = 0
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  uf = UnionFind(N)
  for _ in range(M):
    x,y = map(int, input().split())
    uf.union(x,y)
  if N>2*(M+1):
    return 'Impossible'
  if N-M==1:
    return 0
  roots = uf.roots()
  lis1 = []
  for i,r in enumerate(roots):
    lis = uf.members(r)
    for j in range(len(lis)):
      lis[j] = A[lis[j]]
    lis.sort(reverse=True)
    ans += lis.pop(-1)
    lis1.extend(lis)
  lis1.sort()
  ans += sum(lis1[:(N-M-2)])
  return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

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

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
          x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

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

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def solve():
  ans = 0
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  uf = UnionFind(N)
  for _ in range(M):
    x,y = map(int, input().split())
    uf.union(x,y)
  if N>2*(M+1):
    return 'Impossible'
  if N-M==1:
    return 0
  roots = uf.roots()
  lis1 = []
  for i,r in enumerate(roots):
    lis = uf.members(r)
    for j in range(len(lis)):
      lis[j] = A[lis[j]]
    lis.sort(reverse=True)
    ans += lis.pop(-1)
    for i in range(len(lis)):
      lis1.extend(lis)
  lis1.sort()
  ans += sum(lis1[:(N-M-2)])
  return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(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(self):
        return [self.members(r) for r in 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())

import sys
input = sys.stdin.readline
import heapq

n, m = map(int, input().split())
if m == n-1:
  print(0)
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
uf = UnionFind(n)
for _ in range(m):
  x, y = map(int, input().split())
  uf.unite(x, y)
ans = 0
L = []
for l in uf.all_group():
  K = sorted((A[i] for i in l), reverse=True)
  ans += K.pop()
  for k in K:
    heapq.heappush(L, k)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(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(self):
        return [self.members(r) for r in 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())

import sys
input = sys.stdin.readline
import heapq

n, m = map(int, input().split())
if m == n-1:
  print(0)
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
uf = UnionFind(n)
for _ in range(m):
  x, y = map(int, input().split())
  uf.unite(x, y)
ans = 0
L = []
for l in uf.all_group():
  K = []
  for i in l:
    heapq.heappush(K, A[i])
  ans += heapq.heappop(K)
  for k in K:
    heapq.heappush(L, k)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self,x):
        if(self.parents[x] < 0):
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        others = others + hqs[i]

others.sort()
rem = p - len(ans)
ans = ans + others[:rem]

print(sum(ans))

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(1000000)

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 sorted(uf.roots(), reverse=True, key=lambda x: uf.size(x)):
            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: Time Limit Exceeded

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], uf.members(r)))) for r in uf.roots()}
        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 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())

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    #############################################################
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            self.n = n
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}
    ################################################################################
    N, M = LI()
    a = LI()
    A = []
    for i,j in enumerate(a):
        A.append([j,i])
    A.sort()
    ans = 0
    uf = UnionFind(N)
    for _ in range(M):
        x,y = LI()
        if not uf.same(x,y):
            uf.unite(x,y)
    D = defaultdict(list)
    que_tot = deque()
    rep = defaultdict(bool)
    r = uf.roots()
    for i in r:
        keep = -1
        for j in uf.members(i):
            if not D[i] or D[i]>a[j]:
                D[i] = a[j]
                keep = j
        rep[keep] = True
        ans += D[i]
#    print(rep)
    loop = uf.group_count()-2
    if loop==-1:
        print(0)
        return
    cur = 0
    for i in range(N):
        if cur>=loop:
            break
        if not rep[A[i][1]]:
            cur +=1
            ans += A[i][0]
    if cur<loop:
        print("Impossible")
        return
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    xy=[list(map(int,input().split())) for _ in [0]*m]

    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            temp_list=[]
            temp=self.tree[index][0]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index][0]
            for i in temp_list:
                self.tree[i][0]=index
            return index
    
        #結合
        def unite(self,index1,index2):
            temp_list=[]
            temp=self.tree[index1][0]
            while index1!=temp:
                temp_list.append(index1)
                index1=temp
                temp=self.tree[index1][0]
            for i in temp_list:
                self.tree[i][0]=index1
            r1=index1
            temp_list=[]
            temp=self.tree[index2][0]
            while index2!=temp:
                temp_list.append(index2)
                index2=temp
                temp=self.tree[index2][0]
            for i in temp_list:
                self.tree[i][0]=index2
            r2=index2
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            temp_list=[]
            temp=self.tree[index1][0]
            while index1!=temp:
                temp_list.append(index1)
                index1=temp
                temp=self.tree[index1][0]
            for i in temp_list:
                self.tree[i][0]=index1
            r1=index1
            temp_list=[]
            temp=self.tree[index2][0]
            while index2!=temp:
                temp_list.append(index2)
                index2=temp
                temp=self.tree[index2][0]
            for i in temp_list:
                self.tree[i][0]=index2
            r2=index2
            return r1==r2
    
        #連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    u=unionfind(n)
    for x,y in xy:
        u.unite(x,y)
    for i in range(n):
        u.tree[i][0]=u.root(i)
    ut=u.tree
    d=dict()
    for i in range(n):
        if ut[i][0] in d.keys():
            d[ut[i][0]].append(a[i])
        else:
            d[ut[i][0]]=[a[i]]
    list1=[]
    list2=[]
    for s in d.values():
        s2=sorted(s)
        list1.append(s2[0])
        list2+=s2[1:]
    if len(list1)==1:
        print(0)
    elif len(list1)>len(list2)+2:
        print("Impossible")
    else:
        list2.sort()
        print(sum(list1)+sum(list2[:len(list1)-2]))
main()