Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
h , w = (int(i) for i in input().split())
a =[]
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]


for i in range(h):
    a.append(input())
    
f = True
def check(x,y):
    if a[x][y] =='.':
        return True
    for n in range(4):
        i = dx[n]
        j = dy[n]
#        print(a[x+i][y+j])
        if 0 <= x+i < w and 0 <= y + j < h and a[x+i][y+j]=='#':
            #print(x+i,y+j)
            return True
    return False
#print(check(0,3))
f = True
for i in range(w):
    for j in range(h):
        l = check(i,j)
        if not(l) and f:
            print ("No")
            f = False
if(f):
    print("Yes")


Fixed submission:
a, b, c = (int(i) for i in input().split())
d = int(input())
max_a = max(a,b,c)

ans = a + b + c + max_a * pow(2 , d) - max_a
print(ans)
Buggy python submission (verdict: Runtime Error):
S = int(input().split('/'))

print("2018/"+S[1]+'/'+S[2])


Fixed submission:
S = (input().split('/'))

print("2018/"+S[1]+'/'+S[2])
Buggy python submission (verdict: Runtime Error):
a=[int(x) for x in in input()]
print(sum(a))

Fixed submission:
a=[int(x) for x in input()]
print(sum(a))
Buggy python submission (verdict: Runtime Error):
N = int(input())

p = input().split(' ')
ans = 1
for i in range(N):
    if int(p[i])==i):
        ans += 1

print(ans//2)


Fixed submission:
N = int(input())

p = input().split(' ')
ans = 0
for i in range(N):
    if int(p[i]) == i+1:
        if not(i==N-1) and not(p[i+1] ==i+1):
            rrr = p[i]
            p[i] = p[i+1]
            p[i+1] = rrr
            ans +=1
        else:
            rrr = p[i]
            p[i]=p[i-1]
            p[i-1] =rrr
            ans +=1

print(ans)
#print(p)
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
a = 1
for i in range(N):
    b = int(input())
    a = a * b //math.gcd(a,b)

print(a)


Fixed submission:
def gcd(a,b):
    if a % b ==0:
        return b
    return gcd(b,a%b)

N = int(input())
a = 1
for i in range(N):
    b = int(input())
    a = a * b // gcd(a,b)

print(a)

Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
a = 1
for i in range(N):
    b = int(input())
    a = a * b //math.gcd(a,b)

print(a)


Fixed submission:
def gcd(a,b):
    if a % b ==0:
        return b
    return gcd(b,a%b)

N = int(input())
a = 1
for i in range(N):
    b = int(input())
    a = a * b // gcd(a,b)

print(a)
Buggy python submission (verdict: Runtime Error):
s=input()

print(s[0]+len(s)+s[-1])

Fixed submission:
s=input()

print(s[0],end="")
print(len(s)-2,end="")
print(s[-1])
Buggy python submission (verdict: Runtime Error):
n,a,b=[int(_) for_ in input().split()]
if n==1:
  if a==b:
    print(1)
  else:
    print(0)
print(max(0,(n-2)*(b-a)+1)

Fixed submission:
n,a,b=[int(_) for _ in input().split()]
if n==1:
  if a==b:
    print(1)
  else:
    print(0)
  exit()
print(max(0,(n-2)*(b-a)+1))
Buggy python submission (verdict: Runtime Error):
3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5

Fixed submission:
n,m=[int(_)for _ in input().split()]

ab=[[int(_) for _ in input().split()]for i in range(n)]
cd=[[int(_) for _ in input().split()]for i in range(m)]


def dist(p1,p2):
  return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])

for i in range(n):
  d=1000000000
  ans=0
  for j in range(m):
    if d>dist(ab[i],cd[j]):
      ans=j+1
      d=dist(ab[i],cd[j])
  print(ans)
Buggy python submission (verdict: Runtime Error):
H,W=[int(i) for i in input().split()
ans=[]
for i in range(H):
     lis =input()
     ans.append(lis)
     ans.append(lis)

print(ans)

Fixed submission:
H,W = [int(i) for i in input().split()]

for i in range(H):
    line = input()
    print(line)
    print(line)

Buggy python submission (verdict: Runtime Error):
H,W=[int(i) for i in input().split()
ans=[]
for i in range(H):
lis =input()
     ans.append(lis)
     ans.append(lis)

print(ans)

Fixed submission:
H,W = [int(i) for i in input().split()]

for i in range(H):
    line = input()
    print(line)
    print(line)

Buggy python submission (verdict: Runtime Error):
H,W=[int(i) for i in input().split()
ans=[]
for i in range(H):
 lis =input()
 ans.append(lis)
 ans.append(lis)

print(ans)

Fixed submission:
H,W = [int(i) for i in input().split()]

for i in range(H):
    line = input()
    print(line)
    print(line)
Buggy python submission (verdict: Runtime Error):
s=input()
c=0
ans=0
for i in range(len(s)):
  if s[i]=='T':
    c+=1
  if s[i]='S':
    c-=1
  ans = max(ans,c)
print(ans*2)

Fixed submission:
s=input()
c=0
ans=0
for i in range(len(s)):
  if s[i]=='T':
    c+=1
  if s[i]=='S':
    c-=1
  ans = max(ans,c)
print(ans*2)

Buggy python submission (verdict: Runtime Error):
s=input()
c=0
ans=0
for i in range(n):
  if s[i]=='T':
    c+=1
  if s[i]='S':
    c-=1
  ans = max(ans,c)
print(ans*2)

Fixed submission:
s=input()
c=0
ans=0
for i in range(len(s)):
  if s[i]=='T':
    c+=1
  if s[i]=='S':
    c-=1
  ans = max(ans,c)
print(ans*2)
Buggy python submission (verdict: Runtime Error):
a=[int(_) for i in range(n)]
if a[0]%2==0 or a[1]%2==0 or a[2]%2==0:
  print(0)
else:
  a.sort()
  print(a[0]*a[1])

Fixed submission:
a=[int(_) for _ in input().split()]
if a[0]%2==0 or a[1]%2==0 or a[2]%2==0:
  print(0)
else:
  a.sort()
  print(a[0]*a[1])
Buggy python submission (verdict: Runtime Error):
S, W = map(int(input().split()))
if W >= S:
    print("unsafe")
else:
    print("safe")

Fixed submission:
S, W = map(int, input().split())
if W >= S:
    print("unsafe")
else:
    print("safe")

Buggy python submission (verdict: Runtime Error):
S = int(input())
W = int(input())
if W >= S:
    print("unsafe")
else:
    print("safe")



Fixed submission:
S, W = map(int, input().split())
if W >= S:
    print("unsafe")
else:
    print("safe")
Buggy python submission (verdict: Runtime Error):
x = input()
if x = "0":
  print(1)
elif x = "1":
  print(0)  

Fixed submission:
x = input()
if x == "0":
  print(1)
else:
  print(0)
Buggy python submission (verdict: Runtime Error):


l,r,d = map(input().split(), int)
ans=0

for i = range(l,r+1):
    if (i%d == 0) ans += 1

print(ans)

Fixed submission:
l,r,d = map(int, input().split())
ans=0

for i in range(l,r+1):
    if (i%d == 0): ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
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())
union = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    union.union(A,B)
print(union.group_count()-1)


Fixed submission:
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())
union = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    union.union(A-1,B-1)
print(union.group_count()-1)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

class UnionFind:
    def __init__(self,num:int):
        self.r = [-1 for i in range(num)]
    def root(self,x:int):
        if(self.r[x] < 0):
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    def unite(self,x:int,y:int):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return False
        if(self.r[rx] > self.r[ry]):
            rx,ry = ry,rx
        self.r[rx] += self.r[ry]
        self.r[ry] = rx
        return True
    def size(self,x:int):
        return -self.r[self.root(x)]

N,M = map(int,input().split())
group = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    group.unite(A-1,B-1)
ans = 0
for i in range(N):
    ans = max(ans,group.size(i))
print(ans)


Fixed submission:
D,T,S = map(int,input().split())
if(D>T*S):
    print("No")
else:
    print("Yes")

Buggy python submission (verdict: Runtime Error):
from collections import Counter

class UnionFind:
    def __init__(self,num:int):
        self.r = [-1 for i in range(num)]
    def root(self,x:int):
        if(self.r[x] < 0):
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    def unite(self,x:int,y:int):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return False
        if(self.r[rx] > self.r[ry]):
            rx,ry = ry,rx
        self.r[rx] += self.r[ry]
        self.r[ry] = rx
        return True
    def size(self,x:int):
        return -self.r[self.root(x)]

N,M = map(int,input().split())
group = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    group.unite(A-1,B-1)
ans = 0
for i in range(N):
    ans = max(ans,group.size(i))
print(group.r)
print(ans)


Fixed submission:
D,T,S = map(int,input().split())
if(D>T*S):
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = 0
def seek(LIST:list):
    global ans
    max_num = max(LIST)
    index = LIST.index(max(LIST))
    if(index == 0):
        ans += max_num*len(LIST)-sum(LIST)
    else:
        cal_LIST = LIST[index:]
        ans += max_num*len(cal_LIST)-sum(cal_LIST)
        new_list = LIST[0:index]
        seek(new_list)
seek(A)
print(ans)


Fixed submission:
N = int(input())
A = list(map(int,input().split()))
max_num = A[0]
ans = 0
for i in A:
    if(max_num>=i):
        ans += max_num-i
    else:
        max_num = i
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = 0
def seek(LIST:list):
    global ans
    max_num = max(LIST)
    index = LIST.index(max(LIST))
    if(index == 0):
        for i in LIST[index:]:
            ans += max_num-i
    else:
        for i in LIST[index:]:
            ans += max_num-i
        new_list = LIST[0:index]
        seek(new_list)
seek(A)
print(ans)


Fixed submission:
N = int(input())
A = list(map(int,input().split()))
max_num = A[0]
ans = 0
for i in A:
    if(max_num>=i):
        ans += max_num-i
    else:
        max_num = i
print(ans)
Buggy python submission (verdict: Runtime Error):
S = list(input())
print(String(S[0:3]))


Fixed submission:
S = input()
print(S[0:3])
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
h = list(map(int,input().split()))
route = [[False for x in range(n+1)] for x in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    route[a][b] = True
    route[b][a] = True
ans = 0
for i in range(1,n+1):
    if(route[i] == [False for x in range(n+1)]):
        ans+=1
        continue
    for j in range(1,n+1):
        if(route[i][j]):
            if(h[i-1] <= h[j-1]):
                break
    else:
        ans+=1
print(ans)


Fixed submission:
n,m = map(int,input().split())
h = list(map(int,input().split()))
h.insert(0,0)
ans = [True for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    if(h[a] > h[b]):
        ans[b] = False
    elif(h[a] < h[b]):
        ans[a] = False
    else:
        ans[a] = ans[b] = False
print(ans.count(True)-1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
sum = 0
array = list(map(int,input().split()))
for i in range(1,N):
    print(array.count(i))
    sum += array.count(i)
print(0)


Fixed submission:
N = int(input())
sum = 0
now = 1
for i in sorted(list(map(int,input().split()))):
    if(now == i):
        sum += 1
    else:
        print(sum)
        for j in range(i-now-1):
            print(0)
        now = i
        sum = 1
else:
    print(sum)
while(now < N):
    now += 1
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce

def gcd(*num):
    return reduce(math.gcd,num)

K = int(input())
sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum += gcd(i,j,k)
print(sum)


Fixed submission:
import math
from functools import reduce
 
def gcd(*num):
    return reduce(math.gcd,num)
 
K = int(input())
sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum += gcd(i,j,k)
print(sum)
Buggy python submission (verdict: Runtime Error):
A,B,M = map(int,input().split())
A_ = list(map(int,input().split()))
B_ = list(map(int,input().split()))
mini =min(A_) + min(B_)
for i in range(M):
    array = list(map(int,input().split()))
    m = A_[array[0]-1] + B_[array[0]-1] -array[2]
    if(mini > m):
        mini = m
print(mini)


Fixed submission:
A,B,M = map(int,input().split())
A_ = list(map(int,input().split()))
B_ = list(map(int,input().split()))
mini =min(A_) + min(B_)
for i in range(M):
    array = list(map(int,input().split()))
    m = A_[array[0]-1] + B_[array[1]-1] -array[2]
    if(mini > m):
        mini = m
print(mini)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
str = []
for i in range(N):
    str.append(input())
num = [str.count(x) for x in set(str)]
max_list = []
for i in set(str):
    if(str.count(i) == max(num)):
        max_list.append(i)
max_list.sort()
for i in max_list :print(i)


Fixed submission:
N = int(input())
str = {}
for i in range(N):
    key = input()
    if(key in str.keys()):
        str[key] += 1
    else:
        str[key] = 1
m = max(str.values())
str = sorted(str.items(),key=lambda x:x[1],reverse=True)
z = []
for i in range(len(str)):
    if(str[i][1] == m):
        z.append(str[i][0])
z.sort()
for i in z:print(i)
Buggy python submission (verdict: Runtime Error):
N = int(input())
L = sorted(map(int,input().split()),reverse=True)
num = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            array = [L[i],L[j],L[k]]
            if(array[0]>=array[1]+array[2]):
                break
            else:
                num += 1
print(num)


Fixed submission:
A,B = map(int,input().split())
if(A>=2*B):
    print(A-2*B)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf") for i in range(n)]
dp[0] = 0
for i in range(1,n):
    if(i<k):
        for j in range(1,i+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
    else:
        for j in range(1,k+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
print(dp[-1])


Fixed submission:
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf") for i in range(n)]
dp[0] = 0
for i in range(1,n):
    if(i<k):
        for j in range(1,i+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
    else:
        for j in range(1,k+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int,input().split())
dp = [[0 for x in range(w+1)] for x in range(n+1)]
array = [[int(x) for x in input().split()] for x in range(n)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(array[j-1][0] > i):
            dp[j][i] = dp[j-1][i]
        else:
            if(dp[j-1][i] < dp[j-1][i-array[j-1][0]] + array[j-1][1]):
                dp[j][i] = dp[j-1][i-array[j-1][0]] + array[j-1][1]
            else:
                dp[j][i] = dp[j-1][i]
print(dp[-1][-1])


Fixed submission:
n,w = map(int,input().split())
dp = [[0 for x in range(w+1)] for x in range(n+1)]
array = [[int(x) for x in input().split()] for x in range(n)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(array[j-1][0] > i):
            dp[j][i] = dp[j-1][i]
        else:
            if(dp[j-1][i] < dp[j-1][i-array[j-1][0]] + array[j-1][1]):
                dp[j][i] = dp[j-1][i-array[j-1][0]] + array[j-1][1]
            else:
                dp[j][i] = dp[j-1][i]
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = [""]+list(input())
t = [""]+list(input())
dp = [[0 for x in range(len(s))] for x in range(len(t))]
for y in range(1,len(t)):
    for x in range(1,len(s)):
        if(t[y] == s[x]):
            dp[y][x] = dp[y-1][x-1]+1
        else:
            dp[y][x] = max(dp[y-1][x],dp[y][x-1])
y,x = len(t)-1,len(s)-1
ans = []
while(dp[y][x] > 0):
    if(dp[y][x] == dp[y-1][x]):
        y -= 1
    elif(dp[y][x] == dp[y][x-1]):
        x -= 1
    else:
        ans.append(s[x])
        y -= 1
        x -= 1
ans.reverse()
print("".join(ans))


Fixed submission:
s = [""]+list(input())
t = [""]+list(input())
dp = [[0 for x in range(len(s))] for x in range(len(t))]
for y in range(1,len(t)):
    for x in range(1,len(s)):
        if(t[y] == s[x]):
            dp[y][x] = dp[y-1][x-1]+1
        else:
            dp[y][x] = max(dp[y-1][x],dp[y][x-1])
y,x = len(t)-1,len(s)-1
ans = []
while(dp[y][x] > 0):
    if(dp[y][x] == dp[y-1][x]):
        y -= 1
    elif(dp[y][x] == dp[y][x-1]):
        x -= 1
    else:
        ans.append(s[x])
        y -= 1
        x -= 1
ans.reverse()
print("".join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
h,w = map(int,input().split())
stage = [["#" for x in range(w+2)] for x in range(h+2)]
for i in range(1,h+1):
    stage[i][1:w+1] = list(input())
dp = np.zeros([h+2,w+2],dtype=int)
dp[1][1] = 1
for j in range(1,h+1):
    for i in range(1,w+1):
        dp[j][i] = dp[j][i]%(10**9+7)
        if(stage[j+1][i] == "."):
            dp[j+1][i] += dp[j][i]
        if(stage[j][i+1] == "."):
            dp[j][i+1] += dp[j][i]
print(dp[h][w])


Fixed submission:
h,w = map(int,input().split())
stage = [["#" for x in range(w+2)] for x in range(h+2)]
for i in range(1,h+1):
    stage[i][1:w+1] = list(input())
dp = [[0 for x in range(w+2)] for x in range(h+2)]
dp[1][1] = 1
for j in range(1,h+1):
    for i in range(1,w+1):
        dp[j][i] = dp[j][i]%(10**9+7)
        if(stage[j+1][i] == "."):
            dp[j+1][i] += dp[j][i]
        if(stage[j][i+1] == "."):
            dp[j][i+1] += dp[j][i]
print(dp[h][w])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(float,input().split()))
dp = [[0 for x in range(n+1)] for x in range(n+1)]
dp[0][0] = 1
for y in range(n):
    for x in range(n):
        dp[y+1][x] += dp[y][x]*(1-p[y])
        dp[y+1][x+1] += dp[y][x]*p[y]
print(sum(dp[n][n//2+1:n+1]))


Fixed submission:
n = int(input())
p = list(map(float,input().split()))
dp = [[0 for x in range(n+1)] for x in range(n+1)]
dp[0][0] = 1
for y in range(n):
    for x in range(n):
        dp[y+1][x] += dp[y][x]*(1-p[y])
        dp[y+1][x+1] += dp[y][x]*p[y]
print(sum(dp[n][n//2+1:n+1]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans = 1
flag = False
A.sort()
for i in range(N):
  ans *= A[i]
  if(ans>1000000000000000000):
    flag = True

if(flag):
  print(-1)
else:
  print(ans)

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

ans = 1
flag = False
A.sort()
for i in range(N):
  ans *= A[i]
  if(ans>1000000000000000000):
    flag = True
    break

if(flag):
  print(-1)
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
r=sys.stdin.readline
N,M=map(int,r().split())
city=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,r().split())
    city[a].append(b)
    city[b].append(a)
check=[True]+[False]*(N)
def dfs(v):
    stack=[v]
    visited=[False]*(N+1)
    visited[v]=True
    while stack:
        cur=stack.pop()
        check[cur]=True
        for v in city[cur]:
            if not visited[v]:
                stack.append(v)
cnt=0
for i in range(1,N+1):
    if not check[i]:
        dfs(i)
        cnt+=1
print(cnt-1)

Fixed submission:
import sys
r=sys.stdin.readline
N,M=map(int,r().split())
city=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,r().split())
    city[a].append(b)
    city[b].append(a)
check=[True]+[False]*(N)
def dfs(v):
    stack=[v]
    while stack:
        cur=stack.pop()
        check[cur]=True
        for v in city[cur]:
            if not check[v]:
                stack.append(v)
cnt=0
for i in range(1,N+1):
    if not check[i]:
        dfs(i)
        cnt+=1
print(cnt-1)