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())

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

union=[-1]*n

tree=[[] for _ in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    tree[x].append(y)
    tree[y].append(x)

cnt=-1
for i in range(n):
    if union[i]==-1:
        stack=[i]
        cnt+=1
        while len(stack)>0:
            tmp=stack.pop()
            union[tmp]=cnt
            for item in tree[tmp]:
                if union[item]==-1:
                    union[item]=cnt
                    stack.append(item)

if cnt==0:
    print(0)
    exit()

cost=[[] for _ in range(cnt+1)]
#print(union)
for i,aa in enumerate(a):
    cost[union[i]].append(aa)

import heapq
heapq.heapify(cost[0])


ans=0
del_list=[]
#print(cost)
for i in range(1,cnt+1):
    while 1:
        if len(cost[0])>0:
            tmp=heapq.heappop(cost[0])
        else:
            print("Impossible")
            exit()
        if len(del_list)>0 and tmp==del_list[0]:
            heapq.heappop(del_list)
            
        else:
            break
            

    tmp2=min(cost[i])
    ans+=tmp+tmp2
    heapq.heappush(del_list,tmp2)
    cost[0]=cost[0]+cost[i]
    heapq.heapify(cost[0])

    #print(cost)

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    '''
    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 is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush, heapify
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x, y)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    if N - 1 == M:
        print(0)
        return
    node = [0] * N
    qtable = [[] for _ in range(N)]
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(qtable[node[i]], A[i])
    allq = []
    ans = 0
    for i in range(N):
        if qtable[i]:
            ans += heappop(qtable[i])
        allq.extend(qtable[i])

    heapify(allq)
    for i in range(select_node-N):
        ans += heappop(allq)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    '''
    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 is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x, y)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    node = [0] * N
    q = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(q, (A[i], i))
    ans = 0
    try:
        for i in range(N-M-1):
            a, n = heappop(q)
            tmpa, tmpn = heappop(q)
            while union.is_same_group(tmpn, n):
                tmpa, tmpn = heappop(q)
            ans += a + tmpa
            union.unite(tmpn, n)
        print(ans)
    except:
        print("Impossible")

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    A=LI()
    if (N-2)//2 >= M:
        print("Impossible")
        exit()
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

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

            if x == y:
                return

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

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

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

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

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

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

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

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

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


    """
    まずufで連結成分を把握
    各連結成分ごとにheapqを用意
    最小2つをくっつける(要素数が小さい方を大きい方へ)
    要素の削除が重そう？要素数が大きいものや最小値が大きいものを手前に置いておくとか？
    """
    
    uf=UnionFind(N)
    for i in range(M):
        x,y=MI()
        uf.union(x,y)
    roots=uf.roots()
    Nr=len(roots)
    
    #rootsと番号の対応
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(len(roots)):
        dd[roots[i]]=i
    
    import heapq
    L=[]
    for i in range(Nr):
        L.append([])
    
    for i in range(N):
        root=uf.find(i)
        heapq.heappush(L[dd[root]],A[i])
        
    need = Nr-1
    
    ans=0
    inf=10**9+1
    for _ in range(need):
        min1=[inf,-1]
        min2=[inf+1,-1]
        for i in range(len(L)-1,-1,-1):
            a=heapq.heappop(L[i])
            if a<min1[0]:
                min2=[min1[0],min1[1]]
                min1=[a,i]
            elif a<min2[0]:
                min2=[a,i]
            heapq.heappush(L[i],a)
                
        ans+=min1[0]+min2[0]
        i1=min1[1]
        i2=min2[1]
        
        if i1>i2:
            i1,i2=i2,i1
        
        while L[i2]:
            aaa=heapq.heappop(L[i2])
            heapq.heappush(L[i1],aaa)
        L.pop(i2)
        
    print(ans)
            
        
                
        
    
    
    
    
    
    
    
        

main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)

    # 検索
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

def main():
    n, m = getList()
    uf = UnionFind(n)
    costs = getList()

    q = []
    for i, c in enumerate(costs):
        heapq.heappush(q, (c, i))
    # print(q)
    hen = 0
    for _ in range(m):
        a, b = getList()
        if not uf.same_check(a, b):
            uf.union(a,b)
            hen += 1
 
    # print(uf.par)
    ans = 0
    used = defaultdict(int)
    kaburi = []
    mc = 0
    while(q):
        c1, m1 = heapq.heappop(q)
        if uf.find(m1) not in used.keys():
            ans += c1
            used[uf.find(m1)] = 1
            mc += 1
        else:
            heapq.heappush(kaburi, (c1, m1))

    # print(kaburi, hen, ans)

    if len(kaburi) >= 2 * (n - hen - 1) - mc:
        for _ in range(2 * (n - hen - 1) - mc):
            c1, m1 = heapq.heappop(kaburi)
            ans += c1
        print(ans)
        return 
    else:
        print("Impossible")
        return


if __name__ == "__main__":
    main()
    # solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)

    # 検索
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

def main():
    n, m = getList()
    uf = UnionFind(n)
    costs = getList()

    q = []
    for i, c in enumerate(costs):
        heapq.heappush(q, (c, i))
    # print(q)
    hen = 0
    for _ in range(m):
        a, b = getList()
        if not uf.same_check(a, b):
            uf.union(a,b)
            hen += 1
 
    # print(uf.par)
    ans = 0
    used = defaultdict(int)
    kaburi = []
    mc = 0
    while(q):
        c1, m1 = heapq.heappop(q)
        if m1 not in used.keys():
            ans += c1
            used[m1] = 1
            mc += 1
        else:
            heapq.heappush(kaburi, (c1, m1))

    if len(kaburi) >= 2 * (n - hen - 1):
        for _ in range(2 * (n - hen - 1)):
            c1, m1 - heapq.heappop(q)
            ans += c1
        print(ans)
        return 
    else:
        print("Impossible")
        return


if __name__ == "__main__":
    main()
    # solve()

Submission status: Wrong Answer

Solution code:
# union-find + heap→heap分はsortで対応
# 不可能ケースは点が2箇所以上？
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())
graph = [[] for _ in range(n)]
A = list(map(int, readline().split()))
B = [(0, 0)] * n
for idx, val in enumerate(A):
    B[idx] = (-val, idx)
B.sort()
z = map(int, read().split())
XY = zip(z, z)

# union-Find##
par = [-1] * (n + 1)


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


def unite(x, y):
    a = root(x)
    b = root(y)
    if a == b:
        return False
    else:
        if par[a] > par[b]:
            a, b = b, a
        par[a] += par[b]
        par[b] = a
        return True


def is_same(x, y):
    return root(x) == root(y)


def size(x):
    return -par[root(x)]


for x, y in XY:
    unite(x, y)

cnt = 0
jisho = defaultdict(list)
for i in range(n):
    r = root(i)
    jisho[r].append(A[i])
    if i == r:
        cnt += 1
if cnt == 1:
    print(0)
    exit()
# print(cnt)
kouho = []
ans = 0
for par, lis in jisho.items():
    lis.sort(reverse=True)
    v = lis.pop()
    ans += v
    kouho += lis


if (n - 1) - (cnt + m) > len(kouho):
    print("Impossible")
    exit()
kouho.sort()
for i in range((n - 1) - (cnt + m)):
    ans += kouho[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
XY = [[int(x) for x in input().split()] for _ in range(M)]

if N == 1:
    print(0)
    exit()

if M == 0:
    print("Impossible")
    exit()


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


u = UnionFind(N)

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

groupc = u.group_count()
if N < (groupc - 1) * 2:
    print("Impossible")
    exit()

B = [[] for j in range(u.group_count())]

for i, x in enumerate(u.roots()):
    for m in u.members(x):
        B[i].append(A[m])

    B[i].sort()

ans = 0

q = []
for b in B:
    ans += b[0]
    for bb in b[1:]:
        q.append(bb)

q.sort()
for i in range((groupc - 1) * 2 - groupc):
    ans += q[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)

    # 検索
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

def main():
    n, m = getList()
    uf = UnionFind(n)
    costs = getList()

    q = []
    for i, c in enumerate(costs):
        heapq.heappush(q, (c, i))
    # print(q)
    for _ in range(m):
        a, b = getList()
        if not uf.same_check(a, b):
            uf.union(a,b)
 
    # print(uf.par)
    kaburi = []
    ans = 0
    c1, m1 = heapq.heappop(q)
    while(q):
        c2, m2 = heapq.heappop(q)
        # print(c1,m1,c2,m2)
        if not uf.same_check(m1,m2):
            uf.union(m1, m2)
            ans += c1 + c2
            if kaburi:
                c1, m1 = heapq.heappop(kaburi)
            elif q:
                c1, m1 = heapq.heappop(q)
        else:
            heapq.heappush(kaburi, (c2, m2))



    # print(uf.par)
    p0 = uf.find(0)
    for i in range(1, n):
        if not uf.find(i) == p0:
            print("Impossible")
            return
    print(ans)




if __name__ == "__main__":
    main()
    # solve()

Submission status: Wrong Answer

Solution code:
# union-find + heap→heap分はsortで対応
# 不可能ケースは点が2箇所以上？

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())
graph = [[] for _ in range(n)]
A = list(map(int, readline().split()))
B = [(0, 0)] * n
for idx, val in enumerate(A):
    B[idx] = (-val, idx)
B.sort()
z = map(int, read().split())
XY = zip(z, z)

# union-Find##
par = [-1] * (n + 1)


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


def unite(x, y):
    a = root(x)
    b = root(y)
    if a == b:
        return False
    else:
        if par[a] > par[b]:
            a, b = b, a
        par[a] += par[b]
        par[b] = a
        return True


def is_same(x, y):
    return root(x) == root(y)


def size(x):
    return -par[root(x)]


for x, y in XY:
    unite(x, y)

cnt = 0
for i in range(n):
    if i == root(i):
        cnt += 1
if cnt == 1:
    print(0)
    exit()
# print(cnt)
ans = 0
f_v = 0
out_flag = 0
while cnt > 1:
    # print(cnt)
    if not B:
        out_flag = 1
        break
    hazure = []
    if f_v == 0:
        f_v, f_i = B.pop()
    while B:
        s_v, s_i = B.pop()
        # print("F", f_v, f_i)
        # print("S", s_v, s_i)
        if is_same(f_i, s_i):
            hazure.append((s_v, s_i))
        else:
            ans += -(f_v + s_v)
            unite(f_i, s_i)
            cnt -= 1
            f_v = 0
            break
    B += hazure

if out_flag:
    print("Impossible")
else:
    print(ans)

Submission status: Wrong Answer

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

if N==1:
    print(0)
    exit()

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)
for x,y in XY:
    if uf.is_same(x,y): continue
    uf.unite(x,y)
for i in range(N):
    uf.root(i)

from collections import defaultdict
dic = defaultdict(lambda: set())
for i in range(N):
    dic[uf.root(i)].add(i)

need = (len(dic)-1)*2
if need > N:
    print('Impossible')
    exit()

ans = used = 0
import heapq
hq = []
heapq.heapify(hq)
for r,vs in dic.items():
    mini = -1
    mina = 10**9+1
    for i in vs:
        if A[i] < mina:
            mina = A[i]
            mini = i
    ans += mina
    used += 1
    for i in vs:
        if i==mini: continue
        heapq.heappush(hq, A[i])

for _ in range(need - used):
    ans += heapq.heappop(hq)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)

    # 検索
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

def main():
    n, m = getList()
    uf = UnionFind(n)
    costs = getList()

    q = []
    for i, c in enumerate(costs):
        heapq.heappush(q, (c, i))
    # print(q)
    for _ in range(m):
        a, b = getList()
        if not uf.same_check(a, b):
            uf.union(a,b)

    # print(uf.par)

    ans = 0
    c1, m1 = heapq.heappop(q)
    while(q):
        c2, m2 = heapq.heappop(q)
        # print(c1,m1,c2,m2)
        if not uf.same_check(m1,m2):
            uf.union(m1, m2)
            ans += c1 + c2
            if q:
                c1, m1 = heapq.heappop(q)

    # print(uf.par)
    p0 = uf.find(0)
    for i in range(1, n):
        if not uf.find(i) == p0:
            print("Impossible")
            return
    print(ans)




if __name__ == "__main__":
    main()
    # solve()

Submission status: Wrong Answer

Solution code:
# union-find + heap→heap分はsortで対応
# 不可能ケースは点が2箇所以上？

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())
graph = [[] for _ in range(n)]
A = list(map(int, readline().split()))
B = [(0, 0)] * n
for idx, val in enumerate(A):
    B[idx] = (-val, idx)
B.sort()
z = map(int, read().split())
XY = zip(z, z)

# union-Find##
par = [-1] * (n + 1)


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


def unite(x, y):
    a = root(x)
    b = root(y)
    if a == b:
        return False
    else:
        if par[a] > par[b]:
            a, b = b, a
        par[a] += par[b]
        par[b] = a
        return True


def is_same(x, y):
    return root(x) == root(y)


def size(x):
    return -par[root(x)]


for x, y in XY:
    unite(x, y)

cnt = 0
for i in range(n):
    if i == root(i):
        cnt += 1
if cnt == 1:
    print(0)
    exit()
# print(cnt)
ans = 0
f_v = 0
out_flag = 0
while cnt > 1:
    # print(cnt)
    if not B:
        out_flag = 1
        break
    hazure = []
    if f_v == 0:
        f_v, f_i = B.pop()
    while B:
        s_v, s_i = B.pop()
        # print("F", f_v, f_i)
        # print("S", s_v, s_i)
        if is_same(f_i, s_i):
            hazure.append((s_v, s_i))
        else:
            ans += -(f_v + s_v)
            cnt -= 1
            f_v = 0
            break
    B += hazure

if out_flag:
    print("Impossible")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# union-find + heap→heap分はsortで対応
# 不可能ケースは点が2箇所以上？

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())
graph = [[] for _ in range(n)]
A = list(map(int, readline().split()))
B = [(0, 0)] * n
for idx, val in enumerate(A):
    B[idx] = (-val, idx)
B.sort()
z = map(int, read().split())
XY = zip(z, z)

# union-Find##
par = [-1] * (n + 1)


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


def unite(x, y):
    a = root(x)
    b = root(y)
    if a == b:
        return False
    else:
        if par[a] > par[b]:
            a, b = b, a
        par[a] += par[b]
        par[b] = a
        return True


def is_same(x, y):
    return root(x) == root(y)


def size(x):
    return -par[root(x)]


for x, y in XY:
    unite(x, y)

cnt = 0
for i in range(n):
    if i == root(i):
        cnt += 1
if cnt == 1:
    print(0)
    exit()
# print(cnt)
ans = 0
f_v = 0
out_flag = 0
while cnt > 1:
    print(cnt)
    if not B:
        out_flag = 1
        break
    hazure = []
    if f_v == 0:
        f_v, f_i = B.pop()
    while B:
        s_v, s_i = B.pop()
        # print("F", f_v, f_i)
        # print("S", s_v, s_i)
        if is_same(f_i, s_i):
            hazure.append((s_v, s_i))
        else:
            ans += -(f_v + s_v)
            cnt -= 1
            f_v = 0
            break
    B += hazure

if out_flag:
    print("Impossible")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*(n-m-1) > n:
    print("Impossible")
    exit()

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

u = Unionfind(n)
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    u.union(x,y)

l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        l[i].append(a[i])
    else:
        l[x].append(a[i])

ans = 0
h = []
for i in range(n):
    if l[i]:
        l[i].sort()
        ans += l[i][0]
        for j in l[i][1:]:
            h.append(j)
h.sort()
ans += sum(h[:2*(n-m-1)-n])
print(ans)

Submission status: Wrong Answer

Solution code:

n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*(n-m-1) > n:
    print("Impossible")
    exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque

n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*m < n:
    print("Impossible")
    exit()

e = [[] for i in range(n)]
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    e[x].append(y)
    e[y].append(x)

def dfs(x):
    l = []
    d[x] = 1
    l.append(a[x])
    q = deque([])
    q.append(x)
    while q:
        now = q.pop()
        for nex in e[now]:
            if d[nex] > 0:
                continue
            l.append(a[nex])
            d[nex] = 1
            q.append(nex)
    l.sort()
    ans = l[0]
    
    for i in l[1:]:
        h.append(i)
    return ans
count = 2*(n-m-1)
d = [-1]*n
ans = 0
h = []
for i in range(n):
    if d[i] < 0:
        ans += dfs(i)
        count -= 1
if count > 0:
    h.sort()
    ans += sum(h[:count])
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*m < n:
    print("Impossible")
    exit()

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

u = Unionfind(n)
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    u.union(x,y)
count = 2*(n-m-1)
l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        l[i].append(a[i])
    else:
        l[x].append(a[i])

ans = 0
h = []
for i in range(n):
    if l[i]:
        l[i].sort()
        ans += l[i][0]
        count -= 1
        for j in l[i][1:]:
            h.append(j)
h.sort()
ans += sum(h[:count])
print(ans)