Harryxun/stf_run huggingface dataset:
# Union Find

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 is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
f=lambda:map(int,input().split())
N,M,K=f()
uf=UnionFind(N)
check=[[0]*(N+1) for _ in [0]*(N+1)]
bro=[0]*(N+1)
AB=[]
for _ in [0]*M:
    a,b=f()
    AB.append((a,b))
    check[b][a]==1
    uf.unite(a,b)
for a,b in AB:
    if uf.is_same_group(a,b):
        bro[a]+=1
        bro[b]+=1
for _ in [0]*K:
    c,d=f()
    check[d][c]==1
    if uf.is_same_group(c,d):
        bro[c]+=1
        bro[d]+=1
for i in range(1,N+1):
    print(uf.count(i)-1-bro[i])

### FIXED CODE ###

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 is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
f=lambda:map(int,input().split())
N,M,K=f()
uf=UnionFind(N)
bro=[0]*(N+1)
AB=[]
for _ in [0]*M:
    a,b=f()
    AB.append((a,b))
    uf.unite(a,b)
for a,b in AB:
    if uf.is_same_group(a,b):
        bro[a]+=1
        bro[b]+=1
for _ in [0]*K:
    c,d=f()
    if uf.is_same_group(c,d):
        bro[c]+=1
        bro[d]+=1
for i in range(1,N+1):
    print(uf.count(i)-1-bro[i])
N,m,k = [int(x) for x in input().split()]
p = []
q = []
roots = [0]*(N+1)
rootmatome = [0]*(N+1)
tonari = [0]*(N+1)
dame = [0]*(N+1)
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
par = []
for i in range(N+1):
    par.append(i)
def root(x):
    if par[x] == x:
        return x
    return root(par[x])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    par[rx] = ry
def same(x,y):
    rx = root(x)
    ry = root(y)
    return rx == ry
for i in range(m):
    unite(p[i][0],p[i][1])
for i in range(1,N+1):
  roots[i] = root(i)
for i in range(1,N+1):
    rootmatome[roots[i]] += 1
for i in range(m):
    tonari[p[i][0]] += 1
    tonari[p[i][1]] += 1
for i in range(k):
    if roots[q[i][0]] == roots[q[i][1]]:
        dame[q[i][0]] += 1
        dame[q[i][1]] += 1
for i in range(1,N+1):
    print(rootmatome[roots[i]] - tonari[i] - dame[i] - 1,end=" ")          

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N,m,k = [int(x) for x in input().split()]
p = []
q = []
roots = [0]*(N+1)
rootmatome = [0]*(N+1)
tonari = [0]*(N+1)
dame = [0]*(N+1)
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
par = []
for i in range(N+1):
    par.append(i)
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])#この一文で早くなる
    return root(par[x])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    par[rx] = ry
for i in range(m):
    unite(p[i][0],p[i][1])
for i in range(1,N+1):
  roots[i] = root(i)
for i in range(1,N+1):
    rootmatome[roots[i]] += 1
for i in range(m):
    tonari[p[i][0]] += 1
    tonari[p[i][1]] += 1
for i in range(k):
    if roots[q[i][0]] == roots[q[i][1]]:
        dame[q[i][0]] += 1
        dame[q[i][1]] += 1
for i in range(1,N+1):
    print(rootmatome[roots[i]] - tonari[i] - dame[i] - 1,end=" ")
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))

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

if (n//10 == 9) or (n%10==9):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))

n = int(input())



if (n//10 == 9) or (n%10==9):
    print("Yes")
else:
    print("No")
a,b,c = [int(x) for x in inpput().split()]
print(b+c-a if b+c-a > 0 else 0)

### FIXED CODE ###

a,b,c = [int(x) for x in input().split()]
print(b+c-a if b+c-a > 0 else 0)
raw_input = [int(i)for i in input().split()]
n = raw_input[0]
m = raw_input[1:len(raw_input)-2]
y = raw_input[-n:]
y += [0]
remainder = 0
total = 0
for i in range(n+1):
    y[i] += remainder
    total += min(y[i], m[i])
    remainder = max(y[i] - m[i], 0)
print(total)

### FIXED CODE ###

from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() 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)]
mod = 1000000007


def main():
    n = I()
    monster = LI()
    ret = 0
    ans = sum(monster)
    savor_lim = LI()
    for i in range(n - 1, -1, -1):
        k = min(savor_lim[i], monster[i + 1])
        monster[i + 1] -= k
        savor_lim[i] -= k
        monster[i] -= min(savor_lim[i], monster[i])
    return ans - sum(monster)



print(main())
N = int(input())
num = list(map(int,input().split()))
count = 0
for _ in range(N):
  if min(num[:_+1]) == num[_]:
    count += 1

print(count)

### FIXED CODE ###

a,b = map(int,input().split())
if a == b:
  print('Yes')
else:
  print('No')
a

### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
GYN=['Yes','trumpet']
mo=10**9+7
imp='IMPOSSIBLE'

a,b,c=MI()
print(max(0,c-a+b))
input();a=eval(input().replace(' ','*'));print((a,-1)[a>10**18])

### FIXED CODE ###

n,*a=map(int,open(0).read().split());z=1
for i in a:
 if i>1e18//z:z=-1;break
 z*=i
print(0 if 0in a else z)
H , W ,A , B = map(int ,input().split())
matrix = [[0] * W for _ in range(H)]
idx = 0
k = 0
for i in range(H):
    for j in range(A):
        matrix[i][k] = 1
        k += 1
    k -= B - 1

for row in matrix:
    print(*row)

### FIXED CODE ###

H , W , A , B = map(int , input().split())
mat = [[1] * W for _ in range(H)]
for row in range(H):
    for col in range(W):
        if col < A and row < B or col >= A and row >= B:
            mat[row][col] = 0
for row in mat:
    print(*row,sep = "")
print()
N = int(input())
X = input()

cnt = X.count("1")
div = [0] * (cnt + 1)
for i in range(1, cnt + 1):
    for n in range(20):
        div[i] += i >> n & 1

memo = [-1] * (cnt + 1)
memo[0] = 0
for i in range(1, cnt + 1):
    memo[i] = memo[i % div[i]] + 1

res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)
        res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
    else:
        div = cnt - 1
        tmp = (res1 + div - pow(2, N - i - 1, div)) % div
    print(memo[tmp] + 1)


### FIXED CODE ###

N = int(input())
X = input()

cnt = X.count("1")
res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)

        if cnt - 1 > 0:
            res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    ans = 0
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
        ans += 1
    else:
        if cnt - 1 > 0:
            div = cnt - 1
            tmp = (res1 + div - pow(2, N - i - 1, div)) % div
            ans += 1
        else:
            tmp = 0

    while tmp > 0:
        ans += 1
        div = bin(tmp).count("1")
        tmp %= div
        
    print(ans)
n=int(input())
if n%2==0:
  return(0.5)
else:
  return((n+1)/(2*n))

### FIXED CODE ###

n=int(input())
if n%2==0:
  print(0.5)
else:
  print((n+1)/(2*n))
n, k = map(int,input().split())
a = list(map(int,input().split()))

s = [True] * n
c = [1]
now = 0
while s[now]:
    s[now-1] = False
    now = a[now]
    c.append(now)

start_cycle = c.index(c[-1])
loop = c[start_cycle:-1]
cycle = len(loop)

if k < start_cycle:
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])

### FIXED CODE ###

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

s = [-1] * n
c = [1]
t = 0
now = 0
while s[now] == -1:
    s[now] = t
    now = a[now] - 1
    c.append(now+1)
    t += 1

start_cycle = c.index(c[-1])
loop = c[start_cycle:-1]
cycle = len(loop)

if k < start_cycle:
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])
import sys


def main():
    a, b, c, x, y = map(int, input())

    min_price = None

    for i in range(max(x, y) + 1):
        nc = i * 2
        na = x - i
        if na < 0:
            na = 0
        nb = y - i
        if nb < 0:
            nb = 0

        price = na * a + nb * b + nc * c
        if min_price is None or price < min_price:
            min_price = price

    print(min_price)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    a, b, c, x, y = map(int, input().split())

    min_price = None

    for i in range(max(x, y) + 1):
        nc = i * 2
        na = x - i
        if na < 0:
            na = 0
        nb = y - i
        if nb < 0:
            nb = 0

        price = na * a + nb * b + nc * c
        if min_price is None or price < min_price:
            min_price = price

    print(min_price)


if __name__ == '__main__':
    main()
# ABC057 D - Maximum Average Sets
from collections import defaultdict
from math import factorial
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
def perm(n,r):
    return factorial(n)//factorial(n-r)

def comb(n,r):
    return perm(n,r)//factorial(r)

n,a,b=nm()
V=nl()

d=defaultdict(int)
for vv in V:
    d[vv]+=1

value=0
cnt=0
ans=0

V=list(set(V))
if len(V)==1:
    print(V[0])
    print(2**(b-a+1)-1)
    exit()

for k,v in sorted(d.items(),key=lambda x:x[0],reverse=True):
    if a>=v:
        value+=k*v
        cnt+=v
        a-=v
        b-=v
    elif a<v:
        if a==0 and v==1:
            one_flg=True
        for i in range(a,min(b,v)):
            value+=k*a
            cnt+=a
            nn=v
            kk=a
            ans=comb(nn, kk)
        break
if one_flg:
    ans=1
print(value/cnt)
print(ans)


### FIXED CODE ###

# ABC057 D - Maximum Average Sets
from collections import defaultdict
from math import factorial
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
def perm(n,r):
    return factorial(n)//factorial(n-r)
 
def comb(n,r):
    return perm(n,r)//factorial(r)

n,a,b=nm()
v=sorted(nl(), reverse=True)

if v[0]==v[a-1]:
    n = 0
    for vv in v:
        if vv!=v[0]: break
        n += 1

    ans = 0
    for k in range(a, min(b,n)+1):
        ans += comb(n, k)

else:
    n = k = 0
    for i,vv in enumerate(v):
        if vv==v[a-1]:
            if i<a: k += 1
            n += 1
    ans = comb(n,k)

print(sum(v[:a])/a)
print(ans)
w = input()
for i in set(w):
    if w.count(i)%2 == 1:
        print("No")
        exit(-1)

print("Yes")



### FIXED CODE ###

w = [input() for i in range(4)]
N = int(w[0])
K = int(w[1])
X = int(w[2])
Y = int(w[3])

paid = 0
for i in range(1,N+1):
    if i < K+1:
        paid += X
    else:
        paid += Y

print(paid)
n = int(input())
arr = [int(i) for i in list(input().split())]
def helper(arr):
	if len(arr) <= 1:
		return 0
	if len(arr) == 2:
		return abs(arr[1] - arr[0])
	way1 = abs(arr[-1] - arr[-2]) + helper(arr[:-1])
	way2 = abs(arr[-1] - arr[-3]) + helper(arr[:-2])
	return min(way1, way2 )

if n == 1:
	print(0)
elif n == 2:
	print(abs(arr[1] - arr[0]))
else:
	dp[0] = 0
	dp[1] = abs(arr[1] - arr[0])
	dp = [0]*n
	for i in range(2,len(arr)):
		dp[i] = min(dp[i-1] + abs(arr[i] - arr[i-1]), dp[i-2] + abs(arr[i] - arr[i-2]))
	print(dp[n-1])
# print(helper(arr))

### FIXED CODE ###

n = int(input())
arr = [int(i) for i in list(input().split())]
def helper(arr):
	if len(arr) <= 1:
		return 0
	if len(arr) == 2:
		return abs(arr[1] - arr[0])
	way1 = abs(arr[-1] - arr[-2]) + helper(arr[:-1])
	way2 = abs(arr[-1] - arr[-3]) + helper(arr[:-2])
	return min(way1, way2 )

if n == 1:
	print(0)
elif n == 2:
	print(abs(arr[1] - arr[0]))
else:
	dp = [0]*n
	dp[0] = 0
	dp[1] = abs(arr[1] - arr[0])
	for i in range(2,len(arr)):
		dp[i] = min(dp[i-1] + abs(arr[i] - arr[i-1]), dp[i-2] + abs(arr[i] - arr[i-2]))
	print(dp[n-1])
# print(helper(arr))
n,k=map(int,input().split())
L=[]
for s in range(n):
  a,b=map(int,input().split())
  L.append((a,b))
#print(L)
L=sorted(L,key=lambda x:x[0])
#print(L)
sun=0
for s in L:
  sun+=s[1]
  if sun+1>k:
    print(s[0])
    exit()

### FIXED CODE ###

a,b,c=map(int,input().split());print("Yes" if a<=c<=b else "No")
a,b,c,d = map(int,input().split())
za=abs(a)
zb=abs(b)
zc=abs(c)
zd=abs(d)
if b>=0 and d>=0 :
  if a>0 or c>0:
    print(b*d)
  else:
    ans=max(a*c,b*d)
    print(ans)
elif b<0 and d<0 :
  x=max(za,zb)
  y=max(zc,zd)
  print(x*y)
else:
  if b>=0 and d<0 :
  	x=max(za,zb)
  	y=max(zc,zd)
  	print(x*y)
  else:
  	x=max(za,zb)
  	y=max(zc,zd)
  	print(x*y)



### FIXED CODE ###

x=int(input())
if x ==1:
  print(0)
else:
  print(1)
R = input()
print(R*2*3.14)

### FIXED CODE ###

print(int(input())*2*3.14)
def partition(A, p, r):
    i = p - 1
    for j in range(p, r + 1):
        if A[j][1] <= A[r][1]:
            i += 1
            A[i], A[j] = A[j], A[i]

    return i


def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)


n = int(raw_input())
A = map(int, raw_input().split())

quick_sort(A, 0, n - 1)

print " ".join(map(str, A))

### FIXED CODE ###

n = int(raw_input())
x = map(int,raw_input().split())
x.sort()
for i in xrange(n):
	print x[i],
N = int(input())

A = []
for i in range(N):
    x,y,h = map(int, input().split())
    A.append([x,y,h])
for i in range(100+1):
    for j in range(100+1):
        lst = {}
        for x,y,h in A:
            if h == 0:
                continue
            tx, ty = abs(x-i), abs(y-j)
            H = h + tx + ty
            if H not in lst:
                lst[H] = 1
            else :
                lst[H] += 1
        if len(lst) == 1 and lst.keys()[0] != 0:
            print(i,j,H)



### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
    x,y,h = map(int, input().split())
    A.append([x,y,h])
H = max([h for x,y,h in A])
while True:
    for i in range(100+1):
        for j in range(100+1):
            for x,y,h in A:
                tx, ty = abs(x-i), abs(y-j)
                if max(H - tx - ty, 0) != h:
                    break
            else:
                print(i,j,H)
                exit()
    H += 1
N = int(input())
A = int(input())
B = int(input())

if N == 1:
  print('Hello World')
else:
  print(int(A+B))

### FIXED CODE ###

N = int(input())
if N == 1:
  print('Hello World')
else:
  A = int(input())
  B = int(input())
  print(int(A+B))
nums = input().split()
a = (nums[0])
b = (nums[1])
c = (nums[2])
if a < b < c:
    print(Yes)
else:
    print(No)

### FIXED CODE ###

nums = input().split()
a = int(nums[0])
b = int(nums[1])
c = int(nums[2])
if a < b < c:
    print('Yes')
else:
    print('No')
from itertools import groupby

[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1)

Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

Es_count = [len(list(g[1])) for g in groupby(sorted(Es))]
res = K * (K-1)
res %= 1000000007
for i in range(0, N):
    j = i + 1
    c = Es_count[i]
    if c > K-1:
        res = 0
        break
    res *= num_of_perms[c-1]
    res %= 1000000007

print(res)


### FIXED CODE ###

from itertools import groupby

[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1) % 1000000007

Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

if N == 1:
    res = K
else:
    res = K * (K-1)
    res %= 1000000007
    for g in groupby(sorted(Es)):
        c = len(list(g[1]))
        if c > K-1:
            res = 0
            break
        res *= num_of_perms[c-1]
        res %= 1000000007

print(res)
import sys
n = input().split()
ln = list(map(int, input().split()))
for l in ln:
  if l % 2 == 1:
    continue
  if l % 3 != 0 and l % 5 != 0:
    print("DENIED")
    sys.exit(1)
print("APPROVED")

### FIXED CODE ###

import sys
n = input().split()
ln = list(map(int, input().split()))
for l in ln:
  if l % 2 == 1:
    continue
  if l % 3 != 0 and l % 5 != 0:
    print("DENIED")
    sys.exit()
print("APPROVED")
b = input()
if b == 'A':
    print('C')
elif b == 'C':
    print('A')
elif b == 'G':
    print('T')
else b == 'T':
    print('G')


### FIXED CODE ###

b = input()
if b == 'A':
    print('T')
elif b == 'T':
    print('A')
elif b == 'G':
    print('C')
else:
    print('G')
#! /usr/bin/env python
N = input()
for i in range(1, 10):
    m = N / i
    if m.is_integer() and 1 <= m <= 9:
        print('Yes')
        break
    else:
        print('No')

### FIXED CODE ###

N=int(input())
f=0
for i in range(1,10):
    for j in range(1,10):
        if N==i*j:
            f=1
            break
    if f==1:
        break
if f==0:
    print("No")
else:
    print("Yes")
S = imput()
print(S*2*3.14)

### FIXED CODE ###

S = int(input())
print(S*2*3.14)
import math
input()
x = list(map(int, input().split()))
print(math.max(x) - math.min(x))

### FIXED CODE ###

input()
x = list(map(int, input().split()))
print(max(x) - min(x))
#abc147c　HonestOrUnkind
from itertools import product 
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if bit & (1<<i) :
            for a, b in XY[i]:
                if bit & (1<<a) != b:
                    flag = False 
                    break
    if flag:
        hoenst = max(honest, bin(i)[2:].count('1'))
print(ans)


### FIXED CODE ###

n = int(input())
evidences = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x-1, y))
result = 0
for i in range(1, 2**n):
    consistent = True 
    for j in range(n):
        if (i>>j) & 1 == 0:
            continue 
        for x, y in evidences[j]:
            if (i>>x)&1 != y:
                consistent = False 
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)
n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(n)]

ans = 0
for i,j,k in itertools.combinations(range(n),m):
    u = 0
    for l in range(3):
        u += abs(a[i][l] + a[j][l] + a[k][l])
    ans = max(ans,u)

print(ans)


### FIXED CODE ###

import itertools
n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(n)]

c = [0,1]
ans = 0
for l,j,k in itertools.product(c,repeat=3):
    ans = max(ans,sum(sorted([a[i][0]*(-1)**l+a[i][1]*(-1)**j+a[i][2]*(-1)**k for i in range(n)])[n-m:]))

print(ans)
n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[0 for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0
  p[0] = -1

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 1 and d[i] < cost
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY:
      if M[u][v] < d[v]:
        d[v] = M[u][v]
        p[v] = u
        color[v] = 1:

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]] 
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] == -1:
     M[i][j] = INFTY
   else:
     M[i][j] = G[n]:

print MST()

### FIXED CODE ###

n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[INFTY for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 2 and d[i] < cost:
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY and M[u][v] < d[v]:
        d[v] = M[u][v]
        p[v] = u
        color[v] = 1

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]]
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] != -1:
     M[i][j] = G[j]

print MST()
N, M = map(int, input().split())
group = []
tf = []
for i in range(M):
  A, B = map(int, input().split())
  if A and B not in tf:
    tf.append(A)
    tf.append(B)
    group.append([A,B])
  else:
    if A not in tf:
      tf.append(A)
      for j in range(len(group)):
        if B in group[j]:
          group[i].append(A)
          break
    else:
      tf.append(B)
      for j in range(len(group)):
        if A in group[j]:
          group[i].append(B)
          break
l = list(range(1,N+1))
for i in tf:
  if i in l:
    l.remove(i)
    
print(len(group)+len(l)-1)

### FIXED CODE ###

# Connect Cities
# Union Findデータ構造（素集合データ構造）
 
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
 
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
 
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n
 
	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]
 
	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)
 
		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x
 

		self.parents[y]=x

n,m=input2()
AB=[input_array() for _ in range(m)]
 
uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1

print(ans-1)