Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import combinations

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=1<<60

for rail in range(N-1):
    I=combinations(range(N),rail)

    for rails in I:
        #print(rails)
        if ANS==0:
            break

        for i in range(1<<rail):
            X=[0]
            Y=[0]
            for j in range(rail):
                if (1<<j) & i ==0:
                    X.append(P[rails[j]][0])
                else:
                    Y.append(P[rails[j]][1])

            C=0
            for x,y,p in P:
                MIN=1<<30
                for xx in X:
                    MIN=min(abs(xx-x),MIN)
                for yy in Y:
                    MIN=min(abs(yy-y),MIN)

                C+=MIN*p
                if C>=ANS:
                    break

            #print(X,Y,C)

            ANS=min(ANS,C)

    print(ANS)

ANS=1<<60
for x,y,c in P:
    ANS=min(ANS,abs(x)*c,abs(y)*c)
    for xx,yy,cc in P:
        if x==xx and y==yy:
            continue
        ANS=min(ANS,abs(x-xx)*c,abs(y-yy)*c)

print(ANS)
print(0)
                    
                
                

            
            
        
    
    




### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=[1<<60]*(N+1)
ANS[-1]=0

DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

dfs(DP1,0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)
### BUGGY CODE ###

n = int(input())

s = []
ans = 0
for i in range(n):
    si = input()
    si = sorted(si)
    ss = ""
    for a in si:
        ss += a
    s.append(ss)

sset = list(set(s))

if(len(sset) == len(s)):
    print(0)
else:
    for e in sset:
        if(s.count(e) == 1):
            continue
        ans += s.count(e) * (s.count(e) - 1) // 2

    print(ans)

### FIXED CODE ###

n = int(input())

s = []
dic = {}
ans = 0
for i in range(n):
    si = input()
    si = sorted(si)
    ss = ""
    for a in si:
        ss += a
    if(ss in dic):
        dic[ss] += 1
    else:
        dic[ss] = 1

for e in dic:
    if(dic[e] == 1):
        continue
    ans += dic[e] * (dic[e] - 1) // 2

print(ans)
### BUGGY CODE ###

#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)

def main():
    N, K = LI()
    A = LI()

    for _ in range(K):
        B = [0]*(N+1)
        for i in range(N):
            l = max(i - A[i], 0)
            r = min(A[i] + i + 1, N)
            B[l] += 1
            B[r] -= 1
        for i in range(N):
            B[i+1] += B[i]

        if A == B:
            break
        A = B
    print(*A[:-1], sep=" ")
main()


### FIXED CODE ###

#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)

def main():
    N, K = LI()
    A = LI()

    for _ in range(K):
        B = [0]*(N+1)
        for i in range(N):
            l = max(i - A[i], 0)
            r = min(A[i] + i + 1, N)
            B[l] += 1
            B[r] -= 1
        for i in range(N):
            B[i+1] += B[i]

        if A == B:
            break
        A = B
    print(*A[:-1], sep=" ")


main()
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A)

NMAX=2*10**5

tmp = [0]*(NMAX+1)
for n in c:
    tmp[n] = (c[n] * (c[n] - 1) // 2)

for a in A:
    sum = 0
    for i in c:
        if a ==i:
            n =c[i]-1
            sum += n * (n - 1) // 2
        else:
            sum += tmp[i]

    print(sum)



### FIXED CODE ###

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

import collections 
c=collections.Counter(A)
sum=0
for i in c:
  sum+=c[i]*(c[i]-1)//2  
for a in A:
  print(sum - c[a]*(c[a]-1)//2 + (c[a]-1)*(c[a]-2)//2)
### BUGGY CODE ###

from numpy import cumsum
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = cumsum([0] + A)
B = cumsum([0] + B)
n_read = 0
b_tail = B[-1]
for i, a in enumerate(A):
    if a > k:
        break
    j = m
    if b_tail + a > k:
        for j, b in enumerate(B):
            if a + b > k:
                j -= 1
                break
    n_read = max(n_read, i + j)
print(n_read)


### FIXED CODE ###

from numpy import cumsum
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = cumsum([0] + A)
B = cumsum([0] + B)
n_read = 0
l = len(B) - 1
for i, a in enumerate(A):
    if a > k:
        break
    for j, b in enumerate(B[l::-1]):
        if a + b <= k:
            l -= j
            n_read = max(n_read, i + l)
            break
print(n_read)
### BUGGY CODE ###

import sys
import os
from collections import deque


def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

N,M = LI()
AB = [LI() for _ in range(M)]

if M==0:
    print(1)
    exit()

# 無向グラフ
G = []
for _ in [0]*N:
    G.append([False]*N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    G[f][t] = True
    G[t][f] = True

used = [False] * N

ss = []
for i in range(N):
    if used[i]==True:
            continue
    s = set()
    que = deque([])
    que.append(i)
    while que:
        p = que.popleft() 
        if used[p]==True:
            continue
        s.add(p)
        used[p]=True   
        for i, x in enumerate(G[p]):
            if x == True:
                if used[i]==True:
                    continue
                if not i in que:
                    que.append(i)
    ss.append(len(s))


    # for i, x in enumerate(G[i]):
    #     if x == True:
    #         if used[i]==True:
    #             continue
    #         for j,y in enumerate(x):
    #             if used[j]==True:
    #                 continue
    #             if x == True and used[i]==False:
    #                 s.add(i)


    # l = [i for i, x in enumerate(G[i]) if x == True and used[i]==False]
    # for j in l:
    #     used[j]=True
    #     s.add(j)
    #     for i,x in enumerate(G[i]):
    #         if x == True and used[i]==False:
    #             s.add(i)

print(max(ss))

### FIXED CODE ###

import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N,M = LI()
AB = [LI() for _ in range(M)]

ans = 0

par = [0]*N
# rank = [0]*N

def init(n):
    for i in range(n):
        # 親のID or 属する頂点の数
        par[i]=-1
        # rank[i] = 0

# rootを返す
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
    if (par[x] > par[y]):
        x,y = y,x
    # rootの頂点数を結合
    par[x] += par[y]
    # yの親をxに
    par[y] = x
    return

    # if (rank[x]<rank[y]):
    #     par[x]=y
    # else:
    #     par[y]=x
    #     if rank[x] == rank[y]:
    #         rank[x] += 1

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

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

init(N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    unite(f,t)
    # print(par)

for i in range(N):
    # print(size(i))
    ans = max(ans,size(i))

print(ans)
### BUGGY CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp1 = [[0] * (K+1)]
    dp1[0][0] = 1
    for a in As:
        ndp = []
        pdp = dp1[-1]
        for i in range(K+1):
            ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
        dp1.append(ndp)
    
    dp2 = [[0] * (K+1)]
    dp2[0][0] = 1
    for a in reversed(As):
        ndp = []
        pdp = dp2[-1]
        for i in range(K+1):
            ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
        dp2.append(ndp)
    accs2 = [list(accumulate(dp)) + [0] for dp in dp2]
    
    ans = 0
    for i in range(1, N+1):
        a = As[i-1]
        if a >= K:
            continue
        dp = dp1[i-1]
        acc2 = accs2[N-i]
        for y in range(K+1):
            if dp[y] == 0:
                continue
            t = K-y-a-1
            if acc2[K-y-1] > acc2[t if t >= 0 else -1]:
                break
        else:
            ans += 1
    print(ans)

main()


### FIXED CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()
### BUGGY CODE ###

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

min = 10**18

while True:
  n = abs(n-k)
  if min > n:
    min = n
  else:
    break

print(min)






### FIXED CODE ###

n,k = map(int, input().split())
n = n % k
a = abs(n-k)
if n <= a:
  print(n)
else:
  print(a)
### BUGGY CODE ###

import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# グラフつくる
graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
sources = []
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        a, b = min(a, b), max(a, b)
        c, d = i, A[i][j + 1] - 1
        c, d = min(c, d), max(c, d)

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1
        sources.append(a * N + b)

# トポロジカルソート
S = []
for v in range(N ** 2):
    if ins[v] == 0:
        S.append(v)
L = []
while S:
    v = S.pop()
    L.append(v)
    for u in graph[v]:
        ins[u] -= 1
        if ins[u] == 0:
            S.append(u)

if len(L) != N ** 2:
    print(-1)
    exit()


@lru_cache(maxsize=None)
def dfs(v):
    ret = 0
    for u in graph[v]:
        ret = max(ret, dfs(u))
    return ret + 1


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)
# DAG の最長パスが答え


### FIXED CODE ###

import os
import sys
from collections import defaultdict, deque
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    for i in range(num):
        array.append(int(tmp.split()[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        count += 1
        if(count == 1):
            prev = tmp
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1
        else:
            if prev < tmp and div == -1:
                ans += 1
                div = 0
            elif prev > tmp and div == 1:
                ans += 1
                div = 0


        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import pdb


def main():
    num = int(input())
    array = []
    tmp = input()
    tmp = tmp.split()
    for i in range(num):
        array.append(int(tmp[i]))
        
    ans = 1
    div = 0
    prev = 0
    count = 0
    #pdb.set_trace()
    for tmp in array:
        count += 1
        if count == 1:
            prev = tmp
            continue

        if div == 0:
            if prev < tmp:
                div = 1
            elif prev > tmp:
                div = -1
        else:
            if prev < tmp and div == -1:
                ans += 1
                div = 0
            elif prev > tmp and div == 1:
                ans += 1
                div = 0
                
        prev = tmp
        
    print(ans)

        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
data = [list(map(int, input().split())) for _ in range(M)]

MIN = a[0] + b[0]

for i in range(A):
    for j in range(B):
        
        for k in data:
            if k[0]-1 == i and k[1]-1 == j:
                MIN = min(a[i]+b[j]-k[2], MIN)

        MIN = min(a[i]+b[j], MIN) 

print(MIN)

### FIXED CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
data = [list(map(int, input().split())) for _ in range(M)]

aMIN = min(a)
bMIN = min(b)

MIN = aMIN + bMIN

for k in data:
    MIN = min(MIN, a[k[0]-1]+b[k[1]-1]-k[2])


print(MIN)
### BUGGY CODE ###

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

b = sorted(a)
b.append(0)
#print(b)

for i in range(N):
    flag = 0
    num = 1
    temp = 0
    sumnum = 0
    for j in range(N): 
        if a[i] == b[j]:
            flag=1
        if not b[j] == b[j+1]:
            if flag==1:
                num -= 1
            #print('num',num)
            sumnum += (num * (num-1)) / 2
            num=0
            flag=0
        num +=1
    print(int(sumnum))


### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int,input().split()))

b = Counter(a)
sumnum=0
for j in b.keys(): 
    sumnum += (b[j] * (b[j]-1)) / 2

for i in range(N):
    print(int(sumnum - (b[a[i]]-1)))
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
mod=998244353
dp=[[0 for y in range(D-B+1)]for x in range(C-A+1)]
dp[0][0]=1
for x in range(C-A):
    dp[x+1][0]=(dp[x][0]*B)%mod
for y in range(D-B):
    dp[0][y+1]=(dp[0][y]*A)%mod
for x in range(C-A):
    for y in range(D-B):
        dp[x+1][y+1]=(dp[x+1][y]*(A+x))%mod
        dp[x+1][y+1]+=(dp[x][y+1]*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]-=(dp[x][y]*(A+x)*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]+=(dp[x+1][y]+dp[x][y+1])%mod
        dp[x+1][y+1]%=mod

print(dp[C-A][D-B])


### FIXED CODE ###

A,B,C,D=map(int,input().split())
mod=998244353
dp=[[0 for y in range(D-B+1)]for x in range(C-A+1)]
dp[0][0]=1
for x in range(C-A):
    dp[x+1][0]=(dp[x][0]*B)%mod
for y in range(D-B):
    dp[0][y+1]=(dp[0][y]*A)%mod
for x in range(C-A):
    for y in range(D-B):
        dp[x+1][y+1]=(dp[x+1][y]*(A+x))%mod
        dp[x+1][y+1]+=(dp[x][y+1]*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]-=(dp[x][y]*(A+x)*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]+=(dp[x+1][y]+dp[x][y+1])%mod
        dp[x+1][y+1]%=mod

print(dp[C-A][D-B])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
num = list(range(N))
dic1 = dict(zip(num,S))
q = [list(map(lambda x: int(x)-1,input().split())) for _ in range(Q)]
dic2 = {}
for i in range(N-1):
    if dic1[i]+dic1[i+1] == "AC":
        dic2[i] = i
vl = list(dic2.values())
for i in range(Q):
    ans = 0
    for j in range(len(dic2)):
        if q[i][0] <= vl[j] < q[i][1]:
            ans += 1
    print(ans)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
ac = [0]*(N+1)
for i in range(N):
    ac[i+1] = ac[i] + (1 if S[i:i+2] == "AC" else 0)
for i in range(Q):
    l,r = map(int,input().split())
    print(ac[r-1]-ac[l-1])
### BUGGY CODE ###

a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))
bs = b
cs = c
 
x = 0
 
f = range(a[0])
g = range(a[1])
 
for i in range(a[0]):
    for ii in range(i,a[0]):
        for j in range(a[1]):
            for jj in range(j,a[1]):
                x = x + ((bs[ii] - bs[i]) * (cs[jj] - cs[j]))
                if x > (10**9 + 7):
                    x = x % (10**9 + 7)
 
ans = abs(x)
 
print(ans)

### FIXED CODE ###

a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))

x = 0
y = 0

for i in range(1,a[0]):
    x = x + b[i] - b[0]
    
xx = x
for i in range(1,a[0]-1):
    xx = xx - ((b[i] - b[i - 1]) * (a[0] - i))
    x = x + xx

for i in range(1,a[1]):
    y = y + c[i] - c[0]
    
yy = y
for i in range(1,a[1]-1):
    yy = yy - ((c[i] - c[i - 1]) * (a[1] - i))
    y = y + yy

ans = x * y
ans = ans % (10**9 + 7)

print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
sc=[[0]*N for _ in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    sc[a-1][b-1]=H[b-1]
    sc[b-1][a-1]=H[a-1]

cnt=0
for i in range(N):
    if max(sc[i])<H[i] or max(sc[i])==0:
        cnt+=1

print(cnt)

### FIXED CODE ###

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

flag=[True]*N
for i in range(M):
    a,b=map(int,input().split())
    ha=H[a-1]
    hb=H[b-1]
    if ha==hb:
        flag[a-1]=False
        flag[b-1]=False
    elif ha<hb:
        flag[a-1]=False
    else:
        flag[b-1]=False
cnt=0
for f in flag:    
    if f:
        cnt+=1

print(cnt)
### BUGGY CODE ###

s = str(input())
t = str(input())
s_length = len(s) 
t_length = len(t)

if s_length < t_length:
    s, t = t, s
    s_length, t_length = t_length, s_length

dp = [[0 for j in range(s_length + 1)] for i in range(t_length + 1)]

for i in range(0, t_length):
    for j in range(0, s_length):
        if s[j] == t[i]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lcs = ""
i = t_length
j = s_length

while (i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        lcs += s[j-1]
        i -= 1
        j -= 1

print(lcs[::-1])

### FIXED CODE ###

s = str(input())
t = str(input())
s_length = len(s) 
t_length = len(t)

if s_length < t_length:
    s, t = t, s
    s_length, t_length = t_length, s_length

dp = [[0 for j in range(s_length + 1)] for i in range(t_length + 1)]

for i in range(0, t_length):
    for j in range(0, s_length):
        if s[j] == t[i]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lcs = ""
i = t_length
j = s_length

while (i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        lcs += s[j-1]
        i -= 1
        j -= 1

print(lcs[::-1])
### BUGGY CODE ###

#入力: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[x]+=self.parents[y]
		self.parents[y]=x
        
n,m=input2()
AB=[input_array() for _ in range(m)]
D=[[0]*n for _ in range(n)]

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)


### FIXED CODE ###

#入力: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[x]+=self.parents[y]
		self.parents[y]=x
		# print(self.parents)
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)