Problem:


Score : 600 points

Problem Statement

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

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

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

Constraints

1 ≤ N ≤ 100,000

0 ≤ M ≤ N-1

1 ≤ a_i ≤ 10^9

0 ≤ x_i,y_i ≤ N-1

The given graph is a forest.

All input values are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

7

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

Sample Input 2

5 0
3 1 4 1 5

Sample Output 2

Impossible

We can't make the graph connected.

Sample Input 3

1 0
5

Sample Output 3

0

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



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


Sample output:
7

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 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)

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:
import heapq
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
if n == 1 or m == n-1:
  print(0)
  exit()
if n < 2*(n-m-+1):
    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:
import heapq
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
if n == 1:
  print(0)
  exit()
if m*2 < 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:
        heapq.heappush(l[i],a[i])
    else:
        heapq.heappush(l[x],a[i])

h1 = []
h2 = []
for i in range(n):
    if l[i]:
        if len(l[i])==1:
            x = heapq.heappop(l[i])
            heapq.heappush(h2,[x,i])
        else:
            x = heapq.heappop(l[i])
            heapq.heappush(h1,[x,i])
ans = 0
while len(h1) > 0 and len(h2) > 0:
    a,pa = heapq.heappop(h1)
    b,pb = heapq.heappop(h2)
    ans += a+b
    x = heapq.heappop(l[pa])
    if len(l[pa])>0:
        heapq.heappush(h1,[x,pa])
    else:
        heapq.heappush(h2,[x,pa])
if len(h2) > 0:
    a,pa = heapq.heappop(h2)
    b,pb = heapq.heappop(h2)
    ans += a+b
    
while len(h1) > 1:
    a = heapq.heappop(h1)
    b = heapq.heappop(h1)
    ans += a[0]+b[0]
    l[a[1]] = list(heapq.merge(l[a[1]],l[b[1]]))
    x = heapq.heappop(l[a[1]])
    heapq.heappush(h1,[x,a[1]])
    
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
if n == 1:
  print(0)
  exit()
if m*2 < 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:
        heapq.heappush(l[i],a[i])
    else:
        heapq.heappush(l[x],a[i])

h1 = []
h2 = []
for i in range(n):
    if l[i]:
        if len(l[i])==1:
            x = heapq.heappop(l[i])
            heapq.heappush(h2,[x,i])
        else:
            x = heapq.heappop(l[i])
            heapq.heappush(h1,[x,i])
ans = 0
while len(h2) > 0:
    a,pa = heapq.heappop(h1)
    b,pb = heapq.heappop(h2)
    ans += a+b
    x = heapq.heappop(l[pa])
    if len(l[pa])>0:
        heapq.heappush(h1,[x,pa])
    else:
        heapq.heappush(h2,[x,pa])
    
while len(h1) > 1:
    a = heapq.heappop(h1)
    b = heapq.heappop(h1)
    ans += a[0]+b[0]
    l[a[1]] = list(heapq.merge(l[a[1]],l[b[1]]))
    x = heapq.heappop(l[a[1]])
    heapq.heappush(h1,[x,a[1]])
    
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if n == 1:
  print(0)
  exit()

print("Impossible")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def connected_components(E):
    N = len(E)
    visited = set([])
    comp = []
    for v in range(N):
        if v not in visited:
            S = dfs(E, v)
            visited |= S
            comp += [list(S)]
    return comp

N, M = map(int, input().split())
*A, = map(int, input().split())
F = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    F[x].append(y); F[y].append(x)
if M == N - 1: print(0)
elif M < N - 2: print('Impossible')
else:
    visited = [False] * N
    
    def dfs(E, s):
        global visited
        stack = [(s, -1, 0)] # (vertex, parent, status)
        temp = float('inf')
        while stack:
            v, p, st = stack.pop()
            if st == 0 and not visited[v]: # visited v for the first time
                visited[v] = True
                temp = min(temp, A[v])
                n_children = 0
                for u in E[v]:
                    if visited[u]: continue
                    if n_children == 0:
                        stack += [(v, p, 2), (u, v, 0)]
                        n_children += 1
                    else:
                        stack += [(v, p, 1), (u, v, 0)]
                        n_children += 1
                if n_children == 0: # v is a leaf
                    continue
            elif st == 0 and v in visited: # the edge (v, p) is a back edge
                continue
            elif st == 1: # now searching
                continue
            else: # search finished
                continue
        return temp

    ans = 0
    for v in range(N):
        if not visited[v]:
            ans += dfs(F, v)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
# debug = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

N, M = inm()
A = inl()
assert len(A) == N


def solve():
    uf = UnionFind(N)
    for _ in range(M):
        x, y = inm()
        uf.union(x, y, pay=False)
    rs = uf.roots()
    for r in rs[1:]:
        if not uf.union(rs[0], r, pay=True):
            return "Impossible"
    return uf.paid_cost()


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n
        self._cost_table = [[A[i]] for i in range(n)]  # heap
        self._paid_cost = 0

    def paid_cost(self):
        return self._paid_cost

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y, pay):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

        if pay:
            if not self._cost_table[x]:
                return False
            ax = heapq.heappop(self._cost_table[x])
            if not self._cost_table[y]:
                return False
            ay = heapq.heappop(self._cost_table[y])
            self._paid_cost += ax + ay

        for z in self._cost_table[y]:
            heapq.heappush(self._cost_table[x], z)
        return True

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


print(solve())

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
if n-m == 1:
    print(0)
    exit()
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    way[x].append(y)
    way[y].append(x)

#グラフをグループ化するやつ
import queue
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n)]
    q = queue.Queue()
    for i in range(n):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

grp = grouping(n,way)
if len(grp)+2 > n-len(grp):
    print("Impossible")
    exit()
o2 = [0 for i in range(n-len(grp))]
o1 = [0 for i in range(len(grp))]
i1 = 0
i2 = 0

for j,gi in enumerate(grp):
    m = 10**10
    f = True
    for i in gi:
        if m > a[i]:
            if f:
                f = False
            else:
                o2[i1] = m
                i1 += 1
            m = a[i]
        else:
            o2[i1] = a[i]
            i1 += 1
    o1[j] = m

o2.sort()
ans = sum(o1)
for i in range(len(o1)-2):
    ans += o2[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
if n-m == 1:
    print(0)
    exit()
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    way[x].append(y)
    way[y].append(x)

#グラフをグループ化するやつ
import queue
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n)]
    q = queue.Queue()
    for i in range(n):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

grp = grouping(n,way)
if len(grp)+2 > n-len(grp):
    print("Impossible")
    exit()
o2 = [0 for i in range(n-len(grp))]
o1 = [0 for i in range(len(grp))]
i1 = 0
i2 = 0

for j,gi in enumerate(grp):
    m = 10**10
    f = True
    for i in gi:
        if m > a[i]:
            if f:
                f = False
            else:
                o2[i1] = m
                i1 += 1
            m = a[i]
        else:
            o2[i1] = a[i]
            i1 += 1
    o1[j] = m

o2.sort()
ans = sum(o1)
for i in range(len(o1)-2):
    ans += a[i]
print(ans)

Submission status: Wrong Answer

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

#グラフをグループ化するやつ
import queue
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n)]
    q = queue.Queue()
    for i in range(n):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

grp = grouping(n,way)
k2 = []
k1 = []
mi1 = 0
mi2 = 0
for gi in grp:
    if len(gi) == 1:
        k1.append(a[gi[0]])
    else:
        m1 = 10**10
        m2 = 10**10
        for j in gi:
            if a[j] < m1:
                m1,m2 = a[j],m1
            elif a[j] < m2:
                m2 = a[j]
        if mi1 < m2:
            mi1,mi2 = m2,mi1
        elif mi2 < m2:
            mi2 = m2
        k2.append(m1+m2)

if len(k1) > 2:
    print("Impossible")
elif len(grp) == 1:
    print(0)
else:
    ans = sum(k1)+sum(k2)
    if len(k1) == 1:
        ans -= mi1
    elif len(k1) == 0:
        ans -= (mi1+mi2)
    print(ans)

Submission status: Wrong Answer

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

#グラフをグループ化するやつ
import queue
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n)]
    q = queue.Queue()
    for i in range(n):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

grp = grouping(n,way)
k2 = []
k1 = []
mi1 = 0
mi2 = 0
for gi in grp:
    if len(gi) == 1:
        k1.append(a[gi[0]])
    else:
        m1 = 10**10
        m2 = 10**10
        for j in gi:
            if a[j] < m1:
                m2 = m1
                m1 = a[j]
            elif a[j] < m2:
                m2 = a[j]
        if mi1 < m2:
            mi2 = mi1
            mi1 = m2
        elif mi2 < m2:
            mi2 = m2
        k2.append([m1,m2])

if len(k1) > 2:
    print("Impossible")
elif len(grp) == 0:
    print(0)
else:
    ans = sum(k1)
    for i in k2:
        ans += i[0]+i[1]
    if len(k1) == 1:
        ans -= mi1
    elif len(k1) == 0:
        ans -= mi1+mi2
    print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
a=list(map(int,input().split()))
uf=UnionFindVerSize(N)
for i in range(M):
    x,y=map(int,input().split())
    uf.unite(x,y)

dic={}
for i in range(0,N):
    if uf.find_root(i) not in dic:
        dic[uf.find_root(i)]=[]
    dic[uf.find_root(i)].append(a[i])

for i in dic:
    dic[i].sort()

count=0
for i in dic:
    if len(dic[i])==1:
        count+=1

if len(dic)==1:
    print(0)
else:
    if count>2:
        print("Impossible")
    elif count==2:
        ans=0
        for i in dic:
            if len(dic[i])==1:
                ans+=dic[i][0]
            else:
                ans+=dic[i][0]+dic[i][1]
        print(ans)
    elif count==1:
        ans=0
        minus=0
        for i in dic:
            if len(dic[i])==1:
                ans+=dic[i][0]
            else:
                ans+=dic[i][0]+dic[i][1]
                minus=max(minus,dic[i][1])
        print(ans-minus)
    else:
        ans=0
        second=[]
        for i in dic:
            ans+=dic[i][0]+dic[i][1]
            second.append(dic[i][1])
        second.sort()
        ans-=second[0]+second[1]
        print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
for x,y in XY:
    u.unite(x,y)
if u.size(0)==N:
    print(0);exit()
d={}
x=[]
for i,a in enumerate(A):
    r=u.root(i)
    if r not in d:
        d[r]=a
    elif a<d[r]:
        x.append(d[r])
        d[r]=a
    else:
        x.append(a)
rem=2*(N-1-M)-len(d)
print(d,x,rem)
print(sum([v for v in d.values()])+sum(sorted(x)[:rem]) if len(x)>=rem else "Impossible")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
        self.Vacant=[1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            self.Vacant[rm]+=self.Vacant[rn]
            self.Vacant[rn]=0
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
    def vacant(self,n):
        return self.Vacant[self.root(n)]
u=UnionFind(N)
for x,y in XY:
    u.unite(x,y)
A=sorted([(i,a) for i,a in enumerate(A)],key=lambda x:x[1])
from collections import deque
q=deque()
r=0
for n,(i,a) in enumerate(A):
    if q:
        if u.root(q[0][0])!=u.root(i) and (u.vacant(i)>1 or u.vacant(q[0][0])>1 or u.size(i)+u.size(q[0][0])==N):
            j,b=q.popleft()
            u.unite(i,j)
            r+=a+b
            u.Vacant[u.root(i)]-=2
        else:
            q.append((i,a))
    else:
        q.append((i,a))
print(r if u.size(0)==N else "Impossible")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
for x,y in XY:
    u.unite(x,y)
A=sorted([(i,a) for i,a in enumerate(A)],key=lambda x:x[1])
from collections import deque
q=deque()
r=0
for i,a in A:
    if q:
        if u.root(q[0][0])==u.root(i):
            q.append((i,a))
        else:
            j,b=q.popleft()
            u.unite(i,j)
            r+=a+b
    else:
        q.append((i,a))
print(r if u.size(0)==N else "Impossible")

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
q = []
for i in range(n):
  ai = a[i]
  heappush(q,(ai,i))
  ri = root(i)
  heappush(d[ri],(ai,i))

ans = 0
tmp = 0
c = [0] * n

for i in d.keys():
  tmp += 1
  t,p = heappop(d[i])
  c[p] = 1
  ans += t
if 2*tmp-2 > n:
  print("Impossible")
else:
  for _ in range(tmp-2):
    p,i = heappop(q)
    while c[i]:
      p,i = heappop(q)
    ans += p
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
q = []
for i in range(n):
  ai = a[i]
  heappush(q,(ai,i))
  ri = root(i)
  heappush(d[ri],(ai,i))

ans = 0
tmp = 0
c = [0] * n

for i in d.keys():
  tmp += 1
  t,p = heappop(d[i])
  c[p] = 1
  ans += t
if 2*tmp > n:
  print("Impossible")
else:
  for _ in range(tmp):
    p,i = heappop(q)
    while c[i]:
      p,i = heappop(q)
    ans += p
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
for i in range(n):
  ai = a[i]
  i = root(i)
  heappush(d[i],ai)

ans = 0
forest = []
for i in d.keys():
  p = heappop(d[i])
  heappush(forest,(p,i))

while forest:  
  if len(forest) < 2:
    break
  p1,i1 = heappop(forest)
  p2,i2 = heappop(forest)
  ans += p1 + p2
  union(i1,i2)
  if i1 == root(i1):
    for di2 in d[i2]:
      heappush(d[i1],di2)
  else:
    for di1 in d[i1]:
      heappush(d[i2],di1)
  i1 = root(i1)
  if d[i1]:
    heappush(forest,(heappop(d[i1]),i1))
for i in range(n):
  root(i)
if len(set(par)) == 1:
  print(ans)
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
for i in range(n):
  ai = a[i]
  i = root(i)
  heappush(d[i],ai)

ans = 0
forest = []
for i in d.keys():
  p = heappop(d[i])
  heappush(forest,(p,i))

for i in range(len(set(par))-1):  
  if len(forest) < 2:
    ans = "Impossible"
    break
  p1,i1 = heappop(forest)
  p2,i2 = heappop(forest)
  ans += p1 + p2
  union(i1,i2)
  if i1 == root(i1):
    for di2 in d[i2]:
      heappush(d[i1],di2)
  else:
    for di1 in d[i1]:
      heappush(d[i2],di1)
  i1 = root(i1)
  if d[i1]:
    heappush(forest,(heappop(d[i1]),i1))

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
for i in range(n):
  ai = a[i]
  i = root(i)
  heappush(d[i],ai)

ans = 0
forest = []
for i in set(par):
  p = heappop(d[i])
  heappush(forest,(p,i))

for i in range(len(set(par))-1):  
  if len(forest) < 2:
    ans = "Impossible"
    break
  p1,i1 = heappop(forest)
  p2,i2 = heappop(forest)
  ans += p1 + p2
  union(i1,i2)
  if i1 == root(i1):
    for di2 in d[i2]:
      heappush(d[i1],di2)
  else:
    for di1 in d[i1]:
      heappush(d[i2],di1)
  i1 = root(i1)
  if d[i1]:
    heappush(forest,(heappop(d[i1]),i1))

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))
# edg = [[] for i in range(n)]
rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
for i in range(n):
  ai = a[i]
  i = root(i)
  heappush(d[i],ai)

ans = 0
forest = []
for i in set(par):
  p = heappop(d[i])
  heappush(forest,(p,i))

for i in range(len(set(par))-1):
  p1,i1 = heappop(forest)
  p2,i2 = heappop(forest)
  ans += p1 + p2
  if d[i1]:
    heappush(forest,(heappop(d[i1]),i1))
  if d[i2]:
    heappush(forest,(heappop(d[i2]),i2))
  if len(forest) < 2:
    ans = "Impossible"
    break
print(ans)