Harryxun/stf_run huggingface dataset:
def culc(i, dp, h, n):
  if i == n - 1 :
    return dp[n - 1]
  
  cost1 = abs(h[i - 1] - h[i + 1])
  cost2 = abs(h[i] - h[i + 1])
  
  dp.append(dp[i - 1] + cost1 if cost1 <= cost2 else dp[i] + cost2)
  return culc(i + 1, dp, h, n)
    

n = int(input())
h = [int(i) for i in input().split(" ")]

dp = [0, abs(h[0] - h[1])]
print(culc(1, dp, h, n))


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split(" ")]

dp = [0] * n
dp[1] = abs(h[1] - h[0])

for i in range(2, n, 1):
  cost1 = abs(h[i-2] - h[i])
  cost2 = abs(h[i-1] - h[i])
  dp[i] = min(dp[i-2] + cost1, dp[i-1] + cost2)

print(dp[n-1])
import math

A, B, H, M = map(int,input().split())


timeA = H + (M/60)
argA = (1/12)*timeA

argB = (1/60)*M


sitaA = 360*argA
sitaB = 360*argB



if argA == argB:
  print(abs(B-A))
elif argA > argB:
  c = math.sqrt(A**2 + B**2 - abs((2*A*B*math.cos(math.radians(sitaA-sitaB)))))
elif argA < argB:
  c = math.sqrt(A**2 + B**2 - abs((2*A*B*math.cos(math.radians(sitaB-sitaA)))))

print(c)  

### FIXED CODE ###

import math

A, B, H, M = map(int,input().split())

c = 0
timeA = H + (M/60)
argA = (1/12)*timeA

argB = (1/60)*M


sitaA = 360*argA
sitaB = 360*argB



if abs(sitaA-sitaB) == 180:
  print(A+B)
  exit()



if sitaA == sitaB:
  print(abs(B-A))
  exit()
elif sitaA > sitaB:
  c = math.sqrt(A**2 + B**2 - (2*A*B*math.cos(math.radians(sitaA-sitaB))))
elif sitaA < sitaB:
  c = math.sqrt(A**2 + B**2 - (2*A*B*math.cos(math.radians(sitaB-sitaA))))

print(c)
N = int(input())
S = input()

print (max(len(set(S[:i]) & set(S[i:])) for i in range(1,N-1)))

### FIXED CODE ###

N = int(input())
S = input()

a = [0] * N
for i in range(1, N-1):
  a[i] = len(set(S[:i]) & set(S[i:]))
print (max(a))
h = 0
w = 0
list1 = []

def dfs(x, y, f):
    list1[y] = list1[y][:x] + '1' + list1[y][x+1:]

    if y - 1 >= 0:
        if list1[y - 1][x] == f:
            dfs(x, y - 1, f)
    if y + 1 < h:
        if list1[y + 1][x] == f:
            dfs(x, y + 1, f)
    if x - 1 >= 0:
        if list1[y][x - 1] == f:
            dfs(x - 1, y, f)
    if x + 1 < w:
        if list1[y][x + 1] == f:
            dfs(x + 1, y, f)
    return 1

while True:
    h, w = list(map(lambda x: int(x),input().split(" ")))
    if 0 in (h, w):
        break
    n = 0
    for i in range(0, h):
        list1.append(input())
    for i in range(0, h):
        for j in range(0, w):
            if list1[i][j] != '1':
                n += dfs(j, i, list1[i][j])
    print(n)

### FIXED CODE ###

h = w = 0
slist =[]
list1=[]
def dfs(f):
    while True:
        if len(slist) == 0:
            return 1
        coordinate= slist.pop()
        #print(coordinate)
        x = coordinate[0]
        y = coordinate[1]

        list1[y] = list1[y][:x] + '1' + list1[y][x + 1:]
        if x + 1 < w:
            if list1[y][x + 1] == f:
                slist.append([x + 1,y])
        if x - 1 >= 0:
            if list1[y][x-1] == f:
                slist.append([x - 1, y])
        if y + 1 < h:
            if list1[y + 1][x] == f:
                slist.append([x, y + 1])
        if y -1 >= 0:
            if list1[y -1][x] == f:
                slist.append([x, y - 1])

while True:
    h, w = list(map(lambda x: int(x),input().split(" ")))
    if 0 in (h, w):
        break
    n = 0
    for i in range(0, h):
        list1.append(input())
    for i in range(0, h):
        for j in range(0, w):
            if list1[i][j] != '1':
                slist.append([j,i])
                n += dfs(list1[i][j])
            #print(list1)
    print(n)
    list1=[]
S = str(input())
T = str(input())
mini = []
for i in range(len(S) - len(T)):
    count = 0
    for j in range(len(T)-1):
        if T[j] == S[j+i]:        
            count+=1
    mini.append(len(T) - count)
print(min(mini))

### FIXED CODE ###

S = str(input())
T = str(input())
mini = []

if len(S) != len(T):
    for i in range(len(S) - len(T)):
        count = 0
        for j in range(len(T)):
            if T[j] == S[j+i]:        
                count+=1
        mini.append(len(T) - count)
    print(min(mini))
else:
    count = 0
    for i in range(len(S)):
       if T[i] == S[i]:
           count+=1
    print(len(T) - count)
N,K = list(map(int,input(),split()))
for i in range(100):
  if K**i <= N < K**(i+1):
    print(i+1）

### FIXED CODE ###

n,k = list(map(int,input().split()))
for i in range(100):
  if k**i <= n < k**(i+1):
    print(i+1)
# m-solutions2019C - Best-of-(2n-1) (292 ms)
def get_inv(lim: int) -> list:
    # compute a table of inverse factorials (1-idx)
    inv = [0] * (lim + 1)
    inv[:2] = 1, 1
    for i in range(2, lim + 1):
        inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD
    return inv


def main():
    global MOD
    N, A, B, C = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    inv = get_inv(100, 2 * N)
    pa, pb = [1] * (N + 1), [1] * (N + 1)  # power of a, b
    a, b = A * inv[A + B], B * inv[A + B]
    for i in range(1, N + 1):
        pa[i] = pa[i - 1] * a % MOD
        pb[i] = pb[i - 1] * b % MOD
    ans, comb = (pa[N] + pb[N]) * N, 1
    for m in range(N + 1, 2 * N):
        comb = (comb * (m - 1) * inv[m - N]) % MOD
        x = comb * (pa[N] * pb[m - N] + pa[m - N] * pb[N]) * m
        ans = (ans + x) % MOD
    ans = ans * 100 * inv[100 - C] % MOD
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# m-solutions2019C - Best-of-(2n-1) (292 ms)
def get_inv(lim: int) -> list:
    # compute a table of inverse factorials (1-idx)
    inv = [0] * (lim + 1)
    inv[:2] = 1, 1
    for i in range(2, lim + 1):
        inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD
    return inv


def main():
    global MOD
    N, A, B, C = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    inv = get_inv(max(100, 2 * N))
    pa, pb = [1] * (N + 1), [1] * (N + 1)  # power of a, b
    a, b = A * inv[A + B], B * inv[A + B]
    for i in range(1, N + 1):
        pa[i] = pa[i - 1] * a % MOD
        pb[i] = pb[i - 1] * b % MOD
    ans, comb = (pa[N] + pb[N]) * N, 1
    for m in range(N + 1, 2 * N):
        comb = (comb * (m - 1) * inv[m - N]) % MOD
        x = comb * (pa[N] * pb[m - N] + pa[m - N] * pb[N]) * m
        ans = (ans + x) % MOD
    ans = ans * 100 * inv[100 - C] % MOD
    print(ans)


if __name__ == "__main__":
    main()
H, M, h, m, K = map(int, input().slpit())

print( max(0, 60*(h-H) + m - M - K) )

### FIXED CODE ###

H, M, h, m, K = map(int, input().split())

print( max(0, 60*(h-H) + m - M - K) )
INF=1000000000
def getans(i):
    if i>=(n-1):
        dp[n-1]= 0
        return dp[n-1]
    if dp[i]!=-1:
        return dp[i]
    if i==(n-2):
        dp[i]=abs(h[i]-h[i+1])
        return dp[i]
    else:
        dp[i]=min(abs(h[i]-h[i+1])+getans(i+1),abs(h[i]-h[i+2])+getans(i+2))
        return dp[i]


n=int(input())
dp=[-1]*n
h=list(map(int,input().split()))
ans=getans(0)
print(ans)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(n-1):
    dp[i+1]=min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
    if i+2<n:
        dp[i+2]=min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
print(dp[-1])
import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
for i in range(len(S_dict)):
    if(SS[S[i]]== max(SS.values())):
        res.append(S[i])
res.sort()
for i in range(len(res)):
    print(res[i])
    

### FIXED CODE ###

import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
m = max(SS.values())
for i in SS.keys():
    if(SS[i]== m):
        res.append(i)
res.sort()
for i in range(len(res)):
    print(res[i])
def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in [0] * N)

    before_t = A[0][0]
    before_a = A[0][1]
    for t, a in A[1:]:
        n1 = -(-before_t // t)
        n2 = -(-before_a // a)
        n = max(n1, n2)
        taka, aoki = t * n, a * n
        before_t, before_a = taka, aoki

    print(taka + aoki)

main()


### FIXED CODE ###

def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in [0] * N)

    if N == 1:
        print(sum(A[0]))
        return

    before_t = A[0][0]
    before_a = A[0][1]
    for t, a in A[1:]:
        n1 = -(-before_t // t)
        n2 = -(-before_a // a)
        n = max(n1, n2)
        taka, aoki = t * n, a * n
        before_t, before_a = taka, aoki

    print(taka + aoki)

main()
#文字列wordの文字の種類の構成の表現のためのリストを返す関数
def connection_count(word)->list:
    i=0
    a=[]
    count=1
    while i<(len(word)-1):
        while word[i]==word[i+1]:
            count+=1
            i+=1
            if i>=(len(word)-1):
                break
        a.append(count)
        count=1
        i+=1
    if a[-1]==1:
        a.append(count)
    return a

#S:文字列、K：繰り返す回数
S=input()
K=int(input())

#Sの文字の種類の構成を表現するためのリスト
connection=connection_count(S)

#結果の表示

#すべての文字が同じ場合
if len(connection)==1:
    print(((connection[0]*K)//2))
#最初と最後の文字が異なる場合
elif S[0]!=S[-1]:
    connection2=list(map(lambda x:x//2,connection))
    print((sum(connection2)*K))
#最初と最後の文字が同じ場合（すべての文字が同じ場合を除く）
else:
    t=S*2
    connection2=list(map(lambda x:x//2,connection))
    connection3=list(connection_count(t))
    connection4=map(lambda x:x//2,connection3)
    a=sum(connection2)
    b=sum(connection4)
    ans=a+(b-a)*(K-1)
    print(ans)


### FIXED CODE ###

import sys

#文字列wordの文字の種類の構成の表現のためのリストを返す関数
def connection_count(word)->list:
    i=0
    a=[]
    count=1
    while i<(len(word)-1):
        while word[i]==word[i+1]:
            count+=1
            i+=1
            if i>=(len(word)-1):
                break
        a.append(count)
        count=1
        i+=1
    if a[-1]==1:
        a.append(count)
    return a

#S:文字列、K：繰り返す回数
S=input()
K=int(input())

#Sが一文字の場合(例外処理）
if len(S)==1:
    print(K//2)
    sys.exit()

#Sの文字の種類の構成を表現するためのリスト
connection=connection_count(S)

#すべての文字が同じ場合
if len(connection)==1:
    print(((connection[0]*K)//2))
#最初と最後の文字が異なる場合
elif S[0]!=S[-1]:
    connection2=list(map(lambda x:x//2,connection))
    print((sum(connection2)*K))
#最初と最後の文字が同じ場合（すべての文字が同じ場合を除く）
else:
    t=S*2
    connection2=list(map(lambda x:x//2,connection))
    connection3=list(connection_count(t))
    connection4=map(lambda x:x//2,connection3)
    a=sum(connection2)
    b=sum(connection4)
    ans=a+(b-a)*(K-1)
    print(ans)
N,X=map(int,input().split())
x=list(map(int,input().split()))
for i in range(N):
    if abs(x[i]-X)==0:
        continue
    x[i]=abs(x[i]-X)
for i in range(N-1):
    ans=gcd(x[i],x[i+1])
print(gcd)


### FIXED CODE ###

from fractions import gcd
N,X=map(int,input().split())
x=list(map(int,input().split()))
for i in range(N):
    if abs(x[i]-X)==0:
        continue
    x[i]=abs(x[i]-X)

ans=x[0]
for i in range(N):
    ans=gcd(ans,x[i])
print(ans)
import fractions
n,m=map(int,input().split())
lis  = list(map(int,input().split()))
#aそれぞれを2で割ったものを持っておく
div = []
for i in range(n):
    div.append(lis[i]//2)
#lisそれぞれの要素を2で割り切れる回数をすべて数える
L = []
for i in range(n):
    cnt = 0
    while lis[i] %2 ==0:
        lis[i] //= 2
        cnt += 1
    L.append(cnt)

bl = True
for i in range(n-1):
    if L[0] != L[i+1]:
        bl = False
        print(0)
        break
#div内の最小子公倍数Tを求める
T = 0
ans = div[0]
for i in range(1,n):
    ans =ans*div[i]//fractions.gcd(ans,div[i])
    T = ans

S = m//T
if S %2 ==0:
    print(S//2)
else:
    print(S//2 +1)

### FIXED CODE ###

import fractions
n,m=map(int,input().split())
lis  = list(map(int,input().split()))
#aそれぞれを2で割ったものを持っておく
div = []
for i in range(n):
    div.append(lis[i]//2)
#lisそれぞれの要素を2で割り切れる回数をすべて数える
L = []
for i in range(n):
    cnt = 0
    while lis[i] %2 ==0:
        lis[i] //= 2
        cnt += 1
    L.append(cnt)

bl = True
#重複要素を削除して要素数でLがすべて一緒か判断
def set_list(es):
    return len(list(set(es))) == 1

if set_list(L) != 1:
    print(0)
    exit()

#div内の最小子公倍数ansを求める

ans = div[0]
for i in range(1,n):
    ans =ans*div[i]//fractions.gcd(ans,div[i])

S = m//ans
if S %2 ==0:
    print(S//2)
else:
    print(S//2 +1)
from bisect import bisect_left
from collections import deque
"""
行き ⇨ dp LIS計算とstack登録
帰り ⇨ stackをpop dp巻き戻し
"""

n = int(input())
As = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)


INF = 10**10
dp = []
pos = 0
ans = [0] * n
q = deque([])
def dfs(v,p):
    global pos
    # 行き
    a = As[v]
    ind = bisect_left(dp, a)
    if ind == len(dp): 
        dp.append(a)
        # 引数の1つ目はappendしたか
        q.append((True, -1, -1))
    else:
        # 更新
        tmp = dp[ind]
        dp[ind] = a
        q.append((False,ind,tmp))

    ans[v] = len(dp)
    for u in edges[v]:
        if u == p:continue
        dfs(u,v)
        # 帰り        
        isappend, ind, tmp = q.pop()
        if isappend:
            dp.pop()
        else:
            dp[ind] = tmp
        
    
dfs(0,-1)

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

from bisect import bisect_left
from collections import deque
"""
行き ⇨ dp LIS計算とstack登録
帰り ⇨ stackをpop dp巻き戻し
"""

n = int(input())
As = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)


INF = 10**10
dp = []
pos = 0
ans = [0] * n
q = deque([])
def dfs(v,p):
    global pos
    # 行き
    a = As[v]
    ind = bisect_left(dp, a)
    if ind == len(dp): 
        dp.append(a)
        # 引数の1つ目はappendしたか
        q.append((True, -1, -1))
    else:
        # 更新
        tmp = dp[ind]
        dp[ind] = a
        q.append((False,ind,tmp))

    ans[v] = len(dp)
    for u in edges[v]:
        if u == p:continue
        dfs(u,v)
        # 帰り        
        isappend, ind, tmp = q.pop()
        if isappend:
            dp.pop()
        else:
            dp[ind] = tmp
        
    
dfs(0,-1)

print(*ans)
N = int(input())

if N => 195:
    print("4")
elif N => 165:
    print("3")
elif N => 135:
    print("2")
elif N => 105:
    print("1")
else:
    print("0")

### FIXED CODE ###

N = int(input())

if N >= 195:
    print("5")
elif N >= 189:
    print("4")
elif N >= 165:
    print("3")
elif N >= 135:
    print("2")
elif N >= 105:
    print("1")
else:
    print("0")
n = int(input())
cnt = dict()
xy = [tuple(map(int, input().split())) for _ in range(n)]
for x1, y1 in xy:
    for x2, y2 in xy:
        if x1 == x2 and y1 == y2:
            continue
        dx = x1 - x2
        dy = y1 - y2
        if (dx, dy) not in cnt:
            cnt[(dx, dy)] = 1
        else:
            cnt[(dx,dy)] += 1
print(n - max(cnt.values()))


### FIXED CODE ###

n = int(input())
cnt = dict()
xy = [tuple(map(int, input().split())) for _ in range(n)]
if n == 1:
    print(1)
    exit()
for x1, y1 in xy:
    for x2, y2 in xy:
        if x1 == x2 and y1 == y2:
            continue
        dx = x1 - x2
        dy = y1 - y2
        if (dx, dy) not in cnt:
            cnt[(dx, dy)] = 1
        else:
            cnt[(dx,dy)] += 1
print(n - max(cnt.values()))
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B)
dp = np.array([[np.zeros(80**2) for _ in range(W)] for _ in range(H)], np.bool)
start = 80**2//2
begin = diff[0][0]
dp[0][0][start+begin] = True
dp[0][0][start-begin] = True
for i in range(H):
    for j in range(W):
        d = diff[i][j]
        if i > 0:
            dp[i][j][d:] = np.logical_or(dp[i][j][d:], dp[i-1][j][:-d])
            dp[i][j][:-d] = np.logical_or(dp[i][j][:-d], dp[i-1][j][d:])
        if j > 0:
            dp[i][j][d:] = np.logical_or(dp[i][j][d:], dp[i][j-1][:-d])
            dp[i][j][:-d] = np.logical_or(dp[i][j][:-d], dp[i][j-1][d:])

result = dp[H-1][W-1][start:]
answer = np.where(result==True)[0].min()
print(answer)
# 44

### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = [lr() for _ in range(H)]
B = [lr() for _ in range(H)]
diff = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

X = (H+W) * 80
L = X + X + 1 #真ん中を0とする、最後に-X
dp = [[None] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][X+diff[0][0]] = 1; dp[0][0][X-diff[0][0]] = 1 #非負整数のみでも良い
for h in range(H):
    for w, di in enumerate(diff[h]):
        if h == 0 and w == 0:
            continue
        x = np.zeros(L, np.bool)
        if h > 0:
            x[di:] |= dp[h-1][w][:L-di]
            x[:L-di] |= dp[h-1][w][di:]
        if w > 0:
            x[di:] |= dp[h][w-1][:L-di]
            x[:L-di] |= dp[h][w-1][di:]
        dp[h][w] = x

dp = dp[-1][-1]
possible = np.where(dp)[0] - X
answer = np.abs(possible).min()
print(answer)
# 07
s=sorted;print(['No','Yes'][s(input())<s(input())[-1]])

### FIXED CODE ###

print('Yes'if sorted(input())<sorted(input(),reverse=1)else'No')
N = int(input())
ai = [int(x) for x in input().split()]


c = 0

for i in range(N):
  if i % 2 == 1 and a[i] % 2 ==1:
    c += 1
  
print(c)

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
 
c = 0

for i in range(N):
  if i % 2 == 0 and a[i] % 2 ==1:
    c += 1
print(c)
d,t,s = map(int,input().split())
if d/s<=t:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

d,t,s = map(int,input().split())
if (d/s)<=t:
  print("Yes")
else:
  print("No")
from collections import defaultdict

def dfs(source, used, all_weight, connect):
    max_weight = all_weight
    max_source = source
    used[source] = 1
    for target, weight in connect[source]:
        if not used[target]:
            now_weight = all_weight + weight
            this_source, this_weight = dfs(target, used, now_weight, connect)
            if max_weight < this_weight:
                max_weight = this_weight
                max_source = this_source
    return [max_source, max_weight]

vertice = int(input())
connect = defaultdict(list)
for _ in range(vertice - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight])
    connect[v2].append([v1, weight])
answer = 0
start_v = 0
for i in range(2):
    used = [0 for n in range(vertice)]
    start_v, answer = dfs(start_v, used, 0, connect)
print(answer)

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(200000)

def dfs(source, used, all_weight, connect):
    max_weight = all_weight
    max_source = source
    used[source] = 1
    for target, weight in connect[source]:
        if not used[target]:
            now_weight = all_weight + weight
            this_source, this_weight = dfs(target, used, now_weight, connect)
            if max_weight < this_weight:
                max_weight = this_weight
                max_source = this_source
    return [max_source, max_weight]

vertice = int(input())
connect = defaultdict(list)
for _ in range(vertice - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight])
    connect[v2].append([v1, weight])
answer = 0
start_v = 0
for i in range(2):
    used = [0 for n in range(vertice)]
    start_v, answer = dfs(start_v, used, 0, connect)
print(answer)
import math

A,B,C,D=map(int,input().split())
c=B//C-(A-1)//C 
d=B//D-(A-1)//D 
l=C*D/math.gcd(C,D)
cd=B//l-(A-1)//l
print(int(B-(A-1)-c-d+cd))

### FIXED CODE ###

import fractions

A,B,C,D=map(int,input().split())
c=B//C-(A-1)//C 
d=B//D-(A-1)//D 
l=C*D//fractions.gcd(C,D)
cd=B//l-(A-1)//l
print(int(B-(A-1)-c-d+cd))
import sys
sys.setrecursionlimit(int(1e9))
N, M = map(int, input().split())
class uft:
  def __init__(self, N):
    self.__N = N
    self.__arr = [-1] * (N + 1)
  def fp(self, x):
    if self.__arr[x] < 0:
      return x
    else:
      self.__arr[x] = self.fp(self.__arr[x])
      return self.__arr[x]
  def add(self, x, y):
    if x > y:
      x, y = y, x
    if x == y:
      return 1
    px = self.fp(x)
    py = self.fp(y)
    self.__arr[px] += self.__arr[py]
    self.__arr[py] = px
  def groups(self):
    ret = -1
    for i in self.__arr:
      if i < 0:
        ret += 1
    return ret
UFT = uft(N)

for i in range(M):
  A, B = map(int, input().split())
  UFT.add(A,B)
print(UFT.groups() -1)



### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e9))

class uft:
  def __init__(self, N):
    self.__N = N
    self.__arr = [-1] * (N + 1)
  def fp(self, x):
    if self.__arr[x] < 0:
      return x
    else:
      self.__arr[x] = self.fp(self.__arr[x])
      return self.__arr[x]
  def add(self, x, y):
    px = self.fp(x)
    py = self.fp(y)
    if px > py:
      px, py = py, px
    if px == py:
      return 1
    self.__arr[px] += self.__arr[py]
    self.__arr[py] = px
  def groups(self):
    ret = -1
    for i in self.__arr:
      if i < 0:
        ret += 1
    return ret
  def show_arr(self):
    print(self.__arr)
  
N, M = map(int, input().split()) 
UFT = uft(N)

for i in range(M):
  A, B = map(int, input().split())
  UFT.add(A,B)
print(UFT.groups() -1)
s,t = list(map(int, input().split()))
print(s+t)

### FIXED CODE ###

s,t = input().split()
print(t+s)
X=map(int,input().split())

if(X>=30):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a=int(input())

if(a>=30):
  print("Yes")
else:
  print("No")
with open ('in1.txt', 'r', encoding='utf8') as input:
    s = input.readline()
    i=1
    while True:
        print("case {0}: {1}".format(i,s))
        i += 1
        s = input()
        if s=="0":
            break

### FIXED CODE ###

a = []
i = 0
while True:
    n = input()
    if n == "0":
        break
    a.append(n)
    i += 1
    print("Case {0}: {1}".format(i,n))
n = int(input())
 
l1 = []
for i in range(1, int(n ** 0.5)):
  q, mod = divmod(n , i)
  if mod == 0:
    l1.append(q + i -2)
print(min(l1))

### FIXED CODE ###

n = int(input())
 
l1 = []
for i in range(1, int(n ** 0.5) + 1):
  q, mod = divmod(n , i)
  if mod == 0:
    l1.append(q + i -2)
print(min(l1))