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 sys
from collections import deque, defaultdict
import heapq

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    # 根をbxに統一
    A[by] = bx

edges = [[] for _ in range(N)]
V = [i for i in range(N)]
for _ in range(M):
    x, y = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)
    edges[x].append(y)
    edges[y].append(x)

for i in range(N):
    V[i] = find(V, i)

dig_0 = [i for i in range(N) if len(edges[i]) == 0]
l0 = len(dig_0)
if N == 1:
    print(0); exit()
elif l0 > N//2:
    print('Impossible'); exit()

# 孤立していない頂点の根
roots = [V[i] for i in range(N) if i not in dig_0]
root_point = defaultdict(list)
for i in range(N):
    if i in dig_0:
        continue
    r = V[i]
    heapq.heappush(root_point[r], A[i])

#各グループの最小値以外で使うコストの数
remain = (l0 + len(set(roots)) - 1) * 2 - (l0 + len(set(roots)))
answer = 0
for i in dig_0:
    answer += A[i]

candidates = deque()
for po in root_point:
    answer += heapq.heappop(root_point[po])
    for i in range(min(remain, len(root_point[po]))):
        candidates.append(heapq.heappop(root_point[po]))

if len(candidates) < remain:
    print('Impossible'); exit()
for i in range(remain):
    answer += heapq.heappop(candidates)
print(answer)
# 43

Submission status: Runtime Error

Solution code:
import sys
from collections import deque, defaultdict
import heapq

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    # 根をbxに統一
    A[by] = bx

edges = [[] for _ in range(N)]
V = [i for i in range(N)]
for _ in range(M):
    x, y = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)
    edges[x].append(y)
    edges[y].append(x)

for i in range(N):
    V[i] = find(V, i)

dig_0 = [i for i in range(N) if len(edges[i]) == 0]
l0 = len(dig_0)
if N == 1:
    print(0); exit()
elif l0 > N//2:
    print('Impossible'); exit()

# 孤立していない頂点の根
roots = [V[i] for i in range(N) if i not in dig_0]
root_point = defaultdict(list)
for i in range(N):
    if i in dig_0:
        continue
    r = V[i]
    heapq.heappush(root_point[r], A[i])

#各グループの最小値以外で使うコストの数
remain = (l0 + len(set(roots)) - 1) * 2 - (l0 + len(set(roots)))
answer = 0
for i in dig_0:
    answer += A[i]

candidates = deque()
for po in root_point:
    answer += heapq.heappop(root_point[po])
    for i in range(min(remain, len(root_point[po]))):
        candidates.append(heapq.heappop(root_point[po]))

for i in range(remain):
    answer += heapq.heappop(candidates)
print(answer)
# 43

Submission status: Runtime Error

Solution code:
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
res = 0
if M == 0:
  if N == 1:
    print(0)
  elif N == 2:
    print(sum(a))
  else: print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N - 1)
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
hs = [[] for _ in range(N + 1)]
for x in range(N):
  y = uf.Find_Root(x)
  heapq.heappush(hs[y], a[x])
#print(hs)
c = 0
t = []
for x in range(N):
  if len(hs[x]):
    c += 1
    res += heapq.heappop(hs[x])
    t += hs[x]
t.sort()
#print(c, t, hs, res)
if c == 1:
  print(0)
  exit(0)
for i in range(c - 2):
  if i >= c - 2:
    print("Impossible")
    exit(0)
  res += t[i]
print(res)

Submission status: Runtime Error

Solution code:
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
res = 0
if M == 0:
  if N == 1:
    print(0)
  elif N == 2:
    print(sum(a))
  else: print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N - 1)
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
hs = [[] for _ in range(N + 1)]
for x in range(N):
  y = uf.Find_Root(x)
  heapq.heappush(hs[y], a[x])
#print(hs)
c = 0
t = []
for x in range(N):
  if len(hs[x]):
    c += 1
    res += heapq.heappop(hs[x])
    if len(hs[x]): t.append(heapq.heappop(hs[x]))
t.sort()
#print(c, t, hs, res)
if c == 1:
  print(0)
  exit(0)
for i in range(c - 2):
  if i >= c - 2:
    print("Impossible")
    exit(0)
  res += t[i]
print(res)

Submission status: Runtime Error

Solution code:
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
res = 0
if M == 0:
  if N == 1:
    print(0)
  elif N == 2:
    print(sum(a))
  else: print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N - 1)
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
hs = [[] for _ in range(N + 1)]
for x in range(N):
  y = uf.Find_Root(x)
  heapq.heappush(hs[y], a[x])
#print(hs)
c = 0
t = []
for x in range(N):
  if len(hs[x]):
    c += 1
    res += heapq.heappop(hs[x])
    if len(hs[x]): t.append(heapq.heappop(hs[x]))
t.sort()
#print(c, t, hs, res)

for i in range(c - 2):
  if i >= c - 2:
    print("Impossible")
    exit(0)
  res += t[i]
print(res)

Submission status: Runtime Error

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

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

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.unite(x, y)

d = defaultdict(list)
rs = set()

for i in range(N):
    r = uf.root(i)
    rs.add(r)
    d[r].append(a[i])

if len(rs)==1:
    print(0)
    exit()

if 2*(len(rs)-1)>N:
    print('Impossible')
    exit()
    
ans = 0

for k in d.keys():
    d[k].sort()
    ans += d[0]

l = []

for v in d.values():
    l += v[1:]

l.sort()
ans += sum(l[:len(rs)-2])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import heapq
def makeTree(i):
    V = [(A[i],i)]
    que = deque([i])
    hist[i] = 1
    while que:
        x = que.popleft()
        for y in G[x]:
            if hist[y]==0:
                heapq.heappush(V,(A[y],y))
                que.append(y)
                hist[y] = 1
    T[i] = V
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
T = {}
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==0:
        makeTree(i)
if N<2*(len(T)-1):
    print("Impossible")
else:
    heap = []
    for t in T:
        c,v = heapq.heappop(T[t])
        heapq.heappush(heap,(c,v,t))
    cnt = 0
    while len(heap)>=2:
        c1,v1,t1 = heapq.heappop(heap)
        c2,v2,t2 = heapq.heappop(heap)
        cnt += c1+c2
        if len(T[t1])>=len(T[t2]):
            while T[t2]:
                heapq.heappush(T[t1],heapq.heappop(T[t2]))
            del T[t2]
            c3,v3 = heapq.heappop(T[t1])
            heapq.heappush(heap,(c3,v3,t1))
        else:
            while T[t1]:
                heapq.heappush(T[t2],heapq.heappop(T[t1]))
            del T[t1]
            c3,v3 = heapq.heappop(T[t2])
            heapq.heappush(heap,(c3,v3,t2))
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
if N == 1:
  print(0)
  exit(0)
if M == 0 and (N > 2):
  print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
d = [[] for _ in range(N)]
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
for i in range(N):
  d[uf.Find_Root(i)].append(a[i])
res = 0
x = []
y = 0
for i in range(N):
  d[i].sort(reverse = True)
  if len(d[i]):
    res += d[i].pop()
    y += 1
  x += d[i]
x.sort()
for i in range((y - 1) * 2 - y):
  if i > len(x):
    print("Impossible")
    exit(0)
  res += x[i]
print(res)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as de
from heapq import heappop,heappush
n,m=map(int,input().split())
a=list(map(int,input().split()))
r=[i for i in range(n)]
s=[0]*n
def f(x):
    if x==r[x]:
        return x
    x=r[x]
    return f(r[x])
def g(x,y):
    x=f(x)
    y=f(y)
    if s[x]>s[y]:
        r[y]=x
        s[x]+=s[y]
    else:
        r[x]=y
        s[y]+=s[x]
for i in range(m):
    x,y=map(int,input().split())
    g(x,y)
if n<2*(n-m-1):
    print("Impossible")
else:
    c=de(list)
    for i in range(n):
        c[f(i)]+=[a[i]]
    an=sum(heappop(i)for i in c.values())
    q=[]
    for i in c:
        q+=c
    if m!=n-1:
        print(an+sum(sorted(q)[:n-m-2]))
    else:
        print(0)

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush
n,m=map(int,input().split())
a=list(map(int,input().split()))
r=[i for i in range(n)]
s=[0]*n
def f(x):
    if x==r[x]:
        return x
    x=r[x]
    return f(r[x])
def g(x,y):
    x=f(x)
    y=f(y)
    if s[x]>s[y]:
        r[y]=x
        s[x]+=s[y]
    else:
        r[x]=y
        s[y]+=s[x]
for i in range(m):
    x,y=map(int,input().split())
    g(x,y)
if n<2*(n-m-1):
    print("Impossible")
else:
    c={}
    for i in range(n):
        t=f(i)
        if t in c:
            heappush(c[t],a[i])
        else:
            c[t]=[]
            heappush(c[t],a[i])
    an=0
    q=[]
    for i in c.keys():
        an+=heappop(c[i])
        while c[i]:
            q.append(heappop(c[i]))
    if m!=n-1:
        print(an+sum(sorted(q)[:2*(n-m-1)-n+m]))
    else:
        print(0)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
r=[i for i in range(n)]
s=[0]*n
def f(x):
    if x==r[x]:
        return x
    x=r[x]
    return f(r[x])
def g(x,y):
    x=f(x)
    y=f(y)
    if s[x]>s[y]:
        r[y]=x
        s[x]+=s[y]
    else:
        r[x]=y
        s[y]+=s[x]
for i in range(m):
    x,y=map(int,input().split())
    g(x,y)
if n<2*(n-m-1):
    print("Impossible")
else:
    c={}
    for i in range(n):
        t=f(i)
        if t in c:
            c[t].append(a[i])
        else:
            c[t]=[a[i]]
    an=0
    q=[]
    for i in c.keys():
        an+=min(c[i])
        q+=sorted(c[i])[1:]
    if m!=n-1:
    	print(an+sum(sorted(q)[:2*(n-m-1)-n+m]))
    else:
        print(0)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
r=[i for i in range(n)]
s=[0]*n
def f(x):
    if x==r[x]:
        return x
    x=r[x]
    return f(r[x])
def g(x,y):
    x=f(x)
    y=f(y)
    if s[x]>s[y]:
        r[y]=x
        s[x]+=s[y]
    else:
        r[x]=y
        s[y]+=s[x]
for i in range(m):
    x,y=map(int,input().split())
    g(x,y)
if n<2*(n-m-1):
    print("Impossible")
else:
    c={}
    for i in range(n):
        t=f(i)
        if t in c:
            c[t].append(a[i])
        else:
            c[t]=[a[i]]
    an=0
    q=[]
    for i in c.keys():
        an+=min(c[i])
        q+=sorted(c[i])[1:]
    print(an+sum(sorted(q)[:2*(n-m-1)-n+m]))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
r=[i for i in range(n)]
s=[0]*n
def f(x):
    if x==r[x]:
        return x
    x=r[x]
    return f(r[x])
def g(x,y):
    x=f(x)
    y=f(y)
    if s[x]>s[y]:
        r[y]=x
        s[x]+=s[y]
    else:
        r[x]=y
        s[y]+=s[x]
for i in range(m):
    x,y=map(int,input().split())
    g(x,y)
if n<2*(n-m-1):
    print("Impossible")
else:
    c={}
    for i in range(n):
        t=f(i)
        if t in c:
            c[t].append(a[i])
        else:
            c[t]=[a[i]]
    an=0
    q=[]
    for i in c.keys():
        print(c[i])
        an+=min(c[i])
        q+=sorted(c[i])[1:]
    print(an+sum(sorted(q)[:2*(n-m-1)-n+m]))

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop
n,m=map(int,input().split())
a=list(map(int,input().split()))
r=[i for i in range(n)]
s=[0]*n
def f(x):
    if x==r[x]:
        return x
    x=r[x]
    return f(r[x])
def g(x,y):
    x=f(x)
    y=f(y)
    if s[x]>s[y]:
        r[y]=x
        s[x]+=s[y]
    else:
        r[x]=y
        s[y]+=s[x]
for i in range(m):
    x,y=map(int,input().split())
    g(x,y)
if n<2*(n-m-1):
    print("Impossible")
else:
    c={}
    for i in range(n):
        t=f(i)
        if t in c:
            c[t].append(a[i])
        else:
            c[t]=[a[i]]
    q=[]
    for i in c.keys():
        c[i]=sorted(c[i])
        heappush(q,[c[i][0],i,0])
    d=0
    an=0
    while d<2*(n-m-1):
        a,b,e=heappop(q)
        an+=a
        if len(c[b])>e+1:
            heappush(q,[c[i][e+1],i,e+1])
        d+=1
    print(an)

Submission status: Runtime Error

Solution code:
import heapq
def makeTree(j):
    global tree
    for x in G[j]:
        if hist[x]==0:
            heapq.heappush(F[tree],(A[x],x,tree))
            hist[x] = 1
            makeTree(x)
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
if M==N-1:
    cost = 0
elif N<2*(N-M-1):
    cost = "Impossible"
else:
    n = N-M
    F = {}
    hist = [0 for _ in range(N+1)]
    tree = 0
    for j in range(N):
        if hist[j]==1:continue
        if tree not in F:F[tree]=[]
        heapq.heappush(F[tree],(A[j],j,tree))
        hist[j] = 1
        makeTree(j)
        tree += 1
    cost = 0
    B = [heapq.heappop(F[0])]
    C =sorted([heapq.heappop(F[i]) for i in range(1,n)],key=lambda x:x[0],reverse=True)
    for i in range(n-1):
        b = heapq.heappop(B)
        c = C.pop()
        indb = b[2]
        indc = c[2]
        cost += b[0]+c[0]
        if i==n-2:continue
        if len(F[indb])>0:
            heapq.heappush(B,heapq.heappop(F[indb]))
        if len(F[indc])>0:
            heapq.heappush(B,heapq.heappop(F[indc]))
print(cost)

Submission status: Runtime Error

Solution code:
import heapq
def makeTree(j):
    global tree
    for x in G[j]:
        if hist[x]==0:
            heapq.heappush(F[tree],(A[x],x,tree))
            hist[x] = 1
            makeTree(x)
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
if M==N-1:
    cost = 0
elif N<2*(N-M-1):
    cost = "Impossible"
else:
    n = N-M
    F = {}
    hist = [0 for _ in range(N+1)]
    tree = 0
    for j in range(N):
        if hist[j]==1:continue
        if tree not in F:F[tree]=[]
        heapq.heappush(F[tree],(A[j],j,tree))
        hist[j] = 1
        makeTree(j)
        tree += 1
    if len(F)!=n:
        cost = "Impossible"
    else:
        cost = 0
        B = [heapq.heappop(F[0])]
        C =sorted([heapq.heappop(F[i]) for i in range(1,n)],key=lambda x:x[0],reverse=True)
        for i in range(n-1):
            b = heapq.heappop(B)
            c = C.pop()
            indb = b[2]
            indc = c[2]
            cost += b[0]+c[0]
            if i==n-2:continue
            heapq.heappush(B,heapq.heappop(F[indb]))
            heapq.heappush(B,heapq.heappop(F[indc]))
print(cost)

Submission status: Runtime Error

Solution code:
import heapq
def makeTree(j):
    global tree
    for x in G[j]:
        if hist[x]==0:
            heapq.heappush(F[tree],(A[x],x,tree))
            hist[x] = 1
            makeTree(x)
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
if M==N-1:
    cost = 0
elif N<2*(N-M-1):
    cost = "Impossible"
else:
    n = N-M
    F = {i:[] for i in range(n)}
    hist = [0 for _ in range(N+1)]
    tree = 0
    for j in range(N):
        if hist[j]==1:continue
        heapq.heappush(F[tree],(A[j],j,tree))
        hist[j] = 1
        makeTree(j)
        tree += 1
    cost = 0
    B = [heapq.heappop(F[0])]
    C =sorted([heapq.heappop(F[i]) for i in range(1,n)],key=lambda x:x[0],reverse=True)
    for i in range(n-1):
        b = heapq.heappop(B)
        c = C.pop()
        indb = b[2]
        indc = c[2]
        cost += b[0]+c[0]
        if i==n-2:continue
        heapq.heappush(B,heapq.heappop(F[indb]))
        heapq.heappush(B,heapq.heappop(F[indc]))
print(cost)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]
B = sorted([(a,i) for i,a in enumerate(A)])

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.Size = [1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_Size(self,n):
        n = self.get_Parent(n)
        return self.Size[n]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.Parent[y] = x
            self.Size[x] += self.Size[y]
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    U.merge(x,y)

cost1 = 0
count1 = 0
done = [False]*N
for i,a in enumerate(A):
    if U.get_Size(i)==1:
        cost1 += a
        count1 += 1
        done[i] = True
    
if N>10:
    1/0
else:
    ans = count1
    INF = 2*10**9
    E = []
    for i,a in enumerate(A):
        for j,b in enumerate(A[i+1:],i+1):
            E.append((a+b,i,j))
    E.sort()
    for c,i,j in E:
        if done[i] or done[j]: continue
        if U.is_united(i,j): continue
        U.merge(i,j)
        ans += c
        done[i] = True
        done[j] = True
    while count1>0:
        count1 -= 1
        m = INF
        mi = -1
        for i,a in enumerate(A):
            if done[i]:continue
            if m>a:
                m = a
                mi = i
        if mi == -1:
            ans = "Impossible"
            break
        ans += m
        done[mi] = True
    if N==1:ans=0
    print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]
B = sorted([(a,i) for i,a in enumerate(A)])

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.Size = [1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_Size(self,n):
        n = self.get_Parent(n)
        return self.Size[n]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.Parent[y] = x
            self.Size[x] += self.Size[y]
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    U.merge(x,y)

cost1 = 0
count1 = 0
done = [False]*N
for i,a in enumerate(A):
    if U.get_Size(i)==1:
        cost1 += a
        count1 += 1
        done[i] = True
    
if N>100:
    1/0
else:
    ans = count1
    INF = 2*10**9
    E = []
    for i,a in enumerate(A):
        for j,b in enumerate(A[i+1:],i+1):
            E.append((a+b,i,j))
    E.sort()
    for c,i,j in E:
        if done[i] or done[j]: continue
        if U.is_united(i,j): continue
        U.merge(i,j)
        ans += c
        done[i] = True
        done[j] = True
    while count1>0:
        count1 -= 1
        m = INF
        mi = -1
        for i,a in enumerate(A):
            if done[i]:continue
            if m>a:
                m = a
                mi = i
        if mi == -1:
            ans = "Impossible"
            break
        ans += m
        done[mi] = True
    if N==1:ans=0
    print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]
B = sorted([(a,i) for i,a in enumerate(A)])

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.Size = [1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_Size(self,n):
        n = self.get_Parent(n)
        return self.Size[n]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.Parent[y] = x
            self.Size[x] += self.Size[y]
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    U.merge(x,y)

cost1 = 0
count1 = 0
done = [False]*N
for i,a in enumerate(A):
    if U.get_Size(i)==1:
        cost1 += a
        count1 += 1
        done[i] = True

ans = cost1
bi = 0
bj = 1
if N>100:
  while bj<N:
      if bi>=bj:
          bj = bi+1
          continue
      b,i = B[bi]
      if done[i]:
          bi += 1
          continue
      c,j = B[bj]
      if done[j]:
          bj += 1
          continue
      if U.is_united(i,j):
          bj += 1
      else:
          ans += b + c
          done[i] = True
          done[j] = True
          U.merge(i,j)
          bi += 1
          bj += 1
else:
  1/0

for b,i in B:
    if count1 == 0: break
    if done[i]:continue
    ans += b
    count1 -= 1

if N//2 + M < N-1:
    ans = "Impossible"
elif N==1:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]
B = sorted([(a,i) for i,a in enumerate(A)])

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.Size = [1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_Size(self,n):
        n = self.get_Parent(n)
        return self.Size[n]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.Parent[y] = x
            self.Size[x] += self.Size[y]
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    U.merge(x,y)

cost1 = 0
count1 = 0
done = [False]*N
for i,a in enumerate(A):
    if U.get_Size(i)==1:
        cost1 += a
        count1 += 1
        done[i] = True

ans = cost1
bi = 0
bj = 1
if N>1000:
  while bj<N:
      if bi>=bj:
          bj = bi+1
          continue
      b,i = B[bi]
      if done[i]:
          bi += 1
          continue
      c,j = B[bj]
      if done[j]:
          bj += 1
          continue
      if U.is_united(i,j):
          bj += 1
      else:
          ans += b + c
          done[i] = True
          done[j] = True
          U.merge(i,j)
          bi += 1
          bj += 1
else:
  1/0

for b,i in B:
    if count1 == 0: break
    if done[i]:continue
    ans += b
    count1 -= 1

if N//2 + M < N-1:
    ans = "Impossible"
elif N==1:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]
B = sorted([(a,i) for i,a in enumerate(A)])

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
        self.Size = [1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def get_Size(self,n):
        n = self.get_Parent(n)
        return self.Size[n]
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.Parent[y] = x
            self.Size[x] += self.Size[y]
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    U.merge(x,y)

cost1 = 0
count1 = 0
done = [False]*N
for i,a in enumerate(A):
    if U.get_Size(i)==1:
        cost1 += a
        count1 += 1
        done[i] = True

ans = cost1
bi = 0
bj = 1
while bj<N:
    if bi>=bj:
        bj = bi+1
        continue
    b,i = B[bi]
    if done[i]:
        bi += 1
        continue
    c,j = B[bj]
    if done[j]:
        bj += 1
        continue
    if U.is_united(i,j):
        bj += 1
    else:
        ans += b + c
        done[i] = True
        done[j] = True
        U.merge(i,j)
        bi += 1
        bj += 1

for b,i in B:
    if count1 == 0: break
    if done[i]:continue
    ans += b
    count1 -= 1

if N//2 + M < N-1:
    ans = "Impossible"
    1/0
elif N==1:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappop
from collections import defaultdict

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


N, M, *L = map(int, open(0).read().split())
A, XY = L[:N], L[N:]

uf = UnionFind(N)
for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y)

C = defaultdict(list)
for i, a in enumerate(A):
    C[uf.find(i)].append(a)

if len(C) < 2:
    print(0)
    quit()

D = [sorted(c) for c in C.values()]
s = sum(heappop(d) for d in D)

L = []
for d in D:
    L += d

if len(L) < len(D) - 2:
    print("Impossible")
else:
    print(s + sum(sorted(D)[:len(D) - 2]))