Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(1000000)

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for a, b in edges:
        neighbor_list[a-1] += [b-1]
        neighbor_list[b-1] += [a-1]
        
    return neighbor_list


def paint(K, nlist, now_num, from_num, case_num):
        mod = 1000000007
        if  from_num == -1:
            can_use_color = K - 1
        else:
            can_use_color = K - 2
        
        if len(nlist[now_num]) > can_use_color and len(nlist[now_num]) != 1:
            return 0
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num *= can_use_color
                can_use_color -= 1
                case_num %= mod
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num = paint2(K, nlist, child, now_num, case_num)
        return case_num%mod
            

if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)


    print(paint(K, nlist, 0, -1, K))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for a, b in edges:
        neighbor_list[a-1] += [b-1]
        neighbor_list[b-1] += [a-1]
        
    return neighbor_list


def paint(K, nlist, now_num, from_num, case_num):
        mod = 1000000007
        if  from_num == -1:
            can_use_color = K - 1
        else:
            can_use_color = K - 2
        
        if len(nlist[now_num]) - 1 > can_use_color:
            return 0
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num *= can_use_color
                can_use_color -= 1
                case_num %= mod
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num = paint(K, nlist, child, now_num, case_num)
        return case_num%mod
            

if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)


    print(paint(K, nlist, 0, -1, K))
a,b=map(int,input(),split())
if a-2*b>=0:
  print(a-2*b)
else a-2*b<0:
  print(0)


### FIXED CODE ###

a,b=map(int,input().split())
if a-2*b>=0:
  print(a-2*b)
else:
  print(0)
def getInput():
    return [int(i) for i in input().rstrip().split(' ')]

def swap(x, K):
    return abs(x-K)

def loops (x, K):
    if x < K:
        ab = swap(x, K)
        return min(ab, x)
    elif x % K == 0:
        return 0
    else:
        x = swap(x, K)
        x = loops(x, K)
        return x

N, K = getInput()
x = N
print(loops(x, K))


### FIXED CODE ###

def getInput():
    return [int(i) for i in input().rstrip().split(' ')]

N, K = getInput()
t = N % K 
print(min(t, K -t))
n,k = map(int,input().split())
s = list(map(int,input().split()))

t = [0]*(n+1)
t[1] = 1
q = [1]

for i in range(1,k):
    if t[s[i]] == 0:
        t[s[i]] = 1
        q.append(s[i])
    elif i == k:
        print(s[i])
        exit()
    elif t[s[i]] != 0:
        ans = k%(len(q))
        print(q[ans])
        exit()



    


    


### FIXED CODE ###

n,k = map(int,input().split())
s = list(map(int,input().split()))
s.insert(0,0)

visited = [0]*(n+1)
visited[1] = 1
q = [1]

def dp(town):
    if visited[town] == 1:
        ans = k%(len(q))
        print(q[ans])
        exit()
    else:
        visited[town] += 1
        q.append(town)

i = 1
next_town = s[1]
while True:
    if i == k:
        print(next_town)
        exit()
    if visited[next_town] == 1:
        break
    else:
        visited[next_town] += 1
        q.append(next_town)
        next_town = s[next_town]
        i += 1
    
index = q.index(next_town)
q = q[index:]
ans = (k-i)%len(q)
print(q[ans])
p, q, r = map(int, input().split())
lst = []
lst.extend(p, q, r)
lst.sort()

print(lst[0] +lst[1])

### FIXED CODE ###

lst = list(map(int, input().split()))
lst.sort()
 
print(lst[0] +lst[1])
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

prime = [True] * (10**6 + 2)
prime[1] = False
max_range = int(math.sqrt(10**6)) + 1

for i in range(2, 10**6 + 1):
    if not prime[i]:
        continue
    if prime[i]:
        num = i + i
        while num < max_range:
            prime[num] = False
            num += i

def main():
    gcd = fractions.gcd
    A, B = LI()
    m = gcd(A, B)
    cnt = 1
    for i in range(2, int(math.sqrt(m)) + 1):
        if m % i != 0:
            continue
        j = m // i
        if prime[i]:
            cnt += 1
        if prime[j]:
            cnt += 1
    print(cnt)
main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def integer_factorization(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n //= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    return prime_count

prime = [True] * (10**6 + 2)
prime[1] = False
max_range = int(math.sqrt(10**6)) + 1

for i in range(2, 10**6 + 1):
    if not prime[i]:
        continue
    if prime[i]:
        num = i + i
        while num < max_range:
            prime[num] = False
            num += i

def main():
    gcd = fractions.gcd
    A, B = LI()
    m = gcd(A, B)
    cnt = 1
    cnt += len(integer_factorization(m))
    # for i in range(2, int(math.sqrt(m)) + 1):
    #     if m % i != 0:
    #         continue
    #     if prime[i]:
    #         cnt += 1
    print(cnt)
main()
a, b = map(int, input().split())
numbers = list(range(a, b + 1))
if a < 0:
    if 0 < b:
        print("Zero")
        exit()
    if len(numbers) % 2 != 0:
        print("Negative")
    else:
        print("Positive")
else:
    print("Positive")


### FIXED CODE ###

a, b = map(int, input().split())
if 0 < a <= b:
    print("Positive")

elif a <= b < 0:
    if (b - a + 1) % 2 == 0:
        print("Positive")

    else:
        print("Negative")
elif a <= 0 <= b:
    print("Zero")
n=int(input())
h=list(map(int,input().split()))
ans=0

def f(li):
  global ans
  
  #終了条件
  if li==[]:
    del li
    return
  
  #再帰
  min_num=min(li)
  if min(li)>0:
    count+=min(li)
    li=list(map(lambda x: x-min(li), li))
  li=[li[:li.index(0)],li[li.index(0)+1:]]
  f(li[0])
  f(li[1])

f(h)
print(count)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
ans=0

def f(li):
  global ans
  
  #終了条件
  if li==[]:
    del li
    return
  
  #再帰
  min_num=min(li)
  if min(li)>0:
    ans+=min(li)
    li=list(map(lambda x: x-min(li), li))
  li=[li[:li.index(0)],li[li.index(0)+1:]]
  f(li[0])
  f(li[1])

f(h)
print(ans)
b = input()
 
if b == A:
  print("T")
elif b == T:
  print("A")
elif b == C:
  print("G")
elif b == G:
  print("C")

### FIXED CODE ###

b = input()
 
if b == "A":
  print("T")
if b == "T":
  print("A")
if b == "C":
  print("G")
if b == "G":
  print("C")
from collections import deque
n, m, k = map(int,input().split())
tmpA = list(map(int,input().split()))
tmpB = list(map(int,input().split()))
A = [tmpA[0]]
B = [tmpB[0]]
for i in range(1, n):
    tmp = A[i-1] + tmpA[i]
    if tmp > k:
        break
    else:
        A.append(tmp)
for i in range(1, m):
    tmp = B[i-1] + tmpB[i]
    if tmp > k:
        break
    else:
        B.append(tmp)

if len(A) == 1 and len(B) == 1:
    if A[0] > k:
        A.pop()
    if B[0] > k:
        B.pop()
    print(len(A) + len(B))
elif len(A) == 1:
    if A[0] > k:
        print(len(B))
    else:
        while True:
            if A[0] + B[-1] <= k:
                break
            if A[0] > B[-1]:
                A.pop()
            else:
                B.pop()
        print(len(A) + len(B))
elif len(B) == 1:
    if B[0] > k:
        print(len(A))
    else:
        while True:
            if B[0] + A[-1] <= k:
                break
            if B[0] > A[-1]:
                B.pop()
            else:
                A.pop()
        print(len(A) + len(B))
else:
    while True:
        if A[-1] + B[-1] <= k:
            break
        if A[-1] > B[-1]:
            A.pop()
        else:
            B.pop()
    print(len(A) + len(B))



### FIXED CODE ###

def is_ok(index, key):
    return B[index] <= key

def upper_bound(key): 
    ng = len(B)
    ok = -1

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, key):
            ok = mid
        else:
            ng = mid
    
    return ok 

n, m, k = map(int, input().split())
tmpA = list(map(int, input().split()))
tmpB = list(map(int, input().split()))
A = [0]
B = [0]
# 読むのにかかる時間の累計和のリスト
if A:
    for i in range(n):
        tmp = A[i] + tmpA[i]
        if tmp > k:
            break
        else:
            A.append(tmp)
if B:
    for i in range(m):
        tmp = B[i] + tmpB[i]
        if tmp > k:
            break
        else:
            B.append(tmp)

answer = 0
for i in range(len(A)):
    key = k - A[i]
    answer = max(answer, upper_bound(key) + i)

print(answer)
q,b=map(int,input().split())

if a>=1 and a<=9 and b>=1 and b<=9:
  print(a*b)
else:
  print(-1)

### FIXED CODE ###

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

if a>=1 and a<=9 and b>=1 and b<=9:
  print(a*b)
else:
  print(-1)
from functools import reduce
import math
from collections import defaultdict

MIN = -10 ** 9
MAX = 10 ** 9 + 7

from math import factorial


def main():
    N, K = [int(a) for a in input().split()]

    ab = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    edges = defaultdict(lambda: [])
    for ai, bi in ab:
        r = edges[ai]
        r.append(bi)
        edges[ai] = r
        r = edges[bi]
        r.append(ai)
        edges[bi] = r

    def parsetree(parent_i, current_i):
        children = []
        for nei in edges[current_i]:
            if nei == parent_i:
                continue
            child = parsetree(current_i, nei)
            children.append(child)
        return children

    tree = parsetree(None, 1)

    if len(tree) > K - 1:
        print(0)
        return

    def c(a, b):
        k = 1
        for i in range(b):
            k = (k * (a - i)) % MAX
        return k

    def f(tr):
        childcount = len(tr)

        a = c(K - 2, childcount)
        for child in tr:
            r = f(child) % MAX
            a = (a * r) % MAX
        return a

    try:
        result = K * c((K - 1), len(tree))
        for child in tree:
            r = f(child) % MAX
            result = (result * r) % MAX
    except:
        print(0)
        return
    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys
sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    N, K = [int(a) for a in input().split()]
    if N == 1:
        print(K)
        return
    if K == 1:
        print(0)
        return

    ab = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    edges = defaultdict(lambda: [])
    for ai, bi in ab:
        r = edges[ai]
        r.append(bi)
        edges[ai] = r
        r = edges[bi]
        r.append(ai)
        edges[bi] = r

    childrentable = [None] * (N + 1)

    q = deque()
    q.append((None, 1))

    while len(q) != 0:
        parent_i, current_i = q.pop()

        children = []
        for nei in edges[current_i]:
            if nei == parent_i:
                continue
            q.append((current_i, nei))
            children.append(nei)
        childrentable[current_i] = children

    if len(childrentable[1]) > K - 1:
        print(0)
        return

    def c(a, b):
        k = 1
        for i in range(b):
            if a - i <= 0:
                raise ValueError()
            k = (k * (a - i)) % MAX
        return k

    def f(index):
        target = childrentable[index]
        childcount = len(target)

        a = c(K - 2, childcount)
        for child in target:
            r = f(child) % MAX
            a = (a * r) % MAX
        return a

    try:
        result = K * c((K - 1), len(childrentable[1]))
        for child in childrentable[1]:
            r = f(child) % MAX
            result = (result * r) % MAX
    except:
        print(0)
        return
    print(result)


if __name__ == '__main__':
    main()
s = input()
l = len(s)
half_len = int(l/2)

if l%2 != 0:
	s = s.replace(s[half_len], "")
	fst_half = s[:half_len]
	snd_half = s[half_len:]
else:
	fst_half = s[:half_len]
	snd_half = s[half_len:]

snd_half = snd_half[::-1]

count = 0
for i in range(half_len):
	if(snd_half[i] != fst_half[i]):
		count += 1

print(count)

### FIXED CODE ###

s = input()
count = 0
for i in range(len(s)//2):
    if(s[i] != s[len(s)-i-1]):
        count += 1
print(count)
N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

import fractions
a,b = T[0], T[1]
f=fractions.gcd(a,b)
f2=a*b//f

for i in range(2,N):
    a,b=f2, T[i]
    f=fractions.gcd(a,b)
    f2=a*b//f

print(f2)


### FIXED CODE ###


N = int(input())
T = []
for i in range(N):
    T.append(int(input()))
# print('T:',T)

if N==1:
    f2 = T[0]

elif N==2:
    import math
    a,b = T[0], T[1]
    f=math.gcd(a,b)
    f2=a*b//f

else:
    import math
    a,b = T[0], T[1]
    f=math.gcd(a,b)
    f2=a*b//f
    for i in range(2,N):
        a,b=f2, T[i]
        f=math.gcd(a,b)
        f2=a*b//f

print(f2)
#ABC090
s = input()
t = input()
ans = 0
if s[0]=t[0]:
    ans+=1
if s[1]=t[1]:
    ans+=1
if s[2]=t[2]:
    ans+=1
print(ans)    

### FIXED CODE ###

#ABC090
s = input()
t = input()
ans = 0
if s[0]==t[0]:
    ans+=1
if s[1]==t[1]:
    ans+=1
if s[2]==t[2]:
    ans+=1
print(ans)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+1)
ans=0
if n-1 not in a:
    dp[1]=1
if n-2 not in a:
    dp[2]=dp[1]+1
for i in range(3,n+1):
    if n-i not in a:
        dp[i]=dp[i-1]+dp[i-2]
    else:
        continue
print(dp[n]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[0]*(n+1)
for i in range(m):
    dp[n-a[i]]=-1
if dp[1]==0:
    dp[1]=1
else:
    dp[1]=0
if n>1:
    if dp[2]==0:
        dp[2]=dp[1]+1
    else:
        dp[2]=0
if n>=3:
    for i in range(3,n+1):
        if dp[i]==0:
            dp[i]=dp[i-1]+dp[i-2]
        else:
            dp[i]=0
print(dp[n]%1000000007)
a,b = map(int,input().split())
if a > 2b:
  print(a-2b)
else:
  print(0)

### FIXED CODE ###

a,b = map(int,input().split())
if a > 2*b:
  print(a-2*b)
else:
  print(0)
from collections import deque

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

a = deque(list(map(int,input().split())))
b = deque(list(map(int,input().split())))
cnt = 0
total = 0

while total+a[0] < k or total+b[0] < k:
    if len(a) > 0 and len(b) > 0:
        picked = min(a[0],b[0])
        if picked == a[0]:
            total += a.popleft()
            cnt += 1
        else:
            total += b.popleft()
            cnt += 1
    elif len(a) > 0 and len(b)==0:
        total +=a.popleft()
        cnt += 1
    elif len(b) > 0 and len(a)==0:
        total += b.popleft()
        cnt += 1
print(cnt)

### FIXED CODE ###

#　変数 n, m, k, arr1, arr2, acum1, acum2, ans

n, m, k = map(int, input().split())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))

acum1 = [0]
for i in range(n):
    acum1.append(acum1[-1] + arr1[i])
acum2 = [0]
for i in range(m):
    acum2.append(acum2[-1] + arr2[i])

ans = 0
j = m
for i in range(n+1):
    if acum1[i] > k:
        break
    while acum2[j] > k - acum1[i] and j > 0:
        j -= 1
    ans = max(ans, i+j)
print(ans)
n = int(input())
L = list(map(int,input().split()))

dp = [0]*(2*(10**5)+1000)
one = list(set(L))
for i in L:
    for j in range(2*i,max(L)+1,i):
        if not dp[j-1]:
            dp[j-1] = 1

ans = 0
for i in one:
    if dp[i-1] == 0:
        ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
dp = [0]*((10**6)+1000)
for i in L:
    dp[i] +=1

one = []
for i in range(10**6+1000):
    if dp[i] == 1:
        one.append(i)

dp = [0]*((10**6)+1000)
a = list(set(L))
for i in a:
    for j in range(2*i,10**6+1000,i):
        dp[j] = 1

ans = 0
for i in one:
    if dp[i] == 0:
        ans +=1
print(ans)
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
a = [0]*k
has_k = [False]*n
count = 0

for i in range(k):
    tmp_d = int(input())
    tmp_a = list(map(int, input().split()))
    for ai in tmp_a:
        has_k[ai-1] = True

for ki in has_k:
    if ki == False:
        count += 1

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
h = list(map(int, input().split()))
h_cond = [True]*n
count = 0

for i in range(m):
    tmp_a, tmp_b = map(int, input().split())
    if h[tmp_a-1] < h[tmp_b-1]:
        h_cond[tmp_a-1] = False
    elif h[tmp_a-1] > h[tmp_b-1]:
        h_cond[tmp_b-1] = False
    else:
        h_cond[tmp_a - 1] = False
        h_cond[tmp_b - 1] = False

# print(h_cond)
# print(route)
for idx, hi in enumerate(h_cond):
    if h_cond[idx]:
        count += 1

print(count)
# coding: utf-8
def modcomb(n, r, mod):
    "nCr = X/Yとおく"
    r = min(r, n - r)
    X, Y = 1, 1
    # a, b, c = 1, 1, 1
    for i in range(1, n + 1):
        X = X * (n + 1 - i) % mod
        Y = Y * i % mod
        a = a * i % mod
    for i in range(1, r + 1):
        b = b * i % mod
        c = c * (n - i + 1) % mod
    return a * pow((b * c) % mod, mod-2, mod) % mod
    # return X * pow(Y, mod-2, mod) % mod

N, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = pow(2, N, mod) - 1
a = modcomb(N, A, mod)
# ans %= mod
b = modcomb(N, B, mod)
ans -= a + b
print(ans % mod)

### FIXED CODE ###

# coding: utf-8
def modcomb(n, r, mod):
    "nCr = X/Yとおく"
    r = min(r, n - r)
    X, Y = 1, 1
    for i in range(1, r + 1):
        X = X * (n + 1 - i) % mod
        Y = Y * i % mod
    # return ue * modpow(sita, mod-2, mod)
    return X * pow(Y, mod-2, mod) % mod

N, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = pow(2, N, mod) - 1
a = modcomb(N, A, mod)
# ans %= mod
b = modcomb(N, B, mod)
ans -= a + b
print(ans % mod)
if int(input()) == 1:
    msg = "Hello World!"
else:
    a = [int(input()) for i in range(2)]
    msg = a[0]+a[1]
print(msg)

### FIXED CODE ###

list = list(map(int, input().split()))
print(max([list[0]*2-1,list[0]+list[1],list[1]*2-1]))
a = list(map(int,input()))
if a[0] == 1 and a[1] == 1:
  print("Draw")
elif a[0] == 1:
  print("Alice")
elif a[1] == 1:
  print("Bob")
else:
  if a[0] > a[1]:
    print("Alice")
  elif a[0] == a[1]:
    print("Draw")
  else:
    print("Bob")

  
  
         

### FIXED CODE ###

a = list(map(int,input().split(" ")))
if a[0] == 1 and a[1] == 1:
  print("Draw")
elif a[0] == 1:
  print("Alice")
elif a[1] == 1:
  print("Bob")
else:
  if a[0] > a[1]:
    print("Alice")
  elif a[0] == a[1]:
    print("Draw")
  else:
    print("Bob")
N, P = map(int, input().split())
A = map(int, input().split())

n_even = len(filter(lambda x: x % 2 == 0, A))
n_odd = N - n_even
ans = 2 ** max(0, n_odd - 1) * 2 ** n_even
if P == 0 and n_odd == 0:
    print(0)
else:
    print(ans)


### FIXED CODE ###

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

n_even = len(list(filter(lambda x: x % 2 == 0, A)))
n_odd = N - n_even
ans = (2 ** max(0, n_odd - 1)) * (2 ** n_even)
if P == 1 and n_odd == 0:
    print(0)
else:
    print(ans)
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 i in range(m):
  a,b=map(int,input().split())
  uf.union(a,b)
print(uf.group_count()-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 i in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  uf.union(a,b)
print(uf.group_count()-1)