Harryxun/stf_run huggingface dataset:
# input
n = int(input())
edges = set(tuple(int(i) for i in input().split()) for _ in range(n-1))


from collections import deque


def diameter(tree):
    _, s = farest(tree, 4)
    diam, _ = farest(tree, s)
    return diam


def farest(tree, i):
    dp = [None] * n
    dp[i-1] = 0
    cand_q = deque()
    cand_q.append(i)

    while len(cand_q) > 0:
        u = cand_q.popleft()
        for edge in tree:
            if u in edge:
                v = edge[0] if u == edge[1] else edge[1]
                if dp[v-1] is None:
                    cand_q.append(v)
                    dp[v-1] = dp[u-1] + 1
    max_ = max(dp)
    i_max = dp.index(max_)
    return max_, i_max + 1


d = diameter(edges)


print('Second' if d % 3 == 1 else 'First')


### FIXED CODE ###

# input
n = int(input())
edges = set(tuple(int(i) for i in input().split()) for _ in range(n-1))


from collections import deque


def make_connection(tree):
    con = [[] for _ in range(n+1)]
    for edge in tree:
        con[edge[0]].append(edge[1])
        con[edge[1]].append(edge[0])
    return con


def diameter(tree):
    c = make_connection(tree)
    _, s = farest(tree, c, 1)
    diam, _ = farest(tree, c, s)
    return diam


def farest(tree, con, i):
    dp = [None for _ in range(n+1)]
    dp[i] = 0
    cand_q = deque()
    cand_q.append(i)

    while len(cand_q) > 0:
        u = cand_q.popleft()

        for v in con[u]:
            if dp[v] is None:
                cand_q.append(v)
                dp[v] = dp[u] + 1
    max_ = max(dp[1:])
    i_max = dp.index(max_)
    return max_, i_max


d = diameter(edges)


print('Second' if d % 3 == 1 else 'First')
N = int(input())
lst = list(map(int, input().split()))
boolean = False
updated_lst = []
minimum = min(lst)
min_num = 0
for i in lst:
  num = i % minimum
  if (i != minimum):
    updated_lst.append(num)
  else:
    updated_lst.append(minimum)
    min_num += 1
  if (num % 2 == 1):
    boolean = True

if (min_num == len(lst)):
  print(minimum)
else:
  if (boolean):
    print(1)
  else:
    print(2)


### FIXED CODE ###

N = int(input())

lst = list(map(int, input().split()))

ans = 0
for i in range(len(lst)-1):
  if (lst[i+1] > lst[i]):
    ans += lst[i+1] - lst[i]
print(ans + lst[0])
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
MAX = 2*100000 + 9
dp = [True] * MAX
for num in a:
    for i in range(num*2, MAX, num):
        dp[i] = False
ans = 0
for num in a:
    if dp[num] and a[num] == 1:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
MAX = 1000000 + 9
dp = [True] * MAX
for num in a:
    for i in range(num*2, MAX, num):
        dp[i] = False
ans = 0
for num in a:
    if dp[num] and a[num] == 1:
        ans += 1
print(ans)
x = int(input())

ans = 0

def prime(x):
    y = x//2+1
    cnt = 0
    for i in range(2,y+1):
        if x%i==0:
            cnt += 1
            
    if cnt == 0:
        return x
    else:
        return 0
        
while ans == 0:
    ans = prime(x)
    x += 1
    
if x == 2:
    print(2)
else:
    print(ans)

### FIXED CODE ###

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

pro = [0]*n

ac = set([])

ans = 0

pen = 0

for _ in range(m):
    l = input().split()
    s = l[1]
    p = int(l[0])    
    if s == "AC":
        if p not in ac:
            ans += 1
            pen += pro[p-1]
            ac.add(p)
            
    else:
        if p not in ac:
            pro[p-1] += 1
            
print(ans,pen)
import random 
S = input()
T = input()
a = [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]
if T == S + random.coice(a) 
  print("YES")
  else:
    print("NO")
    
    

### FIXED CODE ###


    
s = input()
t = input()

if t[:-1] == s:
    print("Yes")
else:
    print("No")
import math

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

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

### FIXED CODE ###

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

def lcm(a, b):
    return a * b // gcd(a, b)

a, b = map(int, input().split())
ans = lcm(a, b)
print(ans)
sys.setrecursionlimit(100000)
V, E = int(input()), int(input())
L = []
visited = [0 for i in range(V)]
edges = [[] for i in range(V)]
#flag = 0

def visit(x):
#  if visited[x] == 1:
#    flag = 1
  if not visited[x]:
    visited[x] = 1
    for e in edges[x]:
      visit(e)
    L.insert(0,x)

for i in range(E):
  s, t = map(int,input().split())
  edges[s - 1].append(t - 1)

for i in range(V):
  if not visited[i]:
    visit(i)

flag = 0
for i in range(V):
  print(L[i] + 1)
  if not flag and i < V - 1 and (L[i + 1] not in edges[L[i]]):
    flag = 1
print(flag)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def main():
  V, E = int(input()), int(input())
  L = []
  app = L.append
  visited = [0 for i in range(V)]
  edges = [[] for i in range(V)]
  
  def visit(x):
    if not visited[x]:
      visited[x] = 1
      for e in edges[x]:
        visit(e)
      app(x)
  
  for i in range(E):
    s, t = map(int,input().split())
    edges[s - 1].append(t - 1)
  
  for i in range(V):
    if not visited[i]:
      visit(i)
  L.reverse()
  
  flag = 0
  temp = L[0]
  print(temp + 1)
  for i in range(V - 1):
    v = L[i + 1]
    print(v + 1)
    if not flag and i < V - 1 and (v not in edges[temp]):
      flag = 1
    temp = v
  print(flag)
main()
n,k=map(int,input().split())
inf = 10**9+7
def conv(l,r):
    up = 1
    lo = 1
    for i in range(r):
        up *= l-i
        lo *= r-i
    return int(up/lo)

for i in range(1,k+1):
    print((conv(n-k+1,i)*conv(k-1,i-1))%inf)

### FIXED CODE ###

n,k=map(int,input().split())
inf = 10**9+7

inv_t = [0]+[1]
for i in range(2,n+1):
    inv_t += [inv_t[inf % i] * (inf - int(inf / i)) % inf]
    
bik =  [1]+[1]
for i in range(2,n+1):
    bik += [(bik[i-1]*i)% inf]
    
bik_inv =  [1]+[1]
for i in range(2,n+1):
    bik_inv += [(bik_inv[i-1]*inv_t[i])% inf]

def conv(l,r):
    if l>=r:
        up = bik[l]
        lo = bik_inv[l-r]*bik_inv[r]
        return up*lo
    else:
        return 0

for i in range(1,k+1):
    """print("#########")
    print(i)
    print(conv(n-k+1,i))
    print(conv(k-1,i-1))"""
    print((conv(n-k+1,i)*conv(k-1,i-1))%inf)
a,b,k=map(int, input().split())

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

print(cf(a,b)[-k])


### FIXED CODE ###

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

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

print(cf(a,b)[-k])
import math
n = input()
a = list(map(int, input().split()))
b  = 0
cnt = 0
while "loop":
    for num in a
        if num % 2 == 1:
            b= 1
    if  b == 0:
        for num in a
        num /=2
        cnt+=1
print(cnt)


### FIXED CODE ###

import math
n = input()
a = list(map(int, input().split()))
b  = 0
cnt = 0
while "loop":
    for num in a:
        if num % 2 == 1:
            b= 1
    if  b == 0:
            a = [ i	/2 for i in a]
            cnt += 1
    else:
        break
print(cnt)
n,k,*a=map(int,open(0).read().split())
l,r,*b=[[]for _ in range(10**6)]
for i,v in enumerate(a):
  b[v]+=i,
  l+=len(b[v]),
s=a[0]
i=c=0
while 1:
  j=l[i]%len(b[s])
  if(c>k-2)>j:
    r+=s,
    i+=1
  else:i=-~b[s][j]%n
  c+=j<1
  if i<1:
    if c>k-2:break
    k%=c+1
    c=0
  s=a[i]
print(*r)

### FIXED CODE ###

from bisect import*
from collections import*
n,k,*a=map(int,open(0).read().split())
b=defaultdict(list)
for i,v in enumerate(a):b[v]+=i,
s=a[0]
i=c=0
while 1:
  t=b[s]
  m=len(t)
  j=bisect(t,i)
  c+=j==m
  i=t[j%m]+1
  if i==n:break
  s=a[i]
k%=c+1
s=a[0]
i=c=0
while c<k-1:
  t=b[s]
  m=len(t)
  j=bisect(t,i)
  c+=j==m
  i=t[j%m]+1
  s=a[i]
r=[]
while 1:
  t=b[s]
  m=len(t)
  j=bisect(t,i)
  if j==m:
    r+=s,
    i+=1
  else:
    i=t[j]+1
  if i==n:
    break
  s=a[i]
print(*r)
s=input()
b=False
result = []
for i in s:
  if i=='B':
    if not b:
      result.pop()
      b=True
  else:
    b=False
    result.append(i)
print(''.join(result))

### FIXED CODE ###

s=input()
result = []
for i in s:
  if i=='0':
    result.append('0')
  elif i=='1':
    result.append('1')
  elif i=='B':
    if not result:
      continue
    result.pop()
print(''.join(result))
n,k = map(int, input().split())
li = []
i = 0
for i<k:
  li.append(int(input()))
  i += 1
else:
  Li = list(n)
  while not set(li)&set(Li) == {}:
    n += 1
    Li = list(n)
  else: print("".join(Li))

### FIXED CODE ###

n,k = map(str, input().split())
li = list(map(str, input().split()))
Li = list(n)
while len(set(Li)&set(li)):
  n = int(n)+1
  Li = list(str(n))
else: print("".join(Li))
import math

N = int(input())
I = int(math.sqrt(N) // 1)
print(I)

a = []
for i in range(1, I):
  if N%i==0:
    j=N//i
    k = len(str(i))
    l = len(str(j))
    m = max(k, l)
    a.append(int(m))
print(min(a))

### FIXED CODE ###

N = int(input())
l = []
for a in range(1, 10**5+1):
  if N % a == 0:
    b = N // a
    s = max(len(str(a)), len(str(b)))
    l.append(int(s))
print(min(l))
import sys
n = int(input())
words = input().split()
for i in range(n-1)
    for j in range(1, i):
        if words[i] == words[j]:
                print('No')
                sys.exit()
    if words[i][-1] != words[i+1][1]:
        print('No')
        sys.exit()
print('Yes')

### FIXED CODE ###

import sys
n = int(input())
words=[]
for i in range(n):
    words += [input()]
for i in range(n-1):
    for j in range(i+1, n):
        if words[i] == words[j]:
                print('No')
                sys.exit()
    if words[i][-1] != words[i+1][0]:
        print('No')
        sys.exit()
print('Yes')
from collections import defaultdict

N, Q = map(int, input().split())
e = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    e[a].append(b)

q = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    q[p] += x

seen = [False] * (N + 1)
ans = [0] * (N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
print(*ans[1:])


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
e = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    e[a].append(b)

q = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    q[p] += x

seen = [False] * (N + 1)
ans = [0] * (N + 1)


def dfs(e, v, x):
    seen[v] = True
    ans[v] += x
    for next_v in e[v]:
        if seen[next_v]:
            continue
        else:
            dfs(e, next_v, x + q[next_v])


dfs(e, 1, q[1])
print(*ans[1:])
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np
node_num = int(input())
nodes=input().split()




route_list=np.zeros((node_num,node_num))


mi_count=0
for i in range(node_num-1):
    if i+2<node_num:
        route_list[i][i+1]=abs(int(nodes[i+1])-int(nodes[i])) if abs(int(nodes[i+1])-int(nodes[i])) != 0 else 0.0000001
        route_list[i][i+2]=abs(int(nodes[i+2])-int(nodes[i])) if abs(int(nodes[i+2])-int(nodes[i])) != 0 else 0.0000001
    else:
        route_list[i][i+1]=abs(int(nodes[i+1])-int(nodes[i])) if abs(int(nodes[i+1])-int(nodes[i])) != 0 else 0.0000001


route_list = csr_matrix(route_list)
#print(route_list)
dist_matrix= dijkstra(csgraph=route_list, directed=False, indices=0, return_predecessors=False)

dis=dist_matrix[-1]

print(int(dis))

### FIXED CODE ###

N = int(input())
H = [0] + [int(h) for h in input().split()]
dp = [999999999 for _ in range(N + 1)]
dp[0] = 0
dp[1] = 0
dp[2] = abs(H[2] - H[1])
for i in range(3, N + 1):
    dp[i] = min(dp[i], dp[i - 1] + abs(H[i - 1] - H[i]), dp[i - 2] + abs(H[i - 2] - H[i]))

print(dp[N])
*A,=map(int,open(0));i=1;t=[0]*A[0]
while i-2or t[i]:t[i]=1;i=A[i]
print(-1if i-2else sum(t))

### FIXED CODE ###

*A,=map(int,open(0));i=1;t=[0]*A[0]+[0]
while i-2and t[i]==0:t[i]=1;i=A[i]
print(-1if i-2else sum(t))
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

fact = [1]
for i in range(1, N+10):
    fact.append(fact[-1] * i % MOD)
def rev(x):
    return pow(x, MOD-2, MOD)
def cmb(i, k):
    if(i < k): return 0
    return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

if N==2:
    print(A[1], A[0])
    exit()

maxA = max(A)
ind = bisect_left(A, maxA//2)
res = 0
ress = -1
for i in range(ind, ind+1):
    if i<0 or N-1<=i:
        continue
    val = cmb(maxA, A[i])
    if res<val:
        res = val
        ress = A[i]
print(maxA, ress)

### FIXED CODE ###

# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

fact = [1]
for i in range(1, N + 10):
    fact.append(fact[-1] * i % MOD)


def rev(x):
    return pow(x, MOD - 2, MOD)


def cmb(i, k):
    if i < k:
        return 0
    return fact[i] * rev(fact[k]) * rev(fact[i - k]) % MOD


A.sort()
if N == 2:
    print(A[1], A[0])
    exit()

mv = A[-1]
vm = mv // 2
bli = bisect_left(A, vm)
if bli == N - 1:
    print(mv, A[bli - 1])
elif bli == 0:
    print(mv, A[bli])
else:
    if vm - A[bli - 1] < A[bli] - vm:
        print(mv, A[bli - 1])
    else:
        print(mv, A[bli])
HW = raw_input().split()
hw = raw_input().split()

printint(int(HW[0]) * int(HW[1]) - int(HW[0]) * int(hw[1]) - int(HW[1]) * int(hw[0]) + int(hw[0]) * int(hw[1]))


### FIXED CODE ###

HW = raw_input().split()
hw = raw_input().split()

print(int(HW[0]) * int(HW[1]) - int(HW[0]) * int(hw[1]) - int(HW[1]) * int(hw[0]) + int(hw[0]) * int(hw[1]))
n = input()
if n == '1' :
    print('Helli World')
else :
    a,b = map(int,input().split())
    print(a+b)

### FIXED CODE ###

n = input()
if n == '1' :
    print('Hello World')
else :
    a = int(input())
    b = int(input())
    print(a+b)
import sys
input = sys.stdin.readline

S = list(input())
S = [int(i) for i in S]

count_0 = 0
count_1 = 0

for i in range(len(S)):
	if (i % 2 == 1) ^ S[i]:
		count_0 += 1
	else:
		count_1 += 1
		
print(min(count_0, count_1))
		


### FIXED CODE ###

S = list(input())

count_0 = 0
count_1 = 0

for i in range(len(S)):
	if (i % 2 == 1) ^ (S[i] == '1'):
		count_0 += 1
	else:
		count_1 += 1
		
print(min(count_0, count_1))
import random

data=int(input().split
b=data[0]
c=data[1]
count_data=0
random_data=random.randint(0,b)
random_data2=random.randint(0,b)
random_data3=random.randint(0,b)
resalt=random_data+random_data2+random_data3
if resart<= c:
     count_data=count_data+1
else:
	pass
print(count_data)

### FIXED CODE ###

import sys

data=input().split(' ')
k=int(data[0])
data_1sub=k+1
s=int(data[1])
d=0
e=0
for i in range(data_1sub):
    for j in range(data_1sub):
        d=s-i-j
        if (0 <= d) and (d <= k):
            e=e+1
        else:
            pass
print(e)
n = int(input())
edges = [[] for _ in range(n+1)]
colors = [None] * (n+1)

for i in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edges[u].append((v, 0))
        edges[v].append((u, 0))
    else:
        edges[u].append((v, 1))
        edges[v].append((u, 1))

colors[1] = 0


def color(node, c):
    colors[node] = c
    for i, j in edges[node]:
        if colors[i] is None:
            new_color = (c + j)%2
            color(i, new_color)

color(1,1)

for i in colors[1:]:
    print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
edges = [[] for _ in range(n+1)]
colors = [None] * (n+1)

for i in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edges[u].append((v, 0))
        edges[v].append((u, 0))
    else:
        edges[u].append((v, 1))
        edges[v].append((u, 1))

colors[1] = 0


def color(node, c):
    colors[node] = c
    for i, j in edges[node]:
        if colors[i] is None:
            new_color = (c + j)%2
            color(i, new_color)

color(1,1)

for i in colors[1:]:
    print(i)
a = input()
ar = []
for i in range(len(a)):
  if i % 2 == 0:
    ar.append(i)
print("".join(ar))

### FIXED CODE ###

a = input()
ar = []
for i in range(len(a)):
  if i % 2 == 0:
    ar.append(a[i])
print("".join(ar))
import math

N, x, T = map(int, input().split)

print(math.ceil(N / x) * T)

### FIXED CODE ###

import math

N, x, T = map(int, input().split())

print(math.ceil(N / x) * T)
x,n=map(int,input().split())
ls=inp()
ls.sort()
if n==0:
    print(x)
    exit(0)
else:
    a=x-1
    b=x+1
    flag=False
    while(not flag):
        if a not in ls:
            print(a)
            exit(0)
        else:
            a-=1
        if b not in ls:
            print(b)
            exit(0)
        else:
            b+=1

### FIXED CODE ###

def inp():
    ls=list(map(int,input().split()))
    return ls
x,n=map(int,input().split())
ls=inp()
ans=0
d=float('inf')
for i in range(102):
    if i in ls:
        continue
    tmp = abs(x - i)
    if tmp < d:
        d = tmp
        ans = i
print(ans)
import math
import sys
from itertools import accumulate
from functools import reduce
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())
    = [list(list(sys.stdin.readline().rstrip())) for i in range(h)] #文字列を分解して二次元配列入力

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

if __name__ == "__main__":
    h,w = map(int, sys.stdin.readline().split())
    s =  [list(list(sys.stdin.readline().rstrip())) for i in range(h)]
    flag=0
    for i in range(h):
        for j in range(w): #２重for文で行列を一つずつ確認
            if s[i][j] == "#":
                if s[i-1][j] =="." and s[i+1][j] =="." and s[i][j-1] =="."  and s[i][j+1] ==".":#上下左右塗れなかった時
                    flag = 1
                    print("No")
                    exit()
    print("Yes" if flag==0 else "No")

### FIXED CODE ###

H,W=map(int,input().split())
S=["."+input()+"." for i in range(H)]
S=["."*(W+2)]+S+["."*(W+2)]
flag=0
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            if S[i-1][j]=="." and S[i+1][j]=="." and S[i][j-1]=="." and S[i][j+1]==".":
                flag=1
print("Yes" if flag==0 else "No")
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  #print("x1", x1, "x2", x2)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    r[city_b_par] = r[city_a]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        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):
    # ノードxが属する木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
    #ノード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())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=u.roots()
print(len(ans)-1)