Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

N,M,Q=map(int, input().split())

left=[]
right=[]
for i in range(M):
    l,r=map(int, input().split())
    left.append(l)
    right.append(r)
#left=np.array(left)
#right=np.array(right)
for i in range(Q):
    p,q=map(int, input().split())
    #l=left>=p
    #r=right<=q
    #ans=(l*r).sum()
    ans=0
    for j in range(M):
        l=left[j]
        r=right[j]
        if p<=l and r<=q:
            ans+=1
    print(ans)

Fixed submission:
N,M,Q=map(int, input().split())
L=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r=map(int, input().split())
    L[l][r]+=1

#print(L)
for i in range(1,N+1):
    for j in range(1,N+1):
        L[i][j]+=L[i][j-1]+L[i-1][j]-L[i-1][j-1]

#print(L)

for i in range(Q):
    p,q=map(int, input().split())
    ans=L[q][q]-L[p-1][q]-L[q][p-1]+L[p-1][p-1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

N,M,Q=map(int, input().split())

left=[]
right=[]
for i in range(M):
    l,r=map(int, input().split())
    left.append(l)
    right.append(r)
#left=np.array(left)
#right=np.array(right)
for i in range(Q):
    p,q=map(int, input().split())
    #l=left>=p
    #r=right<=q
    #ans=(l*r).sum()
    ans=0
    for j in range(M):
        l=left[j]
        r=right[j]
        if p<=l and r<=q:
            ans+=1
    print(ans)

Fixed submission:
N,M,Q=map(int, input().split())
L=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r=map(int, input().split())
    L[l][r]+=1

#print(L)
for i in range(1,N+1):
    for j in range(1,N+1):
        L[i][j]+=L[i][j-1]+L[i-1][j]-L[i-1][j-1]

#print(L)

for i in range(Q):
    p,q=map(int, input().split())
    ans=L[q][q]-L[p-1][q]-L[q][p-1]+L[p-1][p-1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N,M,Q=map(int, input().split())

left=[]
right=[]
for i in range(M):
    l,r=map(int, input().split())
    left.append(l)
    right.append(r)
left=np.array(left)
right=np.array(right)
for i in range(Q):
    p,q=map(int, input().split())
    l=left>=p
    r=right<=q
    ans=(l*r).sum()
    print(ans)

Fixed submission:
N,M,Q=map(int, input().split())
L=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r=map(int, input().split())
    L[l][r]+=1

#print(L)
for i in range(1,N+1):
    for j in range(1,N+1):
        L[i][j]+=L[i][j-1]+L[i-1][j]-L[i-1][j-1]

#print(L)

for i in range(Q):
    p,q=map(int, input().split())
    ans=L[q][q]-L[p-1][q]-L[q][p-1]+L[p-1][p-1]
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
D,G=map(int, input().split())

L=[]
for i in range(D):
    p,c=map(int, input().split())
    L.append((p,c))

from itertools import permutations
from math import ceil
ans=float("INF")
for t in permutations(range(1,D+1)):
    #print(t)
    t=list(t)
    now=G
    sub=0
    for x in t:
        p,c=L[x-1]
        if now/(x*100)<=p:
            sub+=ceil(now/(x*100))
            break
        elif x*p*100+c>=now:
            sub+=p
            break
        else:
            now-=x*p*100+c
            sub+=p

    #print(t, sub)
    ans=min(ans, sub)
    
print(ans)

Fixed submission:
D,G=map(int, input().split())

L=[]
for i in range(D):
    p,c=map(int, input().split())
    L.append((p,c))

from itertools import permutations
from math import ceil
ans=float("INF")
for t in permutations(range(1,D+1)):
    #print(t)
    t=list(t)
    now=G
    sub=0
    for x in t:
        p,c=L[x-1]
        if now/(x*100)<=p:
            sub+=ceil(now/(x*100))
            break
        elif x*p*100+c>=now:
            sub+=p
            break
        else:
            now-=x*p*100+c
            sub+=p

    #print(t, sub)
    ans=min(ans, sub)
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def cmbn2(n):
  #n>=2
  return int(n*(n-1)/2)

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
for i in range(N):
  R[i+1]=R[i]+A[i]
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[:10],)
#print(R.count(4))

ans=0
for a in list(set(R[1:])):
  b=R.count(a)
  if b>=2:
    ans+=cmbn2(b)
print(ans)
  

Fixed submission:
def cmbn2(n):
  #n>=2
  return int(n*(n-1)/2)

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
D={0:1}
for i in range(N):
  R[i+1]=R[i]+A[i]
  if R[i+1] not in D.keys():
    D[R[i+1]]=1
  else:
    D[R[i+1]]+=1
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[1:10],)
#print(R.count(4))

ans=0
for b in D.values():
  
  if b>=2:
    ans+=cmbn2(b)
print(ans)
#print(D.values())

Buggy python submission (verdict: Time Limit Exceeded):
def cmb(n, r):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n

  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]

  for p in range(2,r+1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1,r,p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot

  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])

  return result

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
for i in range(N):
  R[i+1]=R[i]+A[i]
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[:10],)
#print(R.count(4))

ans=0
for a in list(set(R[1:])):
  b=R.count(a)
  if b>=2:
    ans+=cmb(b,2)
print(ans)

Fixed submission:
def cmbn2(n):
  #n>=2
  return int(n*(n-1)/2)

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
D={0:1}
for i in range(N):
  R[i+1]=R[i]+A[i]
  if R[i+1] not in D.keys():
    D[R[i+1]]=1
  else:
    D[R[i+1]]+=1
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[1:10],)
#print(R.count(4))

ans=0
for b in D.values():
  
  if b>=2:
    ans+=cmbn2(b)
print(ans)
#print(D.values())
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int, input().split()))
A=sorted(A)

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

now=0
l=0
r=0
for i in range(n-1):
    for j in range(i+1,n):
        c=cmb(A[j],A[i])
        if now<c:
            now=c
            l=A[i]
            r=A[j]
print(r,l)



Fixed submission:

n=int(input())
A=sorted(list(map(int, input().split())))
amax=max(A)
half=amax/2

ans=0
now=amax
for a in A:
  if abs(a-half)<=now and a<amax:
    now=abs(a-half)
    ans=a
print(amax, ans)

Buggy python submission (verdict: Runtime Error):

n=int(input())
A=sorted(list(map(int, input())))
amax=max(A)
half=amax/2

ans=0
now=amax
for a in A:
  if abs(a-half)<=now:
    now=abs(a-half)
    ans=a
print(amax, ans)

Fixed submission:

n=int(input())
A=sorted(list(map(int, input().split())))
amax=max(A)
half=amax/2

ans=0
now=amax
for a in A:
  if abs(a-half)<=now and a<amax:
    now=abs(a-half)
    ans=a
print(amax, ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
n=int(input())
A=sorted(list(map(int, input())))
amax=max(A)
half=amax/2

ans=0
now=amax
for a in A:
  if abs(a-half)<=now:
    now=abs(a-half)
    ans=a
print(amax, ans)

Fixed submission:

n=int(input())
A=sorted(list(map(int, input().split())))
amax=max(A)
half=amax/2

ans=0
now=amax
for a in A:
  if abs(a-half)<=now and a<amax:
    now=abs(a-half)
    ans=a
print(amax, ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
n=int(input())
A=sorted(list(map(int, input())))
amax=max(A)
m=bisect_left(A,amax/2)
a,b=A[m],A[m+1]
if a-amax/2<=amax-b-amax/2:
  print(amax, a)
else:
  print(amax,b)

Fixed submission:

n=int(input())
A=sorted(list(map(int, input().split())))
amax=max(A)
half=amax/2

ans=0
now=amax
for a in A:
  if abs(a-half)<=now and a<amax:
    now=abs(a-half)
    ans=a
print(amax, ans)
Buggy python submission (verdict: Runtime Error):
S=list(input())
abc=list("abcdefghijklmnopqrstuvwxyz")
idx={}
for i in range(26):
    idx[abc[i]]=i
D=[0]*26
for s in S:
    D[idx[s]]+=1

if len(S)!=26:
    for i in range(26):
        if D[idx[abc[i]]]==0:
            ans="".join(S)+abc[i]
            break
        
else:
    ans=-1
    now=S[-1]
    for i in range(len(S)-1, 0,-1):
        if idx[S[i]]> idx[S[i-1]]:
            now=sorted(list(now))
            #print(now)
            for j,n in enumerate(now):
                if idx[n]>idx[S[i-1]]:
                    pre=n

                break

            ans="".join(S[:i-1])+pre
            break


        else:
            now=str(now)
            now+=S[i-1]

print(ans)

Fixed submission:
S=list(input())
N=len(S)
abc=list("abcdefghijklmnopqrstuvwxyz")
D={}
for a in abc:
    D[a]=0
idx={}
for i in range(26):
    idx[abc[i]]=i

for s in S:
    D[s]+=1
L=[]
for k,v in D.items():
    if v==0:
        L.append(k)

L=sorted(L)
if len(L)==0:
    lis=[]
    for i in range(25,-1,-1):
        s=S[i]
        lis.append(s)
        if i!=0:
            if idx[s]>idx[S[i-1]]:
                break
    if len(lis)==26:
        print(-1)
        exit()

    lis=sorted(lis)
    for l in lis:
        if idx[S[i-1]]<idx[l]:
            add=l
            break
    ans="".join(S[:i-1])+add
    print(ans)

        
else:
    print("".join(S)+L[0])
#yzxwvutsrqponmlkjihgfedcba
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=list(map(int, input().split()))
if len(set(S))==3:
  print("Three")
elif len(set(S))==4:
  print("Four")

Fixed submission:
N=int(input())
S=input().split()
if len(set(S))==3:
  print("Three")
elif len(set(S))==4:
  print("Four")
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

print(1)
nex=input()
if nex=="Vacant":
    exit()
nleft=1
left=nex
print(N)
nex=input()
if nex=="Vacant":
    exit()
nright=N
right=nex

for i in range(20)
    nmid=(nright+nleft)//2
    print(nmid)
    nex=input()
    if nex=="Vacant":
        exit()
    mid=nex
    flag=True
    if nleft%2!=nmid%2:
        if left==mid:
            right=mid
            nright=nmid
            flag=False
    else:
        if left!=mid:
            right=mid
            nright=nmid
            flag=False
    if flag:
        left=mid
        nleft=nmid

Fixed submission:
N=int(input())

print(0)
nex=input()
if nex=="Vacant":
    exit()
nleft=0
left=nex
print(N-1)
nex=input()
if nex=="Vacant":
    exit()
nright=N-1
right=nex

for i in range(20):
    nmid=(nright+nleft)//2
    print(nmid)
    nex=input()
    if nex=="Vacant":
        exit()
    mid=nex
    flag=True
    if nleft%2!=nmid%2:
        if left==mid:
            right=mid
            nright=nmid
            flag=False
    else:
        if left!=mid:
            right=mid
            nright=nmid
            flag=False
    if flag:
        left=mid
        nleft=nmid
Buggy python submission (verdict: Runtime Error):
import numpy as np
N,C=map(int, input().split())

#s~tでc
L=np.zeros((C, 10**5+2),dtype="int")

for i in range(N):
    s,t,c=map(int, input().split())
    L[c-1,s-1]+=1
    L[c-1,t]-=1

L=np.cumsum(L, axis=1)
print(max(np.sum(L,axis=0))


Fixed submission:
import numpy as np
N,C=map(int, input().split())

#s~tでc
L=np.zeros((C, 10**5+1))

for i in range(N):
    s,t,c=map(int, input().split())
    L[c-1,s-1]+=1
    L[c-1,t]-=1

L=np.cumsum(L, axis=1)
print(int((L>0).sum(axis=0).max()))
Buggy python submission (verdict: Runtime Error):
A,B,C,D=map(int, list(input()))
L=["+","-"]

for a in L:
  for b in L:
    for c in L:
      #now=A
      if a=="+":
        now+=B
      else:
        now-=B
      if b=="+":
        now+=C
      else:
        now-=C
      if c=="+":
        now+=D
      else:
        now-=D
      print(now)
      if now==7:
        print(str(A)+a+str(B)+b+str(C)+c+str(D)+"=7")
        exit()


Fixed submission:
A,B,C,D=map(int, list(input()))
L=["+","-"]

for a in L:
  for b in L:
    for c in L:
      now=A
      if a=="+":
        now+=B
      else:
        now-=B
      if b=="+":
        now+=C
      else:
        now-=C
      if c=="+":
        now+=D
      else:
        now-=D
      #print(now)
      if now==7:
        print(str(A)+a+str(B)+b+str(C)+c+str(D)+"=7")
        exit()
Buggy python submission (verdict: Runtime Error):
N,M,K=map(int, input().split())
#最初しろ
#行、列ごとに反転
L=[0]*(10*7)
if K==0 or K==N*M:
    print("Yes")
else:
    for h in range(N):
        for w in range(M):
            now=h*w+(N-h)*(M-w)
            L[now]+=1
    if L[K]>0:
        print("Yes")
    else:
        print("No")



Fixed submission:
N,M,K=map(int, input().split())
#最初しろ
#行、列ごとに反転
L=[0]*(10**7)
if K==0 or K==N*M:
    print("Yes")
else:
    for h in range(N+1):
        for w in range(M+1):
            now=h*w+(N-h)*(M-w)
            L[now]+=1
    if L[K]>0:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))
count=[0]*10**6
for a in A:
  count[A]+=1
  
ans=0
for a in range(max(A)+1):
  now=count[a-1]+count[a]+count[a+1]
  ans=max(ans, now)
  
print(ans)

Fixed submission:
N=int(input())
A=list(map(int, input().split()))
count=[0]*10**6
for a in A:
  count[a]+=1
  
ans=0
for a in range(max(A)+1):
  now=count[a-1]+count[a]+count[a+1]
  ans=max(ans, now)
  
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))

pre=(A[0]==1)
count=0
ans=0
if pre:
  count+=1
for i in range(1,N):
  if pre:
    if A[i]!=i+1:
      ans+=ceil(count/2)
      count=0
      pre=False
    else:
      count+=1
  else:
    if A[i]==i+1:
      count+=1
      pre=True
if pre:
  ans+=ceil(count/2)
print(ans)

Fixed submission:
from math import ceil
N=int(input())
A=list(map(int, input().split()))

pre=(A[0]==1)
count=0
ans=0
if pre:
  count+=1
for i in range(1,N):
  if pre:
    if A[i]!=i+1:
      ans+=ceil(count/2)
      count=0
      pre=False
    else:
      count+=1
  else:
    if A[i]==i+1:
      count+=1
      pre=True
if pre:
  ans+=ceil(count/2)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import gcd
N=int(input())
def lcm(a,b):
    return a//gcd(a,b)*b
T=[]
for i in range(N):
    t=int(input())
    T.append(t)
a=1
for i in range(N):
    a=lcm(a,T[i])

print(a)

Fixed submission:
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

N=int(input())
ans=1
for i in range(N):
    t=int(input())
    ans=lcm(ans, t)
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import gcd
N=int(input())
def lcm(a,b):
    return a//gcd(a,b)*b
T=[]
for i in range(N):
    t=int(input())
    T.append(t)
a=1
for i in range(N):
    a=lcm(a,T[i])

print(a)

Fixed submission:
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

N=int(input())
ans=1
for i in range(N):
    t=int(input())
    ans=lcm(ans, t)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

from collections import deque
N=int(input())
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
que=[(K-1,0)]
done=[-1]*N
while que:
    t=que.pop(0)
    now,nowd=t
    done[now]=nowd
    for nex in T[now]:
        nexnode,nexd=nex
        if done[nexnode]!=-1:
            continue
        else:
            que.append((nexnode, nowd+nexd))

#print(done)
for i in range(Q):
    x,y=map(int, input().split())
    print(done[x-1]+done[y-1])

Fixed submission:
N=int(input())
import sys
sys.setrecursionlimit(10**6)
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
dfs(K-1,0)
for i in range(Q):
    x,y=map(int, input().split())
    print(D[x-1]+D[y-1])

Buggy python submission (verdict: Runtime Error):

from collections import deque
N=int(input())
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
que=[(K-1,0)
done=[-1]*N
while que:
    t=que.pop(0)
    now,nowd=t
    done[now]=nowd
    for nex in T[now]:
        nexnode,nexd=nex
        if done[nexnode]!=-1:
            continue
        else:
            que.append((nexnode, nowd+nexd))

#print(done)
for i in range(Q):
    x,y=map(int, input().split())
    print(done[x-1]+done[y-1])

Fixed submission:
N=int(input())
import sys
sys.setrecursionlimit(10**6)
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
dfs(K-1,0)
for i in range(Q):
    x,y=map(int, input().split())
    print(D[x-1]+D[y-1])
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))

  
def judge(n):
  return n//400

rate=[0]*8
masters=0
for a in A:
  if judge(a)<8:
    rate[judge(a)]+=1
  else:
    masters+=1
  
count=0
for r in rate:
  if r!=0:
    count+=1
MAX=min(count+masters)


print(max(1,count),MAX)




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

  
def judge(n):
  return n//400

rate=[0]*8
masters=0
for a in A:
  if judge(a)<8:
    rate[judge(a)]+=1
  else:
    masters+=1
  
count=0
for r in rate:
  if r!=0:
    count+=1
MAX=count+masters


print(max(1,count),MAX)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))
master=False
if max(A)>=3200:
  master=True
  
def judge(n):
  return n//400

rate=[0]*8
for a in A:
  if judge(a)>=8:
    rate[judge(a)]+=1
  
count=0
for r in rate:
  if r!=0:
    count+=1
if master:
  MAX=min(count+1, 8)
else:
  MAX=count

print(count,MAX)

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

  
def judge(n):
  return n//400

rate=[0]*8
masters=0
for a in A:
  if judge(a)<8:
    rate[judge(a)]+=1
  else:
    masters+=1
  
count=0
for r in rate:
  if r!=0:
    count+=1
MAX=count+masters


print(max(1,count),MAX)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))
master=False
if max(A)>=3200:
  master=True
  
def judge(n):
  return n//400

rate=[0]*8
for a in A:
  rate[judge(a)]+=1
  
count=0
for r in rate:
  if r!=0:
    count+=1
if master:
  MAX=min(count+1, 8)
else:
  MAX=count

print(count,MAX)

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

  
def judge(n):
  return n//400

rate=[0]*8
masters=0
for a in A:
  if judge(a)<8:
    rate[judge(a)]+=1
  else:
    masters+=1
  
count=0
for r in rate:
  if r!=0:
    count+=1
MAX=count+masters


print(max(1,count),MAX)
Buggy python submission (verdict: Runtime Error):
A=list(map(int, input().split()))
if N<=2:
    print(1)
    exit()

now=0
ans=1
for i in range(1,N):
    if i==1:
        if A[i]-A[i-1]==0:
            now=0
        else:
            now=(A[i]-A[i-1])//(abs(A[i]-A[i-1]))
        if now>=1:
            plus=True
        elif now==0:
            plus=-1
        else:
            plus=False
            
    else:
        if A[i]-A[i-1]==0:
            nex=0
        else:
            nex=(A[i]-A[i-1])//(abs(A[i]-A[i-1]))
        if plus==-1:
            if nex>=1:
                plus=True
            elif nex<0:
                plus=False
        elif plus:
            if nex<0:
                plus=-1
                ans+=1
        else:
            if nex>0:
                plus=-1
                ans+=1

print(ans)



Fixed submission:
N=int(input())
A=list(map(int, input().split()))
if N<=2:
    print(1)
    exit()

now=0
ans=1
for i in range(1,N):
    if i==1:
        if A[i]-A[i-1]==0:
            now=0
        else:
            now=(A[i]-A[i-1])//(abs(A[i]-A[i-1]))
        if now>=1:
            plus=True
        elif now==0:
            plus=-1
        else:
            plus=False
            
    else:
        if A[i]-A[i-1]==0:
            nex=0
        else:
            nex=(A[i]-A[i-1])//(abs(A[i]-A[i-1]))
        if plus==-1:
            if nex>=1:
                plus=True
            elif nex<0:
                plus=False
        elif plus:
            if nex<0:
                plus=-1
                ans+=1
        else:
            if nex>0:
                plus=-1
                ans+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
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())


input = sys.stdin.readline
N, M = map(int, input().split())
AB  = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
for a, b in AB:
    uf.union(a, b)
print(uf.group_count()-1)


Fixed submission:
import sys
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())


input = sys.stdin.readline
N, M = map(int, input().split())
AB  = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
for a, b in AB:
    a -= 1
    b -= 1
    uf.union(a, b)
print(uf.group_count()-1)