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.

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

        return self.__table[x]

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

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

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

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

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


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

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

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

    if len(d) == 1:
        return 0

    ans = 0
    n = []
    for v in d.values():
        m = min(v)
        ans += m
        v.remove(m)
        n.extend(v)

    e = len(d)-2
    if len(n) < e:
        return 'Impossible'

    n.sort()
    ans += sum(n[:e])
    return ans


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


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

        return self.__table[x]

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

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

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

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

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


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

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

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

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

    if len(d) == 1:
        return 0
    ans = 0
    n = []
    for v in d.values():
        ans += heapq.heappop(v)
        n.extend(v)

    e = len(d)-2
    n.sort()
    if len(n) < e:
        return 'Impossible'
    ans += sum(n[:e])
    return ans


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


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
X = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    X[a].append(b)
    X[b].append(a)

def col(n, E):
    C = [-1] * n
    c = 0
    for i in range(N):
        if C[i] >= 0: continue
        Q = [i]
        C[i] = c
        while Q:
            x = Q.pop()
            for y in E[x]:
                if C[y] == -1:
                    C[y] = C[x]
                    Q.append(y)
        c += 1
    return C

C = col(N, X)
K = max(C) + 1

if N < 2*K-2:
    print("Impossible")
elif K == 1:
    print(0)
else:
    B = [-1] * K
    BB = []
    for i in range(N):
        if B[C[i]] < 0:
            B[C[i]] = A[i]
        else:
            if A[i] >= B[C[i]]:
                BB.append(A[i])
            else:
                BB.append(B[C[i]])
                B[C[i]] = A[i]
    BB = sorted(BB)
    
    print(sum(B + BB[:K-2]))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    k=n-m-1 
    if(k==0):
        print(0)
        return
    if(n<2*k):
        print("Impossible")
        return

    
    A=[[a,i] for i,a in enumerate(map(int,input().split()))]
    A.sort()
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y=map(int,input().split())
        E[x].append(y)
        E[y].append(x)

    cnt=0
    col=[None]*n 
    def dfs(v)->bool:
        if(col[v] is not None): return False
        col[v]=cnt
        Q=[v]
        while(Q):
            v=Q.pop()
            for nv in E[v]:
                if(col[nv] is not None): continue
                col[nv]=cnt
                Q.append(nv)
        return True

    for v in range(n):
        cnt+=dfs(v)

    
    ans=0
    used=[0]*cnt
    for i in range(n):
        a,v=A[i]
        if(not used[col[v]]):
            ans+=a
            used[col[v]]=1
            A[i][0]=INF

    
    A.sort()
    for a,v in A[:2*k-(n-m)]:
        ans+=a

    print(ans)
resolve()

Solution (Python):
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    xy=[list(map(int,input().split())) for _ in [0]*m]

    class unionfind():
        
        def __init__(self,size):
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]
        
        
        def root(self,index):
            temp_list=[]
            temp=self.tree[index][0]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index][0]
            for i in temp_list:
                self.tree[i][0]=index
            return index
    
        
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    u=unionfind(n)
    for x,y in xy:
        u.unite(x,y)
    for i in range(n):
        u.tree[i][0]=u.root(i)
    ut=u.tree
    d=dict()
    for i in range(n):
        if ut[i][0] in d.keys():
            d[ut[i][0]].append(a[i])
        else:
            d[ut[i][0]]=[a[i]]
    list1=[]
    list2=[]
    for s in d.values():
        s2=sorted(s)
        list1.append(s2[0])
        list2+=s2[1:]
    if len(list1)==1:
        print(0)
    elif len(list1)>len(list2)+2:
        print("Impossible")
    else:
        list2.sort()
        print(sum(list1)+sum(list2[:len(list1)-2]))
main()

Solution (Python):
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    xy=[list(map(int,input().split())) for _ in [0]*m]
    class unionfind():
        
        def __init__(self,size):
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]
        
        
        def root(self,index):
            if self.tree[index][0]==index:
                return index
            else:
                self.tree[index][0]=self.root(self.tree[index][0])
                return self.tree[index][0]
    
        
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    u=unionfind(n)
    for x,y in xy:
        u.unite(x,y)
    for i in range(n):
        u.tree[i][0]=u.root(i)
    ut=u.tree
    d=dict()
    for i in range(n):
        if ut[i][0] in d.keys():
            d[ut[i][0]].append(a[i])
        else:
            d[ut[i][0]]=[a[i]]
    list1=[]
    list2=[]
    for s in d.values():
        s2=sorted(s)
        list1.append(s2[0])
        list2+=s2[1:]
    if len(list1)==1:
        print(0)
    elif len(list1)>len(list2)+2:
        print("Impossible")
    else:
        list2.sort()
        print(sum(list1)+sum(list2[:len(list1)-2]))
main()

Solution (Python):
from heapq import heappop
from collections import defaultdict

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


N, M, *L = map(int, open(0).read().split())
A, XY = L[:N], L[N:]

uf = UnionFind(N)
for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y)

C = defaultdict(list)
for i, a in enumerate(A):
    C[uf.find(i)].append(a)

if len(C) < 2:
    print(0)
    quit()

D = [sorted(c) for c in C.values()]
s = sum(heappop(d) for d in D)

L = []
for d in D:
    L += d

if len(L) < len(D) - 2:
    print("Impossible")
else:
    print(s + sum(sorted(L)[:len(D) - 2]))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

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

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1


n, m = LI()
A = [(a, i) for i, a in enumerate(LI())]
heapify(A)
uf = UnionFind(n)
for x, y in LIR(m):
    uf.union(x, y)

k = uf.group_num
if (k - 1) * 2 > n:
    print('Impossible')
else:
    ans = 0
    ret = 0
    ret2 = 0
    D = defaultdict(int)
    while ret + ret2 < (k - 1) * 2:
        a, i = heappop(A)
        r = uf.root(i)
        if not D[r]:
            D[r] = 1
            ret += 1
            ans += a
        else:
            if ret2 < (k - 1) * 2 - k:
                ret2 += 1
                ans += a
    print(ans)

Solution (Python):
N, M = map(int, input().split())
a = [int(i) for i in input().split()]
xy = [[int(i) for i in input().split()] for _ in range(M)]

class UnionFind() :
    def __init__(self, N) :
        self.parent = [-1] * N
        
    def root(self, x) :
        while self.parent[x] >= 0:
            x = self.parent[x]
        return x

    def unite(self, x, y) :
        rx = self.root(x)
        ry = self.root(y)

        if rx != ry :
            if self.parent[rx] > self.parent[ry] :
                self.parent[rx] = ry
            else :
                if self.parent[rx] == self.parent[ry] :
                    self.parent[rx] -= 1
                self.parent[ry] = rx
    
    def same(self, x, y) :
        return self.root(x) == self.root(y)
        
    def size(self, x) :
        return -self.parent[self.root(x)]
        
UF = UnionFind(N)
for x, y in xy :
    UF.unite(x, y)

component = 0
for p in UF.parent :
    if p < 0 :
        component += 1
        
if N < 2 * (component - 1) :
    print('Impossible')
elif component == 1 :
    print(0)
else :
    ret = 0
    b = [(a[i], UF.root(i)) for i in range(N)]
    b.sort()
    visited = [False] * N
    c = component - 2
    for v, k in b :
        if not visited[k] :
            ret += v
            visited[k] = True
        elif c > 0 :
            ret += v
            c -= 1
            
    print(ret)

Solution (Python):
import heapq
from collections import deque


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

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

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

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

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

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

q = []
for i in range(len(group)):
    for num in group[i]:
        if num != 10**9 +7:
            heapq.heappush(q, num)

for i in range(cnt):
    if not q:
        print("Impossible")
        exit()
    ans += heapq.heappop(q)
print(ans)

Solution (Python):
import sys

def wantp(n):

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

    for i in wpq:
        p[i] = n

    return n


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

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


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

dic = {}

ans = 0

for i in range(M):

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

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

    if xp != yp:

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

for i in range(N):

    now = i
    np = wantp(now)

    if np not in dic:
        dic[np] = []

    dic[np].append(a[i])

    """

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

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

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

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

    """



ans = 0
able = []


for i in dic:
    dic[i].sort()
    ans += dic[i][0]

    for j in range(len(dic[i])-1):
        able.append(dic[i][j+1])
    

able.sort()

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

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

for i in range(len(dic)-2):

    ans += able[i]

print (ans)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')


input=lambda: sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(10**7)

show_flg=False
show_flg=True


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

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

for i in range(n):
    if v[i]!=-1:
        continue
    p=[]
    cost=[]
    p.append(i)
    heappush(cost,a[i])
    while p:
        c=p.pop()
        v[c]=a[c]
        for nb in g[c]:
            if v[nb]==-1:
                p.append(nb)
                v[nb]=a[nb]
                heappush(cost,a[nb])
    ans+=heappop(cost)
    cmp+=1
    while cost:
        heappush(rest,heappop(cost))

if cmp==1:
    ans=0
elif len(rest)<cmp-2:
    ans="Impossible"
else:
    for i in range(cmp-2):
        ans+=heappop(rest)

print(ans)

Solution (Python):
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

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

root = {}
for i in range(N):
    r = uni.Find_Root(i)
    if not r in root.keys():
        root[r] = [A[i]]
    else:
        hp.heappush(root[r], A[i])
B = sorted(root.values(), reverse=True, key=lambda x:len(x))
q = []
ok = True
ans = 0
for i, L in enumerate(B):
    if i == 0:
        for a in L:
            hp.heappush(q, a)
    else:
        if not q:
            ok = False
            break
        a1 = hp.heappop(q)
        a2 = hp.heappop(L)
        ans += a1 + a2
        for a in L:
            hp.heappush(q, a)
if not ok:
    print("Impossible")
else:
    print(ans)

Solution (Python):
from collections import*
from heapq import*
n,m,*a=map(int,open(0).read().split())
t=[-1]*n
def r(x):
  while t[x]>=0:x=t[x]
  return x
def u(x,y):
  x,y=r(x),r(y)
  if x!=y:
    if t[x]>t[y]:x,y=y,x
    t[x]+=t[y]
    t[y]=x
d=defaultdict(list)
for x,y in zip(*[iter(a[n:])]*2):u(x,y)
for i,v in enumerate(a[:n]):d[r(i)]+=v,
if len(d)<2:
  print(0)
  exit()
*d,=map(sorted,d.values())
c=sum(heappop(t)for t in d)
l=[]
for t in d:l+=t
i=len(d)-2
print(i>len(l)and'Impossible'or c+sum(sorted(l)[:i]))

Solution (Python):
from collections import*
from heapq import*
n,m,*a=map(int,open(0).read().split())
t=[-1]*n
def r(x):
  while t[x]>=0:x=t[x]
  return x
def u(x,y):
  x,y=r(x),r(y)
  if x!=y:
    if t[x]>t[y]:x,y=y,x
    t[x]+=t[y]
    t[y]=x
d=defaultdict(list)
for x,y in zip(*[iter(a[n:])]*2):u(x,y)
for i,v in enumerate(a[:n]):d[r(i)]+=v,
if len(d)<2:
  print(0)
  exit()
*d,=map(sorted,d.values())
c=sum(heappop(t)for t in d)
l=[]
for t in d:l+=t
i=len(d)-2
print(i>len(l)and'Impossible'or c+sum(sorted(l)[:i]))

Solution (Python):
from collections import*
from heapq import*
def main():
  n,m,*a=map(int,open(0).read().split())
  table=[-1]*n
  def root(x):
    while table[x]>=0:x=table[x]
    return x
  def unite(x,y):
    s1=root(x)
    s2=root(y)
    if s1!=s2:
      if table[s1]>table[s2]:s1,s2=s2,s1
      table[s1]+=table[s2]
      table[s2]=s1
  d=defaultdict(list)
  for x,y in zip(*[iter(a[n:])]*2):unite(x,y)
  for i,v in enumerate(a[:n]):d[root(i)]+=v,
  if len(d)<2:
    print(0)
    return
  *d,=map(sorted,d.values())
  c=sum(heappop(t)for t in d)
  l=[]
  for t in d:l+=t
  i=len(d)-2
  if len(l)<i:
    print('Impossible')
  else:
    print(c+sum(sorted(l)[:i]))
main()

Solution (Python):
def main():
    import sys,heapq
    input = sys.stdin.readline

    n,m = map(int,input().split())
    a = tuple(map(int,input().split()))


    
    par = [-1]*n
    
    def find(x):
        if par[x] < 0:
            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 False
        else:
            
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

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

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


    for _ in [0]*m:
        x,y = map(int,input().split())
        unite(x,y)
    
    if m < (n-1)//2:
        print('Impossible')
        return
    
    h = [[] for _ in [0]*n]
    for i,e in enumerate(a):
        heapq.heappush(h[find(i)],e)
    
    root = []
    for i,e in enumerate(par):
        if e < 0:
            root.append(i)
    
    if len(root) == 1:
        print(0)
        return

    must = 0
    opt = []
    for i in root:
        must += heapq.heappop(h[i])
        for e in h[i]:
            opt.append(e)
    opt.sort()

    print(must+sum(opt[:len(root)-2]))



if __name__ =='__main__':
    main()

Solution (Python):
from collections import deque

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

N, M = map(int, input().split())
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
INF = float('inf')

tree = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    tree.union(a, b)

A.sort()
ans = 0
L = (tree.getComponent() - 1) * 2

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

V = set()
for j, (a, i) in enumerate(A):
    r = tree.root(i)
    if not r in V:
        ans += a
        V.add(r)
        L -= 1
        A[j] = (INF, i)

A.sort()
for a, _ in A[:L]:
    ans += a

if ans == INF:
    print('Impossible')
else:
    print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


parent_data = []

def union(ind):
    global parent_data
    if parent_data[ind] != ind:
        parent_data[ind] = union(parent_data[ind])
    return parent_data[ind]


def main():
    node_num, edge_num = map(int, input().split())
    cost_data = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    global parent_data
    parent_data = [i for i in range(node_num)]

    for i in range(edge_num):
        a, b = data[i]
        parent_a = union(a)
        parent_b = union(b)
        parent_data[min(parent_a, parent_b)] = max(parent_a, parent_b)

    parent_count = defaultdict(int)
    cost_heap = defaultdict(list)
    for i in range(node_num):
        parent_i = union(i)
        parent_count[parent_i] += 1
        heapq.heappush(cost_heap[parent_i], (cost_data[i], parent_i))

    parent_count = list(sorted(parent_count.items(), key=lambda x:-x[1]))

    ans = 0
    ori_ind, ori_count = parent_count[0]

    for i in range(len(parent_count) - 1):
        now_ind, now_count = parent_count[i + 1]
        if len(cost_heap[ori_ind]) == 0:
            print('Impossible')
            sys.exit()
        ori_cost, o_ind = heapq.heappop(cost_heap[ori_ind])
        now_cost, n_ind = heapq.heappop(cost_heap[now_ind])
        ans += ori_cost + now_cost

        if len(cost_heap[n_ind]) > 0:
            a, b = heapq.heappop(cost_heap[n_ind])
            heapq.heappush(cost_heap[ori_ind], (a, b))
        if len(cost_heap[o_ind]) > 0 and o_ind != ori_ind:
            a, b = heapq.heappop(cost_heap[o_ind])
            heapq.heappush(cost_heap[ori_ind], (a, b))

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  ri = root(R, i)
  rj = root(R, j)
  if ri <= rj:
    R[rj] = ri
  else:
    R[ri] = rj
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
if N < 2 * (N - M - 1):
  print('Impossible')
elif M == N - 1:
  print(0)
else:
  cnt= 0
  E = N - M - 2
  C = [0] * N
  F = sorted([[a, R[i]] for i, a in enumerate(A)])
  for a, r in F:
    if C[r] == 0:
      C[r] = a
      cnt += a
    elif E > 0:
      cnt += a
      E -= 1
  print(cnt)