Problem:


Score : 600 points

Problem Statement

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

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

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

Constraints

1 ≤ N ≤ 100,000

0 ≤ M ≤ N-1

1 ≤ a_i ≤ 10^9

0 ≤ x_i,y_i ≤ N-1

The given graph is a forest.

All input values are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

7

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

Sample Input 2

5 0
3 1 4 1 5

Sample Output 2

Impossible

We can't make the graph connected.

Sample Input 3

1 0
5

Sample Output 3

0

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



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


Sample output:
7

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
if M==N-1:
    print(0)
    exit()
if N<2*(N-M-1):
    print("Impossible")
    exit()
a=[int(i) for i in input().split()]
x=[0 for i in range(M)]
y=[0 for i in range(M)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(M):
    unite(x[i],y[i])
A=[find(i) for i in range(N)]
K=0
D=dict()
for i in range(N):
    if A[i] in D:
        D[A[i]].append((a[i],i))
    else:
        D[A[i]]=[(a[i],i)]
        K+=1
ans=0
b=sorted([(a[i],i) for i in range(N)])
c=[-1 for i in range(N)]
for i in range(N):
    c[b[i][1]]=i
used=[0 for i in range(N)]
for i in D:
    seq=min(D[i])
    ans+=seq[0]
    used[c[seq[1]]]=1
Z=2*(N-M-1)-K
j=0
while(Z>0):
    if used[j]==0:
        ans+=b[j][1]
        Z-=1
    j+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
if M==N-1:
    print(0)
    exit()
if N<2*(N-M-1):
    print("Impossible")
    exit()
a=[int(i) for i in input().split()]
x=[0 for i in range(M)]
y=[0 for i in range(M)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(M):
    unite(x[i],y[i])
A=[find(i) for i in range(N)]
K=0
D=dict()
for i in range(N):
    if A[i] in D:
        D[A[i]].append((a[i],i))
    else:
        D[A[i]]=[(a[i],i)]
        K+=1
ans=0
b=sorted([(a[i],i) for i in range(N)])
c=[-1 for i in range(N)]
for i in range(N):
    c[b[i][1]]=i
used=[0 for i in range(N)]
for i in D:
    seq=min(D[i])
    ans+=seq[0]
    used[c[seq[1]]]=1
Z=2*(N-M-1)-K
j=0
while(Z>0):
    if used[j]==0:
        ans+=a[j]
        Z-=1
    j+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
if N-1==M:
  print(0)
  exit()
A=[int(a) for a in input().split()]
G=[[] for i in range(N)]
inf=float("inf")
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)
Tree=[-1]*N

def BFS(x,n):
  global Tree
  stack=deque([x])
  while stack:
    a=stack.popleft()
    Tree[a]=n
    for b in G[a]:
      if Tree[b]<0:
        stack.append(b)
n=0
for i in range(N):
  if Tree[i]<0:
    BFS(i,n)
    n+=1
    
P=[inf]*(n)
for i in range(N):
  P[Tree[i]]=min(P[Tree[i]],A[i])
P.sort()
ans=sum(P)
P.append(inf)
k=0
for i in range(N):
  if A[i]==P[k]:
    A[i]=inf
    k+=1
A.sort()
if 2*(N-M-1)-n>=N or n>2*(N-M-1) or N-2*(N-M-1)<0:
  print("Impossible")
  exit()
for i in range(2*(N-M-1)-n):
  ans+=A[i]
if ans!=inf:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
if N-1==M:
  print(0)
  exit()
A=[int(a) for a in input().split()]
G=[[] for i in range(N)]
inf=float("inf")
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)
Tree=[-1]*N

def BFS(x,n):
  global Tree
  stack=deque([x])
  while stack:
    a=stack.popleft()
    Tree[a]=n
    for b in G[a]:
      if Tree[b]<0:
        stack.append(b)
n=0
for i in range(N):
  if Tree[i]<0:
    BFS(i,n)
    n+=1
    
P=[inf]*(n)
for i in range(N):
  P[Tree[i]]=min(P[Tree[i]],A[i])
P.sort()
ans=sum(P)
P.append(inf)
Q=[False]*(n)
k=0
for i in range(N):
  if A[i]==P[k]:
    A[i]=inf
    k+=1
A.sort()
if 2*(N-M-1)-n>=N-n:
  print("Impossible")
  exit()
for i in range(2*(N-M-1)-n):
  ans+=A[i]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
par = list(range(N))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        par[y] = x

for _ in range(M):
    unite(*map(int, input().split()))

cost = sorted((v, i) for i, v in enumerate(a))
ans = 0
r = 1
visited = set()
for l in range(N):
    if l >= r:
        r = l + 1
    if l in visited:
        continue

    while r < N and root(cost[l][1]) == root(cost[r][1]):
        r += 1
    if r >= N:
        break
    visited |= {l, r}
    # print(cost[l][1], cost[r][1])
    unite(cost[l][1], cost[r][1])
    ans += cost[l][0] + cost[r][0]

if len(set(root(x) for x in range(N))) == 1:
    print(ans)
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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

UF.all_find()

D = defaultdict(list)
for i in range(N):
    D[UF.par[i]].append(A[i])

ans = 0
for key in D.keys():
    heapq.heapify(D[key])

ans = 0
try:
    while len(D) > 1:
        target = [(-float('inf'), -1), (-float('inf'), -1)]

        for key, value in D.items():
            heapq.heappushpop(target, (-value[0], key))

        ans += heapq.heappop(D[target[0][1]]) + heapq.heappop(D[target[1][1]])
        D[target[0][1]].extend(D[target[1][1]])
        heapq.heapify(D[target[0][1]])
        del D[target[1][1]]
except:
    print("Impossible")
    exit()

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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

UF.all_find()

D = defaultdict(list)
for i in range(N):
    D[UF.par[i]].append(A[i])

ans = 0
for key in D.keys():
    heapq.heapify(D[key])

ans = 0
try:
    while len(D) > 1:
        target = [(-float('inf'), -1), (-float('inf'), -1)]

        for key, value in D.items():
            heapq.heappushpop(target, (-value[0], key))

        ans += heapq.heappop(D[target[0][1]]) + heapq.heappop(D[target[1][1]])
        D[target[0][1]].append(D[target[1][1]])
        del D[target[1][1]]
except:
    print("Impossible")
    exit()

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
aa = inpl()

def Find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def Unite(x,y):	#xとyを繋げる
	x = Find(x)
	y = Find(y)

	if x == y:
		return

	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False

table = [i for i in range(N)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(N)]	#木の長さ

for _ in range(M):
	x,y = inpl()
	Unite(x,y)

ed = defaultdict(int)
tmp = 0
Qs = []

for i in range(N):
	root = Find(i)
	ind = ed[root]
	if ind == 0:
		tmp += 1
		ed[root] = tmp
		tmp_q = [(aa[i],i)]
		heapq.heapify(tmp_q)
		Qs.append(tmp_q)
	else:
		heapq.heappush(Qs[ind-1],(aa[i],i))

ans = 0
zan = (N-M-1)*2

if zan > N:
	print('Impossoble')
elif zan == 0:
	print(0)
else:
	ed = defaultdict(int)
	for i in range(len(Qs)):
		c,i = heapq.heappop(Qs[i])
		ed[i] = 1
		ans += c
		zan -= 1

	aa_dush = []
	for i in range(N):
		if ed[i] == 0:
			aa_dush.append(aa[i])
	aa_dush.sort()

	if zan > 0:
		ans += sum(aa_dush[:zan])

	print(ans)

Submission status: Wrong Answer

Solution code:
def f(L, x):
  if L[x]==x:
    return x
  L[x] = f(L, L[x])
  return L[x]

def u(L, x, y):
  if f(L, x)==f(L, y):
    return
  L[L[x]] = L[y]

N, M = map(int, raw_input().split())
a = map(int, raw_input().split())
x = [0]*M
y = [0]*M
L = range(N)
for i in range(M):
  x[i], y[i] = map(int, raw_input().split())
  u(L, x[i], y[i])
d = {}
for i in range(N):
  fi = f(L, i)
  d[fi] = d.get(fi, [])+[a[i]]
if N<2*(N-M-1):
  print "Impossible"
elif N-M==1:
  print 0
else:
  r = []
  l = []
  for k in d.keys():
    sd = sorted(d[k])
    r.append(sd[0])
    l+=sd[1:]
  print sum(r+l[:N-M-2])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  F[T[r]].append(A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in F:
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[F[j][0], j] for j in range(len(F))])
    first = f0[0]
    for f in f0[1:]:
      if root(RF, f[1]) != root(RF, first[1]):
        second = f
        break
    ans += first[0] + second[0]
    RF[second[1]] = RF[first[1]]
    F[first[1]] = F[first[1]][1:]
    F[second[1]] = F[second[1]][1:]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R[i])
    return R[i]
def union(i, j):
  Ri = root(i)
  Rj = root(j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(i)
F = [sorted([A[j] for j in range(N) if R[j] == i]) for i in list(set(R))]
RF = [i for i in range(len(F))]
def rootf(i):
  if RF[i] == i:
    return i
  else:
    RF[i] = rootf(RF[i])
    return RF[i]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in F:
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[F[j][0], j] for j in range(len(F))])
    first = f0[0]
    for f in f0:
      if rootf(f[1]) != rootf(first[1]):
        second = f
        break
    ans += first[0] + second[0]
    RF[second[1]] = RF[first[1]]
    F[first[1]] = F[first[1]][1:]
    F[second[1]] = F[second[1]][1:]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R[i])
    return R[i]
def union(i, j):
  Ri = root(i)
  Rj = root(j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(i)
F = [sorted([A[j] for j in range(N) if R[j] == i]) for i in list(set(R))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in F:
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[F[j][0], j] for j in range(len(F))])
    ans += f0[0][0] + f0[1][0]
    F[f0[0][1]] = F[f0[0][1]][1:]
    F[f0[1][1]] = F[f0[1][1]][1:]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R[i])
    return R[i]
def union(i, j):
  Ri = root(i)
  Rj = root(j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(i)
F = sorted([A[i] for i in list(set(R))])
print(0 if len(F) == 1 else (sum(F) if len(F) == 2 else 'Impossible'))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R[i])
    return R[i]
def union(i, j):
  Ri = root(i)
  Rj = root(j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(i)
F = sorted([A[i] for i in list(set(R))])
print(0 if len(A) == 1 else (sum(A) if len(A) == 2 else 'Impossible'))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R[i])
    return R[i]
def union(i, j):
  Ri = root(i)
  Rj = root(j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(i)
F = sorted([A[i] for i in list(set(R))])
ans = 0
for a in A[1:]:
  ans += A[0] + a
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in mins.items():
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:len(mins)-2])
  print(ans)
  

class union_find:
  def __init__(self, n):
    self.par = [-1] * n
  def __repr__(self):
    return "union_find({0})".format(self.par)
  def unite(self, x, y):
    if self.root(x) != self.root(y):
      self.par[self.root(x)] = y
  def root(self, x):
    if self.par[x] == -1:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  def same(self, x, y):
    return self.root(x) == self.root(y)

main()

Submission status: Wrong Answer

Solution code:
n = input().split()
num_of_vertice = int(n[0])
num_of_edges   = int(n[1])
costs = list(map(int, input().split()))

islands = []
flag = 0
for e in range(num_of_edges):
    edge = list(map(int, input().split()))
    flag = 0
    for island in islands:
        if (edge[0] in island) or (edge[1] in island):
            island.add(edge[0])
            island.add(edge[1])
            flag = 1
    if flag != 1:
        islands.append({edge[0], edge[1]})


# simplify
simplified = []
flag = 0
for island in islands:
    flag = 1
    for s_is in simplified:
        if len((s_is.intersection(island))) != 0:
            s_is = s_is.union(island)
            flag = 0
            break
    if flag == 1:
        simplified.append(island)

# islations
isolation = set([])
for i in range(num_of_vertice):
    isolation.add(i)
for island in simplified:
    isolation.difference_update(island)

# biggest island
size = 1
for island in simplified:
    size = max(size, len(island))

if (size < len(isolation) + len(simplified)):
    print(size, len(isolation), len(simplified))
    print("Impossible")
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

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

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

  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1<root2:
      self.table[root1]+=self.table[root2]
      self.table[root2]=root1
    else:
      self.table[root2]+=self.table[root1]
      self.table[root1]=root2

N,M=map(int,input().split())
A=[int(i) for i in input().split()]
uf=UnionFind(N)
for i in range(M):
  x,y=map(int,input().split())
  uf.union(x,y)
groups=defaultdict(list)
for j in range(N):
  groups[uf.find(j)].append(A[j])

groups = [sorted(g, reverse=False) for g in groups.values()]

if len(groups) == 1:
  print(0)
  sys.exit()

ans=0
cnt=[]
for group in groups:
  ans+=group[0]
  if len(group)>1:
    cnt.append(group[1])

if len(groups)-2 > len(cnt):
  print("Impossible")
elif len(groups) == 2:
  print(ans)
else:
  cnt.sort()
  ans+=sum(cnt[:len(groups)-2])
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

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

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

  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1<root2:
      self.table[root1]+=self.table[root2]
      self.table[root2]=root1
    else:
      self.table[root2]+=self.table[root1]
      self.table[root1]=root2

N,M=map(int,input().split())
A=[int(i) for i in input().split()]
uf=UnionFind(N)
for i in range(M):
  x,y=map(int,input().split())
  uf.union(x,y)
groups=defaultdict(list)
for j in range(N):
  groups[uf.find(j)].append(A[j])

groups = [sorted(g, reverse=False) for g in groups.values()]

if len(groups) == 1:
  print(0)
  sys.exit()

ans=0
cnt=[]
for group in groups:
  ans+=group[0]
  if len(group)>1:
    cnt.append(group[1])

if len(groups)-2 > len(cnt):
  print("Impossible")
else:
  cnt.sort()
  ans+=sum(cnt[:len(groups)-2])
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

#
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
groups = [[x] for x in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    if b<a:
        a,b = b,a

    ida = -1
    idb = -1
    for i in range(len(groups)):
        if a in groups[i]:
            ida = i
        elif b in groups[i]:
            idb = i
        if ida!=-1 and idb!=-1:
            groups[ida] += groups[idb]
            del groups[idb]
            break

#print(groups)
G = [[] for _ in range(len(groups))]
for i in range(len(groups)):
    for j in groups[i]:
        heappush(G[i], S[j])
#print(G)

#
if len(G)==1:
    print(0)
    exit()
#if M<(len(G)-1)*2:
#    print('Impossible')
#    exit()
need = (len(G)-1)*2
if N<need:
    print('Impossible', N, need)
    exit()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

#
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
groups = [[x] for x in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    id = []
    tmp = -1
    for i in range(len(groups)):
        if a in groups[i]:# and not b in groups[i]:
            id.append(i)
            tmp = b
        if b in groups[i]:# and not a in groups[i]:
            id.append(i)
            tmp = a
    if len(id)==2:
        groups[id[0]] += groups[id[1]]
        del groups[id[1]]
    elif len(id)==1:
        groups[id[0]].append(tmp)
    else:
        groups.append([a, b])
#print(groups)
G = [[] for _ in range(len(groups))]
for i in range(len(groups)):
    for j in groups[i]:
        heappush(G[i], S[j])
print(G)

#
if len(G)==1:
    print(0)
    exit()
#if M<(len(G)-1)*2:
#    print('Impossible')
#    exit()
need = (len(G)-1)*2
if N<need:
    print('Impossible', N, need)
    exit()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

#
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
groups = [[x] for x in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    id = []
    tmp = -1
    for i in range(len(groups)):
        if a in groups[i] and not b in groups[i]:
            id.append(i)
            tmp = b
        if b in groups[i] and not a in groups[i]:
            id.append(i)
            tmp = a
    if len(id)==2:
        groups[id[0]] += groups[id[1]]
        del groups[id[1]]
    elif len(id)==1:
        groups[id[0]].append(tmp)
    else:
        groups.append([a, b])
#print(groups)
G = [[] for _ in range(len(groups))]
for i in range(len(groups)):
    for j in groups[i]:
        heappush(G[i], S[j])
#print(G)

#
if len(G)==1:
    print(0)
    exit()
if M<(len(G)-1)*2:
    print('Impossible')
    exit()
need = (len(G)-1)*2
if N<need:
    print('Impossible')
    exit()

#
ans = 0
rest = []
for g in G:
    ans += heappop(g)
    for i in g:
        heappush(rest, i)
need -= len(G)
if len(rest)<need:
    print('Impossible')
    exit()

ans += sum(rest[:need])
#print(ans, G)
# for i in range(need):
#     tmp = [g[0] for g in G]
#     m = min(tmp)
#     ans += m
#     id = tmp.index(m)
#     pushpop(G[id])#del G[id][0]
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

#
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
groups = [[x] for x in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    id = []
    tmp = -1
    for i in range(len(groups)):
        if a in groups[i] and not b in groups[i]:
            id.append(i)
            tmp = b
        if b in groups[i] and not a in groups[i]:
            id.append(i)
            tmp = a
    if len(id)==2:
        groups[id[0]] += groups[id[1]]
        del groups[id[1]]
    elif len(id)==1:
        groups[id[0]].append(tmp)
    else:
        groups.append([a, b])
#print(groups)
G = [[] for _ in range(len(groups))]
for i in range(len(groups)):
    for j in groups[i]:
        heappush(G[i], S[j])
#print(G)

#
if len(G)==1:
    print(0)
    exit()
if M<(len(G)-1)*2:
    print('Impossible')
    exit()
need = (len(G)-1)*2
rest = N
if rest<need:
    print('Impossible')
    exit()

#
ans = 0
for g in G:
    ans += heappop(g)
need -= len(G)
rest -= len(G)
if rest<need:
    print('Impossible')
    exit()

#print(ans, G)
for i in range(need):
    tmp = [g[0] for g in G]
    m = min(tmp)
    ans += m
    id = tmp.index(m)
    del G[id][0]
print(ans)

Submission status: Wrong Answer

Solution code:
#
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
groups = [[x] for x in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    id = []
    tmp = -1
    for i in range(len(groups)):
        if a in groups[i] and not b in groups[i]:
            id.append(i)
            tmp = b
        if b in groups[i] and not a in groups[i]:
            id.append(i)
            tmp = a
    if len(id)==2:
        groups[id[0]] += groups[id[1]]
        del groups[id[1]]
    elif len(id)==1:
        groups[id[0]].append(tmp)
    else:
        groups.append([a, b])
#print(groups)
G = []
for g in groups:
    G.append(sorted([S[i] for i in g]))
#print(G)

#
if len(G)==1:
    print(0)
    exit()
if M<(len(G)-1)*2:
    print('Impossible')
    exit()

#
ans = 0
for g in G:
    ans += g[0]
    del g[0]
#print(ans, G)
for i in range((len(G)-1)*2-len(G)):
    tmp = [g[0] for g in G]
    m = min(tmp)
    ans += m
    id = tmp.index(m)
    del G[id][0]
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify, nsmallest

N, M = map(int, input().split())
costs = list(map(int, input().split()))
treemin = [(cost, i) for i, cost in enumerate(costs)] # グループ内での最小値

parent = list(range(N))
rank = [0] * (N)
def getRoot(x):
  if parent[x] == x:
    return x
  else:
    # ルートに繋ぎ変える
    parent[x] = getRoot(parent[x])
    return parent[x]

def unite(x, y):
  global treemin
  xRoot = getRoot(x)
  yRoot = getRoot(y)
  if xRoot == yRoot:
    return
  if rank[xRoot] < rank[yRoot]:
    parent[xRoot] = yRoot
    if treemin[yRoot][0] > treemin[xRoot][0]:
      treemin[yRoot] = treemin[xRoot]
  else:
    parent[yRoot] = xRoot
    if treemin[xRoot][0] > treemin[yRoot][0]:
      treemin[xRoot] = treemin[yRoot]
    if rank[xRoot] == rank[yRoot]:
      rank[xRoot] += 1

for i in range(M):
  x, y = map(int, input().split())
  unite(x, y)

ans = 0
numtree = 0
numsingle = 0
exclude = set()
for i in range(N):
  if parent[i] == i:
    numtree += 1
    if rank[i] == 0:
      ans += costs[i]
      numsingle += 1
      exclude.add(i)
    else:
      ans += treemin[i][0]
      exclude.add(treemin[i][1])

if N < (numtree-1) * 2:
  print('Impossible')
  exit()
if numtree == 1:
  print(0)
  exit()

heap = []
for i in range(N):
  if i not in exclude:
    heappush(heap, costs[i])

ans += sum(nsmallest(numtree - numsingle - 2, heap))
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
src = list(map(int,input().split()))
es = [tuple(map(int,input().split())) for i in range(M)]

if N == 1:
    print(0)
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    root(i)
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
src = list(map(int,input().split()))
es = [tuple(map(int,input().split())) for i in range(M)]

if N == 1:
    print(0)
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)