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:
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 <= 2:
    print(0)
  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()
if len(t) < c - 2:
  print("Impossible")
  exit(0)
for i in range(max(0, c - 2)): res += t[i]
print(res)

Submission status: Wrong Answer

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():
    ans += min(d[k])

l = []

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N)]

for x,y in XY:
    data[x].append(y)
    data[y].append(x)
visitedlst=[]

ittenai=set([i for i in range(0,N)])
while ittenai:
    q=ittenai.pop()
    stack=[q]
    visited=set()
    visited.add(q)
    while stack:
        q=stack.pop()
        for p in data[q]:
            if p not in visited:
                visited.add(p)
                ittenai.remove(p)
                stack.append(p)
    visitedlst.append(visited)
lst=[]
value=0
count=0
for visited in visitedlst:
    visited=sorted([A[i] for i in list(visited)])
    for i in visited[1:]:
        lst.append(i)
    value+=visited[0]
    count+=1
if count==1:
    print(0)

elif len(lst)<(count//2-1+count%2)*2+count%2:
    print("Impossible")
else:
    lst.sort()
    value+=sum(lst[:(count//2-1)*2+count%2])
    print(value)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N)]

for x,y in XY:
    data[x].append(y)
    data[y].append(x)
visitedlst=[]

ittenai=set([i for i in range(0,N)])
while ittenai:
    q=ittenai.pop()
    stack=[q]
    visited=set()
    visited.add(q)
    while stack:
        q=stack.pop()
        for p in data[q]:
            if p not in visited:
                visited.add(p)
                ittenai.remove(p)
                stack.append(p)
    visitedlst.append(visited)
lst=[]
value=0
count=0
for visited in visitedlst:
    visited=sorted([A[i] for i in list(visited)])
    for i in visited[1:]:
        lst.append(i)
    value+=visited[0]
    count+=1
if count==1:
    print(0)

elif len(lst)<(count//2-1+count%2)*2:
    print("Impossible")
else:
    lst.sort()
    value+=sum(lst[:(count//2-1+count%2)*2])
    print(value)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N)]

for x,y in XY:
    data[x].append(y)
    data[y].append(x)
visitedlst=[]

ittenai=set([i for i in range(0,N)])
while ittenai:
    q=ittenai.pop()
    stack=[q]
    visited=set()
    visited.add(q)
    while stack:
        q=stack.pop()
        for p in data[q]:
            if p not in visited:
                visited.add(p)
                ittenai.remove(p)
                stack.append(p)
    visitedlst.append(visited)
lst=[]
value=0
count=0
for visited in visitedlst:
    visited=sorted([A[i] for i in list(visited)])
    for i in visited[1:]:
        lst.append(i)
    value+=visited[0]
    count+=1
print(count,len(lst))
if count==1:
    print(0)

elif len(lst)<(count//2-1+count%2)*2:
    print("Impossible")
else:
    lst.sort()
    value+=sum(lst[:(count//2-1+count%2)*2])
    print(value)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N)]

for x,y in XY:
    data[x].append(y)
    data[y].append(x)
visitedlst=[]

ittenai=set([i for i in range(0,N)])
while ittenai:
    q=ittenai.pop()
    stack=[q]
    visited=set()
    visited.add(q)
    while stack:
        q=stack.pop()
        for p in data[q]:
            if p not in visited:
                visited.add(p)
                ittenai.remove(p)
                stack.append(p)
    visitedlst.append(visited)
lst=[]
value=0
count=0
for visited in visitedlst:
    visited=sorted([A[i] for i in list(visited)])
    for i in visited[1:]:
        lst.append(i)
    value+=visited[0]
    count+=1
if count==1:
    print(0)

elif len(lst)<count//2-1+count%2:
    print("Impossible")
else:
    lst.sort()
    value+=sum(lst[:count//2-1+count%2])
    print(value)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N)]

for x,y in XY:
    data[x].append(y)
    data[y].append(x)
visitedlst=[]

ittenai=set([i for i in range(0,N)])
while ittenai:
    q=ittenai.pop()
    stack=[q]
    visited=set()
    visited.add(q)
    while stack:
        q=stack.pop()
        for p in data[q]:
            if p not in visited:
                visited.add(p)
                ittenai.remove(p)
                stack.append(p)
    visitedlst.append(visited)
lst=[]
value=0
count=0
for visited in visitedlst:
    visited=sorted([A[i] for i in list(visited)])
    for i in visited[1:]:
        lst.append(i)
    value+=visited[0]
    count+=1
if count==1:
    print(0)

elif N<count*2:
    print("Impossible")
else:
    lst.sort()
    value+=sum(lst[:count//2-1+count%2])
    print(value)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N)]
for x,y in XY:
    data[x].append(y)
    data[y].append(x)


stack=[0]
ittenai=set([i for i in range(1,N)])
visited=set([0])
while stack:
    q=stack.pop()
    for p in data[q]:
        if p not in visited:
            visited.add(p)
            ittenai.remove(p)
            stack.append(p)

visited1=copy.copy(visited)
if not ittenai:
    print(0)
    exit()
visited.clear()
q=ittenai.pop()
stack=[q]
visited.add(q)
while stack:
    q=stack.pop()
    for p in data[q]:
        if p not in visited:
            visited.add(p)
            ittenai.remove(p)
            stack.append(p)

if ittenai:
    print("Impossible")
    exit()

print(min([A[i] for i in visited])+min([A[i] for i in visited1]))

Submission status: Wrong Answer

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
def mergeT(t1,t2):
    if len(T[t1])>=len(T[t2]):
        while T[t2]:
            heapq.heappush(T[t1],heapq.heappop(T[t2]))
        if len(T[t1])==1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap1,(c,v,t1))
        elif len(T[t1])>1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap2,(c,v,t1))
    else:
        while T[t1]:
            heapq.heappush(T[t2],heapq.heappop(T[t1]))
        if len(T[t2])==1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap1,(c,v,t2))
        elif len(T[t2])>1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap2,(c,v,t2))
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:
    heap1 = []
    heap2 = []
    for t in T:
        if len(T[t])==1:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap1,(c,v,t))
        else:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap2,(c,v,t)) 
    cnt = 0
    while heap2:
        c1,v1,t1 = heapq.heappop(heap2)
        if len(heap1)>0 and len(heap2)>0:
            c2,v2,t2 = heapq.heappop(heap2)
            c3,v3,t3 = heapq.heappop(heap1)
            if c3<=c2:
                cnt += c1+c3
                mergeT(t1,t3)
                heapq.heappush(heap2,(c2,v2,t2))
            else:
                cnt += c1+c2
                mergeT(t1,t2)
                heapq.heappush(heap1,(c3,v3,t3))  
        else:
            if len(heap1)==0 and len(heap2)>0:
                c2,v2,t2 = heapq.heappop(heap2)
                cnt += c1+c2
                mergeT(t1,t2)
            elif len(heap2)==0 and len(heap1)>0:
                c2,v2,t2 = heapq.heappop(heap1)
                cnt += c1+c2
                mergeT(t1,t2)
    if len(heap1)>=2:
        c1,v1,t1 = heapq.heappop(heap1)
        c2,v2,t2 = heapq.heappop(heap1)
        cnt += c1+c2
    print(cnt)

Submission status: Wrong Answer

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
def mergeT(t1,t2):
    if len(T[t1])>=len(T[t2]):
        T[t1] += T[t2]
        heapq.heapify(T[t1])
        if len(T[t1])==1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap1,(c,v,t1))
        elif len(T[t1])>1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap2,(c,v,t1))
    else:
        T[t2] += T[t1]
        heapq.heapify(T[t2])
        if len(T[t2])==1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap1,(c,v,t2))
        elif len(T[t2])>1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap2,(c,v,t2))
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:
    heap1 = []
    heap2 = []
    for t in T:
        if len(T[t])==1:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap1,(c,v,t))
        else:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap2,(c,v,t)) 
    cnt = 0
    while heap2:
        c1,v1,t1 = heapq.heappop(heap2)
        if len(heap1)>0 and len(heap2)>0:
            c2,v2,t2 = heapq.heappop(heap2)
            c3,v3,t3 = heapq.heappop(heap1)
            if c3<=c2:
                cnt += c1+c3
                mergeT(t1,t3)
                heapq.heappush(heap2,(c2,v2,t2))
            else:
                cnt += c1+c2
                mergeT(t1,t2)
                heapq.heappush(heap1,(c3,v3,t3))  
        else:
            if len(heap1)==0 and len(heap2)>0:
                c2,v2,t2 = heapq.heappop(heap2)
                cnt += c1+c2
                mergeT(t1,t2)
            elif len(heap2)==0 and len(heap1)>0:
                c2,v2,t2 = heapq.heappop(heap1)
                cnt += c1+c2
                mergeT(t1,t2)
    if len(heap1)>=2:
        c1,v1,t1 = heapq.heappop(heap1)
        c2,v2,t2 = heapq.heappop(heap1)
        cnt += c1+c2
    print(cnt)

Submission status: Wrong Answer

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
def mergeT(t1,t2):
    if len(T[t1])>=len(T[t2]):
        T[t1] += T[t2]
        heapq.heapify(T[t1])
        if len(T[t1])==1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap1,(c,v,t1))
        elif len(T[t1])>1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap2,(c,v,t1))
    else:
        T[t2] += T[t1]
        heapq.heapify(T[t2])
        if len(T[t2])==1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap1,(c,v,t2))
        elif len(T[t2])>1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap2,(c,v,t2))
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:
    heap1 = []
    heap2 = []
    for t in T:
        if len(T[t])==1:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap1,(c,v,t))
        else:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap2,(c,v,t)) 
    cnt = 0
    while len(heap1)+len(heap2)>=2:
        if len(heap1)>0 and len(heap2)>0:
            c1,v1,t1 = heapq.heappop(heap1)
            c2,v2,t2 = heapq.heappop(heap2)
            if c1<=c2:
                cnt += c1+c2
                mergeT(t1,t2)
            else:
                if len(heap2)>0:
                    c3,v3,t3 = heapq.heappop(heap2)
                    if c1<=c3:
                        cnt += c1+c2
                        mergeT(t1,t2)
                        heapq.heappush(heap2,(c3,v3,t3))
                    else:
                        cnt += c2+c3
                        mergeT(t2,t3)
                        heapq.heappush(heap1,(c1,v1,t1))
                else:
                    cnt += c1+c2
                    mergeT(t1,t2)
        else:
            if len(heap1)==0:
                c1,v1,t1 = heapq.heappop(heap2)
                c2,v2,t2 = heapq.heappop(heap2)
                cnt += c1+c2
                mergeT(t1,t2)
            elif len(heap2)==0:
                c1,v1,t1 = heapq.heappop(heap1)
                c2,v2,t2 = heapq.heappop(heap1)
                cnt += c1+c2
    print(cnt)

Submission status: Wrong Answer

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
def mergeT(t1,t2):
    if len(T[t1])>=len(T[t2]):
        T[t1] += T[t2]
        heapq.heapify(T[t1])
        if len(T[t1])==1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap1,(c,v,t1))
        elif len(T[t2])>1:
            c,v = heapq.heappop(T[t1])
            heapq.heappush(heap2,(c,v,t1))
    else:
        T[t2] += T[t1]
        heapq.heapify(T[t2])
        if len(T[t2])==1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap1,(c,v,t2))
        elif len(T[t2])>1:
            c,v = heapq.heappop(T[t2])
            heapq.heappush(heap2,(c,v,t2))
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:
    heap1 = []
    heap2 = []
    for t in T:
        if len(T[t])==1:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap1,(c,v,t))
        else:
            c,v = heapq.heappop(T[t])
            heapq.heappush(heap2,(c,v,t)) 
    cnt = 0
    while len(heap1)+len(heap2)>=2:
        if len(heap1)>0 and len(heap2)>0:
            c1,v1,t1 = heapq.heappop(heap1)
            c2,v2,t2 = heapq.heappop(heap2)
            if c1<=c2:
                cnt += c1+c2
                mergeT(t1,t2)
            else:
                if len(heap2)>0:
                    c3,v3,t3 = heapq.heappop(heap2)
                    if c1<=c3:
                        cnt += c1+c2
                        mergeT(t1,t2)
                        heapq.heappush(heap2,(c3,v3,t3))
                    else:
                        cnt += c2+c3
                        mergeT(t2,t3)
                        heapq.heappush(heap1,(c1,v1,t1))
                else:
                    cnt += c1+c2
                    mergeT(t1,t2)
        else:
            if len(heap1)==0:
                c1,v1,t1 = heapq.heappop(heap2)
                c2,v2,t2 = heapq.heappop(heap2)
                cnt += c1+c2
                mergeT(t1,t2)
            elif len(heap2)==0:
                c1,v1,t1 = heapq.heappop(heap1)
                c2,v2,t2 = heapq.heappop(heap1)
                cnt += c1+c2
                mergeT(t1,t2)
    print(cnt)

Submission status: Wrong Answer

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]
            if len(T[t1])>0:
                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]
            if len(T[t2])>0:
                c3,v3 = heapq.heappop(T[t2])
                heapq.heappush(heap,(c3,v3,t2))
    print(cnt)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

    def root(self, x):
        return self.__root(x)

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@mt
def slv(N, M, A, XY):
    uf = UnionFind()

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

    d = defaultdict(list)
    for i in range(N):
        d[uf.root(i)].append(A[i])

    for v in d.values():
        heapq.heapify(v)

    ans = 0
    while len(d) > 1:
        cand = []
        for k, v in d.items():
            cand.append((v[0], k, v))
        cand.sort(reverse=True)
        l = cand.pop()
        r = cand.pop()
        ans += heapq.heappop(l[2]) + heapq.heappop(r[2])
        del d[l[1]]
        del d[r[1]]
        d[l[1]] = l[2]
        while r[2]:
            heapq.heappush(d[l[1]], heapq.heappop(r[2]))
        if len(d[l[1]]) == 0:
            return 'Impossible'
    return ans



    ans = 0
    return ans


def main():
    N, M = read_int_n()
    A = read_int_n()
    XY = [read_int_n() for _ in range(M)]
    print(slv(N, M, A, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)
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
E = []
for i in range(n):
    E.append((len(F[i]),i))
E = sorted(E,key=lambda x:x[0],reverse=True)
v1 = E[0][1]
v2 = E[0][1]
cnt = 0
while cnt<2:
    v = v1
    if cnt==1:v=v2
    B = [heapq.heappop(F[v])]
    C = []
    for i in range(n):
        if i!=v:
            C.append(heapq.heappop(F[i]))
    C =sorted(C,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 len(F[indb])>0:
            heapq.heappush(B,heapq.heappop(F[indb]))
        if len(F[indc])>0:
            heapq.heappush(B,heapq.heappop(F[indc]))
        if i<n-2 and len(B)==0:
            cost="Impossible"
            break
    if cnt==0 and cost=="impossible":
        cnt += 1
    else:break
print(cost)

Submission status: Wrong Answer

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)
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
E = []
for i in range(n):
    E.append((len(F[i]),i))
E = sorted(E,key=lambda x:x[0],reverse=True)
v = E[0][1]
B = [heapq.heappop(F[v])]
C = []
for i in range(n):
    if i!=v:
        C.append(heapq.heappop(F[i]))
C =sorted(C,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 len(F[indb])>0:
        heapq.heappush(B,heapq.heappop(F[indb]))
    if len(F[indc])>0:
        heapq.heappush(B,heapq.heappop(F[indc]))
    if i<n-2 and len(B)==0:
        cost="Impossible"
        break
print(cost)

Submission status: Wrong Answer

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
    E = []
    for i in range(n):
        E.append((len(F[i]),i))
    E = sorted(E,key=lambda x:x[0],reverse=True)
    v = E[0][1]
    B = [heapq.heappop(F[v])]
    C = []
    for i in range(n):
        if i!=v:
            C.append(heapq.heappop(F[i]))
    C =sorted(C,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 len(F[indb])>0:
            heapq.heappush(B,heapq.heappop(F[indb]))
        if len(F[indc])>0:
            heapq.heappush(B,heapq.heappop(F[indc]))
        if i<n-2 and len(B)==0:
            cost="Impossible"
            break
print(cost)