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

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
m=n+1
a=list(map(int,input().split()))

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    ans=0
    ans+=cmb(m-2,k)
    ans+=cmb(m-2,k-2)
    if m-ma-2>=k-1:
        ans+=cmb(m-ma-2,k-1)
    for i in range(1,ma+1):
        if k-1-i>=0 and m-ma-2>=k-1-i:
            ans+=2*cmb(ma,i)*cmb(m-ma-2,k-1-i)
    print(ans%mod)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
m=n+1
a=list(map(int,input().split()))

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)
    if m-2-ma>=k-1:
        tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)
### BUGGY CODE ###

N = int(input())

A = [0] + [n for n in map(int, input().split())]

for i in range(N):
    A[i+1] += A[i]

element_A = set(A)

ans = 0

for a in element_A:
    num_a = A.count(a)
    if num_a > 1:
        ans += num_a * (num_a - 1) / 2
print(int(ans))


### FIXED CODE ###

N = int(input())

A = [0] + [n for n in map(int, input().split())]

for i in range(N):
    A[i+1] += A[i]

A.sort()
ans = 0

cnt_list = []
temp = A[0]
cnt = 0

for i in range(N+1):
    if temp == A[i]:
        cnt += 1
    else:
        cnt_list.append(cnt)
        cnt = 1
        temp = A[i]
else:
    cnt_list.append(cnt)
for x in cnt_list:
    if x > 1:
        ans += x*(x-1) / 2

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

# -*- Coding: utf-8 -*-

originalS = raw_input()

i = 0
while originalS.find('ABC')!=-1:
  originalS = originalS.replace('ABC', 'BCA', 1)
  i += 1

print i

### FIXED CODE ###

# -*- Coding: utf-8 -*-
#import numpy as np

def count(s):
	i = 0
	a_cnt = 0
	cnt = 0
	while i < len(s):
		if s[i] == 'A':
			a_cnt += 1
		if s[i] =='D':
			cnt += a_cnt

		i += 1

	return cnt



originalS = raw_input()
originalS = originalS.replace('BC', 'D')
originalS = 'B'+originalS+'B'	


idx = []
i = 0

while i < len(originalS):
	if (originalS[i] == 'B')|(originalS[i] == 'C'):
		idx.append(i)
	i += 1


Substr = []

i = 0
while i < len(idx)-1:
	if idx[i+1]-idx[i]!=1:
		Substr.append(originalS[idx[i]+1:idx[i+1]])

	i += 1

ans = 0
for c in Substr:
	ans += count(c)

print ans
### BUGGY CODE ###

n = map(int, input().split())
a = map(int, input().split())
ans = 1
for i in a:
    ans *= i

print(ans if ans <= 10**18 else -1)


### FIXED CODE ###

n = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
flag = True if 0 in a else False

if flag:
    print(0)
    exit()

for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

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

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
s = input()

cnt=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if j-i == k-j:
        continue
      if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
        cnt+=1

print(cnt)


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
s = input()

rs=0
gs=0
bs=0

for i in range(n):
  if s[i]=='R':
    rs+=1
  elif s[i]=='G':
    gs+=1
  else:
    bs+=1

total = rs*gs*bs

for i in range(n):
  for j in range(i+1,n):
    k=j+j-i
    if k<n:
      if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
        total-=1

print(total)
### BUGGY CODE ###

import fractions

def lcm(x, y):
    return x * y // fractions.gcd(x, y)

def main():
    MOD = 1000000007
    N = int(input())
    A = list(map(int, input().split()))
    lc = 1
    for i in A:
        lc = lcm(lc, i)
        ans = 0
    for i in A:
        ans += lc // i
    print(ans%MOD)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import fractions

def lcm(x, y):
    return x * y // fractions.gcd(x, y)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    prev_lc = 1
    ans = 0
    for i in A:
        lc = lcm(prev_lc, i)
        ans = ans * (lc // prev_lc) + lc // i
        prev_lc = lc
    print(ans % 1000000007)

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

N,K=map(int,input().split())
*H,=map(int,input().split())

D=[float("inf")]*N
D[0]=0
D[1]=abs(H[1]-H[0])
for i in range(2,N):
  # print(i, "before:",D)
    D[i]=min(D[i], *[abs(H[i]-H[i-k])+D[i-k] for k in range(1,K+1)])
  # print(i, "after:",D)

print(D[-1])

### FIXED CODE ###

N,K=map(int,input().split())
*H,=map(int,input().split())

D=[float("inf")]*N
D[0]=0
D[1]=abs(H[1]-H[0])
for i in range(2,N):
  # print(i, "before:",D)
  #  print(i,i-1,i-K, max(1, i-K))
  D[i]=min(abs(H[i]-H[k])+D[k] for k in range(max(0,i-K),i))
  # print(i, "after:",D)

print(D[-1])
### BUGGY CODE ###

n = int(input())
s = input()

dict_x = {"R":1, "G":2, "B":3}
s = [dict_x[s] for s in s]

result = 0

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if (j - i) != (k - j):
                if s[i] * s[j] * s[k] == 6:
                    result += 1

print(result)


### FIXED CODE ###

n = int(input())
s = input()
 
r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')
 
ans = r_cnt * g_cnt * b_cnt
 
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

def main():
  import fractions
  import math

  a,b = map(int,input().split())
  g = fractions.gcd(a,b)
  
  d = [1]
  num = 2

  while num <= g:
    #print("num",num)
    if g%num == 0:
      d.append(num)
    while g%num == 0 and g>1:
      g = g//num
      #print(g)
    num += 1
  
  print(len(d))

if __name__ == "__main__":
  main()



### FIXED CODE ###

def main():
  import fractions
  import math

  a,b = map(int,input().split())
  g = fractions.gcd(a,b)
  
  d = [1]
  num = 2

  while num**2 <= g:
    #print("num",num)
    if g%num == 0:
      d.append(num)
    while g%num == 0 and g>1:
      g = g//num
      #print(g)
    num += 1
  
  print(len(d) + (g > 1))

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

N = int(input())
A = list(map(int, input().split()))
M = 10**9 + 7
s = 0
for i in range(N):
    for j in range(N):
        if i < j:
            s += A[i] * A[j]
            s = s % M

print (s)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = 10**9 + 7
s = 0

sm = sum(A)

for i in range(N):
    sm -= A[i]
    s += sm * A[i]
    s = s % M

print (s)
### BUGGY CODE ###

N=int(input())
count=0
s=[input() for i in range(N)]
n=['a' for t in range(N) for i in range(t+1,N) if sorted(s[t])==sorted(s[i])]
print(len(n))

### FIXED CODE ###

N=int(input())
S=[''.join(sorted((input()))) for i in range(N)]
P={}
for i in range(N):
    if S[i] in P:
        P[S[i]]+=1
    else:
        P[S[i]]=0
for i in P.keys():
    if P[i]>=2:
        P[i]=P[i]*(P[i]+1)/2
print(int(sum(P.values())))
### BUGGY CODE ###

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

for i in range(n-1):
    i = i + 1
    cnt = 0
    for j in range(n-1):
        if i == A[j]:
            cnt += 1
    print(cnt)
print("0")

### FIXED CODE ###

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

ans = [0] * N
for a in A:
    ans[a-1] += 1

for a in ans:
    print(a)
### BUGGY CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append([x-1,y])
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append([x,y-1])
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append([x+1,y])
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append([x,y+1])
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

#
# abc072 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """7
3 1 4 1 5 9 2"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10
0 1 2 3 4 5 6 7 8 9"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1
99999"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    an = {}
    for a in A:
        an.setdefault(a, 0)
        an[a] += 1

    ans = 1
    for x in range(min(A)-1, max(A)+1):
        t = 0
        for k, v in an.items():
            if x == k-1 or x == k or x == k+1:
                t += v
        ans = max(ans, t)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc072 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """7
3 1 4 1 5 9 2"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10
0 1 2 3 4 5 6 7 8 9"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1
99999"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    AN = [0] * 100002  # -1 <= X <= 10^5+1

    for a in A:
        AN[a] += 1
        AN[a+1] += 1
        AN[a+2] += 1
    print(max(AN))


if __name__ == "__main__":
    # unittest.main()
    resolve()
### BUGGY CODE ###

def GCD(a, b):
    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

ans = 0
N = int(input())
A = tuple(map(int,input().split()))
for S in range(len(A)):
    Af = 0
    for i in range(len(A)):
        if S != i:
            Af = GCD(Af,A[i])
    ans = max(ans,Af)

print(ans)


### FIXED CODE ###

def GCD(a, b):
    if a == 0 and b == 0:
        return 0
    elif a == 0:
        return b
    elif b == 0:
        return a

    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

ans = 0
N = int(input())
A = tuple(map(int,input().split()))

X = [0]*N
Y = [0]*N

for i in range(1,N):
    X[i] = GCD(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i] = GCD(Y[i+1],A[i+1])

for i in range(N):
    ans = max(ans,GCD(X[i],Y[i]))

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

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    flg = [[True] * n for _ in range(n)]

    for k in range(n):
        for i in range(n):
            if i == k:
                continue
            for j in range(n):
                if i == j or j == k:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    flg[i][j] = False

    res = 0
    for i in range(n):
        for j in range(n):
            if flg[i][j]:
                res += A[i][j]

    print(res // 2)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]
    flg = [[True] * n for _ in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if grid[i][k] + grid[k][j] < grid[i][j]:
                    print(-1)
                    exit()
                elif grid[i][k] + grid[k][j] == grid[i][j] and i != k and j != k:
                    flg[i][j] = False

    res = 0
    for i in range(n):
        for j in range(n):
            if flg[i][j]:
                res += grid[i][j]
    print(res // 2)


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

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

a_list = sorted(a_list, reverse=True)
a_set = set(a_list)
a_dict = {}
sorted_dict = {}

ans_big = 0
ans_small = 0

for i in a_set:
    a_dict[i] = a_list.count(i)

for k, v in sorted(a_dict.items(), key=lambda x: -x[0]):
    if v >= 4:
        if ans_big < k:
            ans_big = k
        if ans_small < k:
            ans_small = k
    elif v >= 2:
        if ans_big < k:
            ans_big = k
        elif ans_small < k:
            ans_small = k
print(ans_small * ans_big)


### FIXED CODE ###

from collections import Counter

a = input()
a_list = list(map(int, input().split()))
 
# 要素数の数え上げと取り出し
num_counter = Counter(a_list)
num_keys = sorted(num_counter.keys(), reverse=True)

big = 0
small = 0

for i in num_keys:
  x = num_counter[i]
  if x >= 4:
    if big == 0:
      big = small = i
    elif big != 0 and small == 0:
      small = i
  elif x == 3 or x == 2:
    if big == 0:
      big = i
    elif big != 0 and small == 0:
      small = i
  if big != 0 and small != 0:
    break
print(big * small)
### BUGGY CODE ###

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

def distinct(arry):
  while True:
    if len(arry) == 1:
      return True
    x = arry.pop(0)
    if x in arry:
      return False

if distinct(A):
  print("YES")
else:
  print("NO")


### FIXED CODE ###

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

def distinct(arry):
  x = set(arry)
  if len(A) != len(x):
    return False
  return True

if distinct(A):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

n = int(input())
s = input()
S = list(s)
a = 0
for k in range(n):
        for j in range(k):
            if S[j] != S[k]:
                for i in range(j):
                    if   S[i] != S[j] and S[k] != S[i] and 2*j != i + k:
                        # print(i, j, k)
                        a += 1
print(a)

### FIXED CODE ###

n = int(input())
s = input()
S = list(s)
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r * g * b
for k in range(n):
        for j in range(k):
            i = 2*j - k
            if i >= 0 and i < j and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
L1 = list(map(int,input().split()))
m = int(input())
L2 = list(map(int,input().split()))
for i in range(m):
    if L2[i] in L1:
        L1.remove(L2[i])
    elif L2[i] not in L1:
        print("NO")
        exit()
if len(L1) >= 0:
    print("YES")

### FIXED CODE ###

from collections import Counter
n = int(input())
L1 = list(map(int,input().split()))
m = int(input())
L2 = list(map(int,input().split()))
li1 = Counter(L1)
li2 = Counter(L2)

flag = False
for i in range(m):
    if li1[L2[i]] >= li2[L2[i]]:
        flag = True
    else:
        flag = False
        break
if flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

s=input()
k=int(input())
n=len(s)
ans=[]
for i in range(n):
    for j in range(1,i+k+1):
        ans.append(s[i:j])
ans=list(set(ans))
ans.sort()
if "" in ans:
    ans.pop(0)
print(ans[k-1])

### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
ans=[]
for i in range(n):
    for j in range(i+1,i+k+1):
        ans.append(s[i:j])
ans=list(set(ans))
ans.sort()
if "" in ans:
    ans.pop(0)
print(ans[k-1])
### BUGGY CODE ###

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

list_ = []
for i in range(N):
  list_.append(A.count(i))

list_.append(0)
for j in list_[1:]:
  print(j)

### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N

A.append(0)

for i in range(0, N-1):
  ans[A[i]] += 1
for i in range(1, N):
  print(ans[i])
print(0)
### BUGGY CODE ###

from collections import Counter
from itertools import combinations


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

if len(a_occ) == 1:
    print(int(n / 2))
    exit()

a_mcommon = a_occ.most_common()

elem = list()
elem.append(a_mcommon[0][0])
elem.append(a_mcommon[1][0])

for i in range(2, len(a_mcommon)):
    if a_mcommon[i][1] >= a_mcommon[1][1]:
        elem.append(a_mcommon[i][0])
    else:
        break


def algo_run(elem_tuple: tuple, list_to_alt: list) -> int:
    item_select = True
    result_true = 0
    result_false = 0
    for i in list_to_alt:
        if item_select:
            if i != elem_tuple[0]:
                result_true += 1
        else:
            if i != elem_tuple[1]:
                result_true += 1

        if not(item_select):
            if i != elem_tuple[0]:
                result_false += 1
        else:
            if i != elem_tuple[1]:
                result_false += 1

        item_select = not (item_select)

    return result_true if result_true < result_false else result_false


minimum = 9999999
for perm in combinations(elem, 2):
    algo_run_cache = algo_run(perm, a)
    if algo_run_cache < minimum:
        minimum = algo_run_cache


print(minimum)


### FIXED CODE ###

n = int(input())
x = list(int(i) for i in input().split())
a = []
b = []
for i in range(0, n):
    if i % 2 == 0:
        a.append(x[i])
    else:
        b.append(x[i])
cnta = [0] * (100002 + 1)
cntb = [0] * (100002 + 1)
vala = 0
vala1 = 0
maxCnta = 0
maxCnta1 = 0
for i in a:
    cnta[i] += 1

for i in a:
    if maxCnta < cnta[i]:
        vala = i
        maxCnta = cnta[i]
for i in a:
    if maxCnta1 < cnta[i] and vala != i:
        maxCnta1 = cnta[i]
        vala1 = i
#---------------------------
valb = 0
valb1 = 0
maxCntb = 0
maxCntb1 = 0
for i in b:
    cntb[i] += 1

for i in b:
    if maxCntb < cntb[i]:
        valb = i
        maxCntb = cntb[i]

for i in b:
    if maxCntb1 < cntb[i] and valb != i:
        maxCntb1 = cntb[i]
        valb1 = i

if valb != vala:
    res = 0
    for i in a:
        if i != vala:
            res += 1
    for i in b:
        if i != valb:
            res += 1
    print(res)
else:
    resa = 0
    resb = 0
    resa1 = 0
    resb1 = 0
    for i in a:
        if i != vala:
            resa += 1
        if i != vala1:
            resa1 += 1
    for i in b:
        if i != valb:
            resb += 1
        if i != valb1:
            resb1 += 1
    print(min(resa + resb1, resa1 + resb))

#print(a, b, vala, valb)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = 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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int,input().split())
uf = UnionFind(n)

for _ in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    uf.union(a , b)
    
print(len(uf.all_group_members())-1)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = 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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int,input().split())
uf = UnionFind(n)

for _ in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    uf.union(a , b)
    
print(uf.group_count()-1)