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 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 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
    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 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-1 and len(B)==0:
            cost="Impossible"
            break
print(cost)

Submission status: Wrong Answer

Solution code:
#############################################################
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

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

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

    def all_group_members(self):
        # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
################################################################################
def examD():
    N, M = LI()
    a = LI()
    A = []
    for i,j in enumerate(a):
        A.append([j,i])
    A.sort()
    uf = UnionFind(N)
    for i in range(M):
        x,y = LI()
        if not uf.same(x,y):
            uf.union(x,y)
    keep = deque([A[0][0]]); cur = A[0][1]
    loop = uf.group_count()
    ans = 0
    for _ in range(loop-1):
        for j in range(1,N):
            if uf.same(cur,A[j][1]):
                keep.append(A[j][0])
            else:
                if keep:
                    ans += (keep.popleft()+A[j][0])
                    uf.union(cur,j)
    if uf.group_count()!=1:
        print("Impossible")
    else:
        print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

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

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:
  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 = bi + 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"
elif N==1:
    ans = 0
print(ans)

Submission status: Wrong Answer

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
for _ in range(2):
  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"
elif N==1:
    ans = 0
print(ans)

Submission status: Wrong Answer

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"
elif N==1:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
print("Impossible")

Submission status: Wrong Answer

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

import heapq

class UnionFind:
    def __init__(self,N,A):
        self.Parent = [-1]*N
        self.Cost = [[a] for a in A]
    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 merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y:
            self.Parent[y] = x
            for a in self.Cost[y]:
                heapq.heappush(self.Cost[x],a)
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

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

ans = 0
roots = [i for i,p in enumerate(U.Parent) if p==-1]
costs = []
hpush = heapq.heappush
hpop = heapq.heappop
for i in roots:
    hpush(costs,(U.Cost[i][0],i))
while len(costs)>2:
    reserve = []
    ci,i = hpop(costs)
    cj,j = hpop(costs)
    while len(U.Cost[i])==1 and len(U.Cost[j])==1:
        if len(costs)==0:
            ans = None
            break
        reserve.append((cj,j))
        cj,j = hpop(costs)
    if ans == None:break
    ans += hpop(U.Cost[i]) + hpop(U.Cost[j])
    U.merge(i,j)
    hpush(costs,(U.Cost[i][0],i))
    for r in reserve:
        hpush(costs,r)
if ans == None: print("Impossible")
else:
    if len(costs)>1:ans += costs[0][0] + costs[1][0]
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque


n, m = map(int, input().split())
a = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]

for b, c in info:
    tree[b].append(c)
    tree[c].append(b)

visited = [False] * n
group = []
for i in range(n):
    if visited[i]:
        continue
    q = deque([i])
    visited[i] = True
    tmp = [a[i]]
    while q:
        pos = q.pop()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            q.append(next_pos)
            tmp.append(a[next_pos])
    group.append(tmp)

for i in range(len(group)):
    group[i] = sorted(group[i])

ans = 0
cnt = len(group)*2 - 2

if cnt == 0:
    print(0)
    exit()
    
for i in range(len(group)):
    ans += group[i][0]
    cnt -= 1
    group[i][0] = 10**9 + 7

q = []
for i in range(len(group)):
    for num in group[i]:
        if num != 10**9 +7:
            heapq.heappush(q, num)
print(1)
exit()
for i in range(cnt):
    if not q:
        print("Impossible")
        exit()
    ans += heapq.heappush(q)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def wantp(n):

    wpq = []
    while n != p[n]:
        wpq.append(n)
        n = p[n]

    for i in wpq:
        p[i] = n

    return n


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

a = list(map(int,input().split()))


p = [i for i in range(N)]
rank = [1] * N

dic = {}

ans = 0

for i in range(M):

    x,y = map(int,input().split())

    xp = wantp(x)
    yp = wantp(y)

    if xp != yp:

        if rank[xp] < rank[yp]:
            p[xp] = yp
        elif rank[xp] > rank[yp]:
            p[yp] = xp
        else:
            p[yp] = xp
            rank[yp] += 1

for i in range(N):

    now = i
    np = wantp(now)

    if np not in dic:
        dic[np] = [float("inf"),float("inf"),float("inf")]

    if dic[np][1] > a[i]:
        dic[np][2] = dic[np][1]
        dic[np][1] = a[i]

    elif dic[np][2] > a[i]:
        dic[np][2] = a[i]

    if dic[np][2] == float("inf"):
        dic[np][0] = dic[np][1]
    else:
        dic[np][0] = dic[np][1] + dic[np][2]


lis = []

for i in dic:
    lis.append(dic[i])

lis.sort()
lis.reverse()
#print (lis,p)

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

elif len(lis) - 1 > N // 2:
    print ("Impossible")
    sys.exit()

for i in range(len(lis)):

    if i <= 1:
        ans += lis[i][1]
    else:
        ans += lis[i][0]

print (ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

import heapq as hp
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
uni = UnionFind(N-1)
for _ in range(M):
    a, b = map(int, input().split())
    uni.Unite(a, b)

root = {}
for i in range(N):
    r = uni.Find_Root(i)
    if not r in root.keys():
        root[r] = [A[i]]
    else:
        hp.heappush(root[r], A[i])

q = []
ok = True
ans = 0
for i, L in enumerate(root.values()):
    if i == 0:
        for a in L:
            hp.heappush(q, a)
    else:
        if not q:
            ok = False
            break
        a1 = hp.heappop(q)
        a2 = hp.heappop(L)
        ans += a1 + a2
        for a in L:
            hp.heappush(q, a)
if not ok:
    print("Impossible")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(10**7)

show_flg=False
show_flg=True

n,m=LI()
a=LI()
g=[[] for _ in range(n)]
ans=0
cmp=0
for i in range(m):
    x,y=LI()
    g[x].append(y)
    g[y].append(x)

rest=[]
q=[]
v=[-1]*n

for i in range(n):
    if v[i]>0:
        continue
    p=[]
    cost=[]
    p.append(i)
    heappush(cost,a[i])
    while p:
        c=p.pop()
        v[c]=a[c]
        for nb in g[c]:
            if v[nb]==-1:
                p.append(nb)
                v[nb]=a[nb]
                heappush(cost,a[nb])
    ans+=heappop(cost)
    cmp+=1
    while cost:
        heappush(rest,heappop(cost))
    
if len(rest)<cmp-1:
    ans="Impossible"
elif cmp==1:
    ans=0
else:
    for i in range(cmp-2):
        ans+=heappop(rest)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(10**7)

show_flg=False
show_flg=True

n,m=LI()
a=LI()
g=[[] for _ in range(n)]
ans=0
cmp=0
for i in range(m):
    x,y=LI()
    g[x].append(y)
    g[y].append(x)

rest=[]
q=[]
v=[-1]*n

for i in range(n):
    if v[i]>0:
        continue
    p=[]
    cost=[]
    p.append(i)
    while p:
        c=p.pop()
        v[c]=a[c]
        heappush(cost,a[c])
        for nb in g[c]:
            if v[nb]==-1:
                p.append(nb)
                v[nb]=a[nb]
                heappush(cost,a[nb])
    ans+=heappop(cost)
    cmp+=1
    while cost:
        heappush(rest,heappop(cost))
    
if len(rest)<cmp-1:
    ans="Impossible"
elif cmp==1:
    ans=0
else:
    for i in range(cmp-2):
        ans+=heappop(rest)

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self,size):
    self.table=[-1]*size
  def root(self,x):
    while self.table[x]>=0:
      x=self.table[x]
    return x
  def unite(self,x,y):
    s1=self.root(x)
    s2=self.root(y)
    if s1!=s2:
      if self.table[s1]>self.table[s2]:
        s1,s2=s2,s1
      self.table[s1]+=self.table[s2]
      self.table[s2]=s1
  def same(self,x,y):
    return self.root(x)==self.root(y)
  def size(self,x):
    return -self.table[self.root(x)]
from collections import*
from heapq import*
def main():
  n,m,*a=map(int,open(0).read().split())
  u=UnionFind(n)
  d=defaultdict(list)
  for x,y in zip(*[iter(a[n:])]*2):u.unite(x,y)
  for i,v in enumerate(a[:n]):d[u.root(i)]+=v,
  *h,=map(sorted,d.values())
  heapify(h)
  p=heappop
  c=0
  while len(h)>1:
    x,y=p(h),p(h)
    if not x or not y:
      print('Impossible')
      exit()
    c+=p(x)+p(y)
    heappush(h,list(merge(x,y)))
  print(c)
main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self,size):
    self.table=[-1]*size
  def root(self,x):
    while self.table[x]>=0:
      x=self.table[x]
    return x
  def unite(self,x,y):
    s1=self.root(x)
    s2=self.root(y)
    if s1!=s2:
      if self.table[s1]>self.table[s2]:
        s1,s2=s2,s1
      self.table[s1]+=self.table[s2]
      self.table[s2]=s1
  def same(self,x,y):
    return self.root(x)==self.root(y)
  def size(self,x):
    return -self.table[self.root(x)]
from collections import*
from heapq import*
n,m,*a=map(int,open(0).read().split())
u=UnionFind(n)
d=defaultdict(list)
for x,y in zip(*[iter(a[n:])]*2):
  u.unite(x,y)
for i,v in enumerate(a[:n]):
  heappush(d[u.root(i)],v)
*h,=d.values()
heapify(h)
p=heappop
c=0
while len(h)>1:
  x,y=p(h),p(h)
  if not x or not y:
    print('Impossible')
    exit()
  c+=p(x)+p(y)
  heappush(h,list(merge(x,y)))
print(c)