Harryxun/stf_run huggingface dataset:
from collections import deque
 
n,m=map(int,input().split())
node=[[] for _ in range(n)]
 
for _ in range(m):
    a,b=map(lambda x:int(x)-1,input().split())
    node[a].append(b)
    node[b].append(a)
    
#print(node)
 

seen=[False]*n
depth=[-1]*n
todo=deque([])
todo.append(0)
depth[0]=1

    
while len(todo)>0:
    p=todo[0]
    
    seen[p]=True
    to=node[p]
    for i in to:
        if seen[i]:continue
        if depth[i]==-1:
            depth[i]=depth[p]+1
            todo.append(i)
    todo.popleft()
 
 

if min(depth)==-1:
    print('No')
else:
    print("Yes")
    for i in range(1,n):
        for j in node(i):
            if depth[i]>depth[j]:
                print(j+1)
                break

### FIXED CODE ###

from collections import deque
 
n,m=map(int,input().split())
node=[[] for _ in range(n)]
 
for _ in range(m):
    a,b=map(lambda x:int(x)-1,input().split())
    node[a].append(b)
    node[b].append(a)
    
#print(node)
 

seen=[False]*n
depth=[-1]*n
todo=deque([])
todo.append(0)
depth[0]=1

    
while len(todo)>0:
    p=todo[0]
    
    seen[p]=True
    to=node[p]
    for i in to:
        if seen[i]:continue
        if depth[i]==-1:
            depth[i]=depth[p]+1
            todo.append(i)
    todo.popleft()
 
 

if min(depth)==-1:
    print('No')
else:
    print("Yes")
    for i in range(1,n):
        for j in node[i]:
            if depth[i]>depth[j]:
                print(j+1)
                break
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.unit64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
        d[a::a] += 1
      else:
        d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
main()


### FIXED CODE ###

import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.uint64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      d[a::a] += 1
    else:
      d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
main()
n,k = map(int,input().split())
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1,k+1):
    ans = (combinations_count(n-k+1,i)*combinations_count(k-1,i-1))%((10**9)+7)
    print(ans)

### FIXED CODE ###

import math

n,k = map(int,input().split())

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))



for i in range(1,k+1):
    if n-k+1>=i:
        ans = (combinations_count(n-k+1,i)%(10**9+7)*combinations_count(k-1,i-1)%(10**9+7))
        print(ans%(10**9+7))
    else:
        print(0)
for  x in range(1,101)
 print(x ** 3)

### FIXED CODE ###

x = int(input())

print(x **3)
anntena = []
for i in range(5):
    anntena.append(int(input())
k = int(input())
                 
if anntena[4] - anntena[0] <= k:
    print('Yey!')
else:
    print(':(')


### FIXED CODE ###

max_distance = 0
previous = int(input())
for i in range(4):
    current = int(input())
    distance = current - previous
    if distance > max_distance:
        max_distance = distance

k = int(input())

if max_distance > k:
    print(":(")
else:
    print("Yay!")
o = input()
e = input()
ans = ''
n = len(o)
a = 0
while a < n:
  ans += o[a]
  if a <= len(e):
    ans += e[a]
  a += 1
print(ans)

### FIXED CODE ###

o = input()
e = input()
ans = ''
n = len(o)
a = 0
while a < n:
  ans += o[a]
  if a+1 <= len(e):
    ans += e[a]
  a += 1
print(ans)
SA = list(input())
SB = list(input())
SC = list(input())

D = {'a': SA, 'b': SB, 'c': SC}
now = 'a'

while D[now]:
    now = D[now].pop()

print(now)


### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print((a + b) * h // 2)
import sys,math,bisect
input = sys.stdin.readline

mod = 1000000007
eps = 0.001

n = int(input())

ab = []
ang = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,b))
    if a == 0:
        ang.append((90.0,i))
    else:
        ang.append((math.degrees(math.atan(b/a)),i))
ang.sort()

res = 1
used = [False]*n


rest = n

for i in range(n):
    e,idx = ang[i]
    if used[idx]:
        continue
    used[idx] = True
    
    cnt = 1
    k = idx + 1
    while k < n:
        if abs(e-ang[k][0]) <= eps:
            p = ang[k][1]
            if ab[p][0]*ab[idx][1] == ab[p][1]*ab[idx][0]:
                cnt += 1
                used[p] = True
            k += 1
        else:
            break


    cnt2 = 0

    ok = n-1
    ng = i+1
    while ok-ng > 1:
        mid = (ok+ng)//2
        if ang[mid][0] >= e+90-eps:
            ok = mid
        else:
            ng = mid

    k = ok
    while k < n:
        if abs(e+90-ang[k][0]) <= 0.002:
            p = ang[k][1]
            if ab[p][0]*ab[idx][0] + ab[p][1]*ab[idx][1] == 0:
                cnt2 += 1
                used[p] = True
            k += 1
        else:
            break

    if cnt2 != 0:
        res = res*(pow(2,cnt,mod) + pow(2,cnt2,mod) - 1)%mod
        rest -= cnt+cnt2

res = res*pow(2,rest,mod)%mod - 1
print(res)





### FIXED CODE ###

import sys,math
input = sys.stdin.buffer.readline

mod = 1000000007
n = int(input())

ab = []
ang = dict()
rev = dict()
dg = 10**20
zero = 0

for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        if 1 in ang:
            ang[1] += 1
        else:
            ang[1] = 1
    elif b == 0:
        if 1 in rev:
            rev[1] += 1
        else:
            rev[1] = 1
    elif a*b > 0:
        if a < 0 and b < 0:
            a,b = -a,-b
        g = math.gcd(a,b)
        a,b = a//g,b//g

        if a*dg + b in ang:
            ang[a*dg + b] += 1
        else:
            ang[a*dg + b] = 1
    else:
        a,b = abs(a),abs(b)
        g = math.gcd(a,b)
        a,b = a//g,b//g

        if b*dg + a in rev:
            rev[b*dg + a] += 1
        else:
            rev[b*dg + a] = 1

rest = n - zero

res = 1

for e in ang:
    if e in rev:
        res = res*(pow(2,ang[e],mod) + pow(2,rev[e],mod) - 1)%mod
        rest -= ang[e] + rev[e]

res = res*pow(2,rest,mod)%mod - 1 + zero

print(res%mod)
8
9 1 14 5 5 4 4 14

### FIXED CODE ###

K=int(input())
D=[int(x) for x in input().split()]
D.sort()
M=K/2
m=M-1
ans=D[int(M)]-D[int(m)]
print(ans)
s = input()
q = int(input())

query = []
rev=1

for i in range(q):
    query.append(input().split())

for i in range(q):
    if query[i][0]=="1":
        rev*=-1
    else:
        if rev==1:
            if query[i][1]=="1":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])
        else:
            if query[i][1]=="2":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])

if rev==-1:
    s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

query = []
rev=1

for i in range(q):
    query.append(input().split())

for i in range(q):
    if query[i][0]=="1":
        rev*=-1
    else:
        if rev==1:
            if query[i][1]=="1":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])
        else:
            if query[i][1]=="2":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])

result="".join(list(s))
if rev==-1:
    result = result[::-1]
print(result)
s = input()
t = input()
n = 0
max_n = 0
for ss in strs:
    for i in np.arange(len(t)):
        if t[i]==ss[i]:
            n += 1
        else:
            n = 0
        if max_n < n:
            max_n = n
print(len(t)-max_n)

### FIXED CODE ###

import numpy as np
s = input()
t = input()
strs = []
t_size = len(t)
for i in np.arange(len(s)-len(t)+1):
    strs.append(s[i:i+t_size])
n = 0
max_n = 0
for ss in strs:
    for i in np.arange(len(t)):
        if t[i]==ss[i]:
            n += 1
        if max_n < n:
            max_n = n
    n = 0
print(len(t)-max_n)
while True:
    x=input()
    if x=="0 ? 0":
        break
    print(int(eval(x)))

### FIXED CODE ###

while True:
    x=input()
    if "?" in x:
        break
    print(int(eval(x.replace("/","//"))))
h,a = map(int,input().split())

ans=h//a
if(h%a!=0):
    ans++
print(ans)


### FIXED CODE ###

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

ans=h//a
if(h%a!=0):
    ans+=1
print(ans)
N,M=map(int,input().split())
import sympy as sym
oo = sym.oo
n=sym.symbols('n')
t=M*1900+(N-M)*100
p=(1/2)**M
q=1-(1/2)**M
print(sym.summation(n*t*p*q**(n-1), (n, 1, oo)))


### FIXED CODE ###

N,M=map(int,input().split())
print((M*1900+100*(N-M))*(2**M))
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

def dfs(loc,num):
    root[loc]=num
    for item in plan[loc]:
        if root[item]==-1:
            dfs(item,num)
    return 0

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

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

plan=[[]for i in range(N)]
root=[-1]*N

for _ in range(M):
    a,b=map(int,input().split())
    plan[a-1].append(b-1)
    plan[b-1].append(a-1)

for i in range(N):
    if root[i]==-1:
        dfs(i,i)

ans=0
for i in range(N):
    if root[i]==root[P[i]-1]:
        ans+=1
#print(root)
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
 
sys.setrecursionlimit(10**7)

def dfs(num,hiyo):
    ans[num]=hiyo
    for to,cos in way[num]:
        if ans[to]==-1:
            dfs(to,hiyo+cos)
    
    return 

N=int(input())

way=[[] for i in range(N)]
ans=[-1]*N

for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    way[u].append([v,w])
    way[v].append([u,w])

#lis.sort(key=lambda x:(x[0],x[1]))

dfs(0,0)
#print(ans)
for item in ans:
    print(item%2)
while True:
    a=list(map(int,input().split()))
    if a[0]==0 and a[1]==0:
        break
    a.sort()
    print("{} {}".format(a[0],a[1]))
    

### FIXED CODE ###

a,b,c=map(int,input().split())
d=[i for i in range(a,b+1)]
count=0
for i in d:
    if c%i==0:
        count+=1
print(count)
from itertools import product
n=int(input())

ans = 0
for i in range(3, 10):
    for s in product('357', repeat=i):
        if len(set(s)) < 3:
            continue
        753num = int(''.join(s))
        if  753num> n:
            break
        ans += 1
print(ans)


### FIXED CODE ###

from itertools import product
n=int(input())

ans = 0
for i in range(3, 10):
    for s in product('357', repeat=i):
        if len(set(s)) < 3:
            continue
        num = int(''.join(s))
        if  num > n:
            break
        ans += 1
print(ans)
N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
scores = []
for i in range(N):
  pos = P[i]-1
  s = [C[i]]
  j = 1
  while j < K and pos != i:
    s.append(s[-1]+C[pos])
    pos = P[pos]-1
    j += 1
  smax = max(s)
  length = len(s)
  if length < K and s[-1] > 0:
    smod = s[:K%length]
    smodmax = max(smod)
    scores.append(max(s[-1] * ((K//length)-1) + smax, s[-1] * (K//length), s[-1] * (K//length) + smodmax))
  else:
    scores.append(smax)
print(max(scores))

### FIXED CODE ###

N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
scores = []
for i in range(N):
  pos = P[i]-1
  s = [C[i]]
  j = 1
  while j < K and pos != i:
    s.append(s[-1]+C[pos])
    pos = P[pos]-1
    j += 1
  smax = max(s)
  length = len(s)
  if length < K and s[-1] > 0:
    if K%length != 0:
      smod = s[:K%length]
      smodmax = max(smod)
    else:
      smodmax = 0
    scores.append(max(s[-1] * ((K//length)-1) + smax, s[-1] * (K//length), s[-1] * (K//length) + smodmax))
  else:
    scores.append(smax)
print(max(scores))
h = map(int, input().split())
monster = list(h)

attack_count = 0
fin_flag = 0

print(monster)

while(fin_flag == 0):

    for i in range(len(monster)) :
        attack_count = attack_count + 1
        if(monster[i] == 1):
            if(i == 0 and monster[0] == 1):
                fin_flag = 1
                break
            monster.pop(i)
        else:
            monster.append(monster[i]//2)
            monster.append(monster[i]//2)
            monster.pop(i)

print(attack_count+1)

### FIXED CODE ###

h = input()

def myfunc(hp: 'int') -> 'int':
    if(hp == 1):
        return 1
    elif(hp > 1):
        return int(myfunc(hp/2)) * 2 + 1
    return hp


if __name__ == '__main__':
    ans = myfunc(int(h))
    print(ans)
n=int(input())
lst=[int(input()) for i in range(5)]
l=[0]*5
l.insert(0,n)
def counting(l,lst,ans):
    if l[5]==n:
        return ans
    else:
        for i in range(5,0,-1):
            res=min(l[i-1],lst[i-1])
            l[i]+=res
            l[i-1]-=res
        ans+=1
        return counting(l,lst,ans)
print(counting(l,lst,0))

### FIXED CODE ###

n=int(input())
lst=[int(input()) for i in range(5)]
m=min(lst)
import math
print(math.ceil(n/m)+4)
if X == 3 or X == 5 or X == 7:
  print('YES')
else:
  print('NO')
  


### FIXED CODE ###

X = int(input())

if X==3 or X==5 or X==7:
  print("YES")
else:
  print("NO")
import sys
input = sys.stdin.readline

def F(N,A,B):
    AB = list(zip(A,B))
    AB = [(a,b) for a,b in AB if a < b] # 有用なやつだけ
    AB.sort(key = lambda x: x[1]/x[0], reverse = True)
    if len(AB) == 0:
        return N
    if len(AB) == 1:
        a,b = AB[0]
        x = N//a
        return N + (b-a) * x
    if len(AB) == 2:
        (a,b),(c,d) = AB
        # 2種類目の硬価はa回未満しか使わない：ac個はa優先なので
        return max(N + (N - i * c) // a * (b-a) + i * (d-c) for i in range(M))
    # 効率の良いものから並んでいる
    dp = [0] * (N+1)
    for n in range(N+1):
        x = n
        for a,b in AB:
            if n >= a:
                y = dp[n-a] + b
                if x < y:
                    x = y
        dp[n] = x
    return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

### FIXED CODE ###

# 新ステージでは、一度全部どんぐりに直してから換金を始めるとしてよい

def F(N, A, B):
  # N個のどんぐりを、Aで換金してからBに持っていく
  # Bでどんぐりに直す
  dp = [0] * (N+1)
  for n in range(N+1):
    x = n
    for j in range(3):
      if n >= A[j]:
        y = dp[n-A[j]] + B[j]
        if x < y:
          x = y
    dp[n] = x
  return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)
import sys
num = sys.stdin.readline()
print(num**num)

### FIXED CODE ###

num = int(input())
print(num**3)
A, B, K = list(map(int, input().split()))


def cf(x1, x2):
    cf = []
    for i in range(2, min(x1, x2) + 1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)

    cf = sorted(cf)
    return cf

cf_list = cf(A, B)

if len(cf_list) == 0:
    print(1)
else:
    print(cf_list[-K])

### FIXED CODE ###

A, B, K = list(map(int, input().split()))
count = 0

for i in range(min(A, B), 0, -1):
    if A % i == 0 and B % i == 0:
        count += 1
    if count == K:
        print(i)
        exit()
def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


if __name__ == '__main__':
    H, W, K = map(int, input().split())

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            # print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    MOD = 1_000_000_007
    ANS = C[K - 1] % MOD
    print(ANS)


### FIXED CODE ###

def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


if __name__ == '__main__':
    H, W, K = map(int, input().split())

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            # print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    # MOD = 1_000_000_007  # Underscore is not supported until 3.6
    MOD = 1000000007
    ANS = C[K - 1] % MOD
    print(ANS)
N,K = map(int,input().split())
p = list(map(int,input().split()))
p.sort()
if len(p) >= 3:
    print(p[0]+p[1]+p[2])
else if len(p) == 2:
    print(p[0] + p[1])
else:
    print(p[0])
    

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
p.sort()
count = 0
if len(p) >= K:
    for i in range(K):
        count = count + p[i]
else:
    for i in p:
        count = count + i
        
print(count)
class unionFind:
    parent = []
    nums = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.nums = [1]*N

    def root(self, x):
        if x >= N:
            return(N-1)
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.nums[y] += self.nums[x]
            self.nums[x] = 0
            return


N, M = map(int, input().split())
G = unionFind(N)
ans = [0]*M
ab = [tuple(map(int, input().split())) for i in range(M)]

tmp = (N * (N-1)) // 2
for i, x in enumerate(reversed(ab)):
    a, b = x[0], x[1]
    ans[M-1-i] = tmp
    a = G.root(a-1)
    b = G.root(b-1)
    if a == b:
        continue
    else:
        tmp -= G.nums[a] * G.nums[b]
        G.parent[a] = b
        G.nums[b] += G.nums[a]
        G.nums[a] = 0


for i in range(M):
    print(ans[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)


class unionFind:
    parent = []
    nums = []

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.nums = [1]*n

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

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.nums[y] += self.nums[x]
            self.nums[x] = 0
            return


N, M = map(int, input().split())
G = unionFind(N)
ans = [0]*M
ab = [tuple(map(int, input().split())) for i in range(M)]

tmp = (N * (N-1)) // 2
for i, x in enumerate(reversed(ab)):
    a, b = x[0], x[1]
    ans[M-1-i] = tmp
    a = G.root(a-1)
    b = G.root(b-1)
    if a == b:
        continue
    else:
        tmp -= G.nums[a] * G.nums[b]
        G.parent[a] = b
        G.nums[b] += G.nums[a]
        G.nums[a] = 0


for i in range(M):
    print(ans[i])
A=input().split()
N=int(A[0])
del A[0]
B=[]
for i in range(N):
    B.append(0)
for i in range(N-1):
    B[int(A[i])-1]+=1
print(B)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
a=[]
for i in range(n):
  a.append(0)
for i in range(n-1):
  a[l[i]-1]+=1
for i in range(n):
  print(a[i])
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(D)[:len(D) - 2]))


### FIXED CODE ###

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]))
N =int(input())
A = list(map(int,input().rstrip().split(" ")))
Aq = []
DP = [0 for i in range(10 ** 5)]
DPP = []
ans = 0
for i in range(N):
    if i >= A[i]:
        ans += DP[i - A[i]] 
    DP[A[i] + i] += 1
    
print(ans)

### FIXED CODE ###

N =int(input())
A = list(map(int,input().rstrip().split(" ")))
Aq = []
DP = [0 for i in range(5 * 10 ** 5)]
DPP = []
ans = 0
for i in range(N):
    if i >= A[i]:
        ans += DP[i - A[i]]
    if A[i] <= N:
        DP[A[i] + i] += 1
    
print(ans)