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:
from heapq import heappush, heappop, heapify


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    uft = UnionFindTree(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uft.unite(x, y)
    groups = uft.groups()
    if len(groups) == 1:
        print(0)
        return
    single = 0
    ans = 0
    h = []
    for g in groups:
        if len(g) == 1:
            single += 1
            ans += A[g[0]]
        else:
            if len(h) == 0:
                for x in g:
                    heappush(h, A[x])
            else:
                ans += heappop(h)
                g2 = [A[x] for x in g]
                g2.sort()
                ans += g2[0]
                for x in g2[1:]:
                    heappush(h, x)
    if len(groups) == 2 and N == 2:
        print(ans)
        return
    if len(h) < single:
        print("Impossible")
        return
    for _ in range(single):
        ans += heappop(h)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections, heapq
N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]
G = collections.defaultdict(list)
for x, y in XY:
    G[x] += [y]
    G[y] += [x]
B = sorted([v, i] for i, v in enumerate(A))
visited = [0] * N
ans = 0
H = []
t = 0
for b in B:
    v, i = b
    if not visited[i]:
        visited[i] = 1
        ans += v
        q = G[i]
        t += 1
        while q:
            i = q.pop()
            if not visited[i]:
                visited[i] = 1
                heapq.heappush(H, [A[i], i])
                q += G[i]
if len(H) < t - 2:
    print('impossible')
    exit()
elif t == 1:
    print(0)
    exit()
for _ in range(t - 2):
    v, i = heapq.heappop(H)
    ans += v
print(ans)

Submission status: Wrong Answer

Solution code:
print('Impossible')

Submission status: Wrong Answer

Solution code:
import collections, heapq
N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]
visited = [0] * (N + 1)
G = collections.defaultdict(list)
for x, y in XY:
    G[x] += [y]
    G[y] += [x]
B = sorted([v, i] for i, v in enumerate(A))

ans = 0
H = []
Q = [B[0][1]]
while Q:
    i = Q.pop()
    if not visited[i]:
        visited[i] = 1
        heapq.heappush(H, [A[i], i])
        Q += G[i]
for b in B[1:]:
    v, i = b
    if not visited[i]:
        visited[i] = 1
        if not H:
            print('Impossible')
            exit()
        ans += v + heapq.heappop(H)[0]
        q = G[i]
        while q:
            i = q.pop()
            if not visited[i]:
                visited[i] = 1
                heapq.heappush(H, [A[i], i])
                q += G[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]

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

root = [-1 for _ in range(n)]
is_minimum = [False for _ in range(n)]

def dfs(x, r):
	global mi, mi_ind
	if a[x] < mi:
		mi = a[x]
		mi_ind = x
	for v in adj[x]:
		if root[v] < 0:
			root[v] = r
			dfs(v, r)
	return mi_ind

for i in range(n):
	if root[i] < 0:
		mi, mi_ind = 10**10, -1
		root[i] = i
		is_minimum[dfs(i, i)] = True

con_num = len(set(root))
#print(con_num)
if (con_num-1) * 2 > n:
	print("Impossible")
	sys.exit()
elif con_num == 0:
	print(0)
	sys.exit()
ans = sum([a[i] for i in range(n) if is_minimum[i]])
ans += sum(sorted([a[i] for i in range(n) if not is_minimum[i]])[:con_num-2])
print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


if M == N-1:
    print(0)
elif N < 2*(N-M-1):
    print(0)
else:
    cost = 0
    cnt = 0
    for l in Un.get_parents():
        cost += heapq.heappop(Un.costs[l])
        cnt += len(Un.costs[l])
    print("N->", N, cnt)

    remain_l = []
    for l in Un.get_parents():
        for v in Un.costs[l]:
            heapq.heappush(remain_l, v)
    # for _ in range(2*(N-M-1)):
    #    cost += heapq.heappop(remain_l)
    print(cost)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 0
        if len(self.costs[px]) == 0 or len(self.costs[py]) == 0:
            print("Impossible")
            exit()
        cost = heapq.heappop(self.costs[px])+heapq.heappop(self.costs[py])
        self.union(px, py)
        return cost

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


cost = 0
leaders = Un.get_parents()
while len(leaders) > 1:
    leader = leaders[0]
    tmp_ind = -1
    tmp_min = float('inf')
    for l in leaders[1:]:
        tmp_cost = min(Un.costs[l])
        if tmp_cost < tmp_min:
            tmp_id = l
            tmp_min = tmp_cost
    cost += Un.merge(leader, tmp_id)
    leaders = Un.get_parents()

print(cost)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 0
        if len(self.costs[px]) == 0 or len(self.costs[py]) == 0:
            print("Impossible")
            exit()
        cost = heapq.heappop(self.costs[px])+heapq.heappop(self.costs[py])
        self.union(px, py)
        return cost

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


cost = 0
leaders = Un.get_parents()
while len(leaders) > 1:
    leader = leaders[0]
    tmp_ind = -1
    tmp_min = float('inf')
    for l in leaders[1:]:
        tmp_cost = heapq.heappop(Un.costs[l])
        if tmp_cost < tmp_min:
            tmp_id = l
            tmp_min = tmp_cost
        heapq.heappush(Un.costs[l], tmp_cost)
    cost += Un.merge(leader, tmp_id)
    leaders = Un.get_parents()

print(cost)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 0
        if len(self.costs[px]) == 0 or len(self.costs[py]) == 0:
            print("Impossible")
            exit()
        cost = heapq.heappop(self.costs[px])+heapq.heappop(self.costs[py])
        self.union(px, py)
        return cost

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


cost = 0
leaders = Un.get_parents()
leader = leaders[0]
for p in leaders[1:]:
    cost += Un.merge(p, leader)
    leader = Un.find(p)
print(cost)

Submission status: Wrong Answer

Solution code:
import heapq
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 0
        if len(self.costs[px]) or len(self.costs[py]):
            print("Impossible")
            exit()
        cost = heapq.heappop(self.costs[px])+heapq.heappop(self.costs[py])
        self.union(px, py)
        return cost

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


cost = 0
leaders = Un.get_parents()
leader = leaders[0]
for p in leaders[1:]:
    cost += Un.merge(p, leader)
    leader = Un.find(p)
print(cost)

Submission status: Wrong Answer

Solution code:
import heapq
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 0
        if len(self.costs[px]) or len(self.costs[py]):
            print("Impossible")
            exit()
        cost = heapq.heappop(self.costs[px])+heapq.heappop(self.costs[py])
        self.union(px, py)
        return cost

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


cost = 0
leaders = Un.get_parents()
for p in leaders[1:]:
    cost += Un.merge(p, leaders[0])
print(cost)

Submission status: Wrong Answer

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

class Uf:
    def __init__(self, N, mins):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
        self.mins = mins
        self.amins = list(range(N))

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0

            if self.mins[v] > self.mins[u]:
                self.mins[v] = self.mins[u]
                self.amins[v] = self.amins[u]
            self.mins[u] = -1
            self.mins[u] = -1
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.mins[u] > self.mins[v]:
                self.mins[u] = self.mins[v]
                self.amins[u] = self.amins[v]
            self.mins[v] = -1
            self.mins[v] = -1

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

    def min(self, x):
        return self.mins[self.root(x)]

uf = Uf(N, A.copy())

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


mins = [x for x in uf.mins if x != -1]
amins = set([x for x in uf.amins if x != -1])
ans = sum(mins)
A = [a for i, a in enumerate(A) if i not in amins]
A.sort()
ntrees = len(mins)
if ntrees == 1:
    print(0)
    exit()
if ntrees * 2 - 2 > N:
    print("Impossible")
    exit()
ans += sum(A[:ntrees - 2])
print(ans)

Submission status: Wrong Answer

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

class Uf:
    def __init__(self, N, mins):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
        self.mins = mins
        self.amins = list(range(N))

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0

            if self.mins[v] > self.mins[u]:
                self.mins[v] = self.mins[u]
                self.amins[v] = self.amins[u]
            self.mins[u] = -1
            self.mins[u] = -1
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.mins[u] > self.mins[v]:
                self.mins[u] = self.mins[v]
                self.amins[u] = self.amins[v]
            self.mins[v] = -1
            self.mins[v] = -1

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

    def min(self, x):
        return self.mins[self.root(x)]

uf = Uf(N, A)

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


mins = [x for x in uf.mins if x != -1]
amins = set([x for x in uf.amins if x != -1])
ans = sum(mins)
A = [a for i, a in enumerate(A) if i not in amins]
A.sort()
ntrees = len(mins)
if ntrees == 1:
    print(0)
    exit()
if ntrees * 2 - 2 > N:
    print("Impossible")
    exit()
ans += sum(A[:ntrees - 2])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(lambda x: [int(x)], input().split()))

class Uf:
    def __init__(self, N, mins):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
        self.mins = mins

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0

            self.mins[v] = sorted(self.mins[v] + self.mins[u])[:2]
            self.mins[u] = -1
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            self.mins[u] = sorted(self.mins[v] + self.mins[u])[:2]
            self.mins[v] = -1
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

    def min(self, x):
        return self.mins[self.root(x)]

uf = Uf(N, A)

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


AA1 = []
AA2 = []
len1cnt = 0
for i, a in enumerate(uf.mins):
    if a==-1:
        continue
    if len(a) == 1:
        len1cnt += 1
        AA1.extend(a)
    else:
        AA1.append(a[0])
        AA2.append(a[1])

if len1cnt>2:
    print("Impossible")
    exit()

if min(uf.p)==max(uf.p):
    print(0)
    exit()

ans = sum(AA1)
AA2.sort()
ans += sum(AA2[:len(AA1)-2])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(lambda x: [int(x)], input().split()))

class Uf:
    def __init__(self, N, mins):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
        self.mins = mins

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0

            self.mins[v] = sorted(self.mins[v] + self.mins[u])[:2]
            self.mins[u] = -1
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            self.mins[u] = sorted(self.mins[v] + self.mins[u])[:2]
            self.mins[v] = -1
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

    def min(self, x):
        return self.mins[self.root(x)]

uf = Uf(N, A)

for _ in range(M):
    x, y = map(int, input().split())
    #print(A[x], A[y])
    uf.unite(x, y)


AA = []
iAA = []
len1cnt = 0
for i, a in enumerate(uf.mins):
    if a==-1:
        continue
    if len(a) == 1:
        len1cnt += 1
        AA.extend(a)
        iAA.append(i)
    else:
        AA.extend(a)
        iAA.append(i)
        iAA.append(i)

if len1cnt>2:
    print("Impossible")
    exit()

if (len(AA)==2 and M!=0) or N==1:
    print(0)
    exit()

AAA = list(zip(AA, iAA))
AAA.sort(reverse=True)
a0, a1 = AAA[:2]
if a0[1] == a1[1]:
    a1 = AAA[2]
print(sum(AA) - a0[0] - a1[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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

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

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

    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

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

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

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

D = defaultdict(list)
for i in range(N):
    D[uf.find(i)].append(a[i])

for i in D:
    D[i] = sorted(D[i])

ans = 0
Q = []

x = len(D)
for i in D:
    if len(D[i]) == 1:
        ans += D[i][0]
    else:
        ans += D[i][0]
        m = len(D[i])
        for j in range(1, m):
            heappush(Q, D[i][j])

if N == 1:
    print(0)
else:
    if N >= 2 * len(D) - 2:
        for i in range(len(D) - 2):
            x = heappop(Q)
            ans += x
        print(ans)
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

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

    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

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

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

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

D = defaultdict(list)
for i in range(N):
    D[uf.find(i)].append(a[i])

for i in D:
    D[i] = sorted(D[i])

j = 0
for i in D:
    if len(D[i]) == 1:
        j += 1

if j >= 3:
    print("Impossible")
elif len(D) == 1:
    print(0)
else:
    if j == 2:
        ans = 0
        for i in D:
            if len(D[i]) == 1:
                ans += D[i][0]
            else:
                ans += D[i][0] + D[i][1]
        print(ans)
    elif j == 1:
        ans = 0
        d = []
        for i in D:
            if len(D[i]) == 1:
                ans += D[i][0]
            else:
                ans += D[i][0] + D[i][1]
                d.append(D[i][1])
        print(ans - max(d))
    else:
        ans = 0
        d = []
        for i in D:
            if len(D[i]) == 1:
                ans += D[i][0]
            else:
                ans += D[i][0] + D[i][1]
                d.append(D[i][1])
        d = sorted(d)
        print(ans - d[-1] - d[-2])

Submission status: Wrong Answer

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