Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02902 (python)

Fixed submission:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N


def joint(v, visit):
    if impossible[v]:
        return None
    visit = visit + [v]
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if t is not None:
            return t
    impossible[v] = True
    return None


def solve(l):
    n = len(l)
    d = {l[i]: i for i in range(n)}
    for i in range(n):
        x = l[i]
        for y in link[x]:
            if y in d:
                j = d[y]
                if (i + 1) % n == j:
                    continue
                if j < i:
                    l = l[j : i + 1]
                else:
                    l = l[: i + 1] + l[j:]
                return solve(l)
    return l
            

def main():
    t = None
    for i in range(N):
        t = joint(i, [])
        if t is not None:
            break
    if t is None:
        print(-1)
        return
    
    ans = solve(t)
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N


def joint(v, visit):
    if impossible[v]:
        return None
    visit = visit + [v]
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if t is not None:
            return t
    impossible[v] = True
    return None


def main():
    ans = None
    for i in range(N):
        ans = joint(i, [])
        if ans is not None:
            break
    if ans is None:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()
Problem p02947 (python)

Fixed submission:
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())
S = [input() for _ in range(N)]

d = {}
for s in S:
    s = "".join(sorted(s))
    if s in d:
        d[s] += 1
    else:
        d[s] = 1
ans = 0
for v in d.values():
    if v > 1:
        ans += cmb(v, 2)
print(ans)

Buggy submission (verdict: Runtime Error):
from scipy.special import comb

N = int(input())
S = [input() for _ in range(N)]

d = {}
for s in S:
    s = "".join(sorted(s))
    if s in d:
        d[s] += 1
    else:
        d[s] = 1
ans = 0
for v in d.values():
    if v > 1:
        ans += comb(v, 2)
print(ans)
Problem p02960 (python)

Fixed submission:
#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in l[li]:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(int(dp[-1][5]))

Buggy submission (verdict: Runtime Error):
import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        for v in range(10):
            w = v * now % 13
            x[w:13] += x_[:13 - w]
            x[:w] += x_[13 - w:]
    else:
        v = int(s) * now % 13
        x[w:13] = x_[:13 - w]
        x[:w] = x_[13 - w:]
    x %= mod
    now, pre = (now - pre) % 13, now
    x_ = x
print(int(dp[-1][5]))
Problem p02971 (python)

Fixed submission:
N  = int(input())
A = [int(input()) for _ in range(N)]

mx1 = max(A)
A_ = A[:]
A_.remove(mx1)
mx2 = max(A_)
for a in A:
    if a == mx1:
        print(mx2)
    else:
        print(mx1)

Buggy submission (verdict: Runtime Error):
A[:].remove(mx1)
Problem p02972 (python)

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

b = [0] * (N + 1)
half = N // 2
b[half + 1:] = A[half:]
for i in range(half, 1, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b[:]):
    if b_ == 1:
        print(i, end=" ")

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

b = [0] * (N + 1)
half = int(N / 2)
b[half:] = A[half - 1:]
for i in range(N, 0, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b):
    if b_ == 1:
        print(i, end=" ")

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

b = [0] * (N + 1)
half = int(N / 2)
b[half:] = A[half - 1:]
for i in range(N, 0, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b):
    if b_ == 1:
        print(i, end=" ")
Problem p02995 (python)

Fixed submission:

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

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

A, B, C, D = tuple(map(int, input().split()))

s = -1
c = C * (A // C + 1)
if A % C == 0:
    c = A
if c <= B:
    s += (B - c) // C + 1
        
d = D * (A // D + 1)
if A % D == 0:
    d = A
if d <= B:
    s += (B - d) // D + 1
    
cd_lcm = lcm(C, D)
cdl = cd_lcm * (A // cd_lcm + 1)
if A % cd_lcm == 0:
    cdl = A
if cdl <= B:
    s -= (B - cdl) // cd_lcm + 1

print(B - A - s)

Buggy submission (verdict: Runtime Error):

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

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

A, B, C, D = tuple(map(int, input().split()))

s = -1
c = C * (A // C + 1)
if c <= B:
    s += (B - c) // C + 1
        
d = D * (A // D + 1)
if d <= B:
    s += (B - d) // D + 1
    
cd_lcm = lcm(C, D)
cdl = cd_lcm * (A // cd_lcm + 1)
if cdl <= B:
    s -= (B - cdl) // cd_lcm + 1

print(B - A - s)

Buggy submission (verdict: Runtime Error):
import math

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

A, B, C, D = tuple(map(int, input().split()))

s = -1
c = C * (A // C + 1)
if c <= B:
    s += (B - c) // C + 1
        
d = D * (A // D + 1)
if d <= B:
    s += (B - d) // D + 1
    
cd_lcm = lcm(C, D)
cdl = cd_lcm * (A // cd_lcm + 1)
if cdl <= B:
    s -= (B - cdl) // cd_lcm + 1

print(B - A - s)
Problem p03000 (python)

Fixed submission:
LI = lambda: list(map(int, input().split()))

N, X = LI()
L = LI()


def main():
    ans = 1
    d = 0
    for l in L:
        d += l
        if d > X:
            break
        ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
LI = lambda: list(map(int, input().split()))

N, X = LI()
L = LI()


def main():
    ans = X // L
    print(ans)


if __name__ == "__main__":
    main()
Problem p03005 (python)

Fixed submission:
(N, K) = list(map(int, input().split()))
max_distribution = N - K
if K == 1:
    max_distribution = 0
print(max_distribution)

Buggy submission (verdict: Runtime Error):
x = input()
(N, K) = (int(x[0]), int(x[2]))
max_distribution = N - K
if K == 1:
    max_distribution = 0
print(max_distribution)
Problem p03006 (python)

Fixed submission:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
if N == 1:
    print(1)
else:
    d_list = [(i[0] - j[0], i[1] - j[1]) for i in xy for j in xy if i != j]
    items = list(set(d_list))
    s = 1
    for item in items:
        c = d_list.count(item)
        if c > s:
            s = c
    print(N - s)

Buggy submission (verdict: Runtime Error):
x = input()
(N, K) = (int(x[0]), int(x[2]))
max_distribution = N - K
if K == 1:
    max_distribution = 0
print(max_distribution)
Problem p03007 (python)

Fixed submission:
def successive_subtraction(N, A, i=1, l=[]):
    mx = max(A)
    mn = min(A)
    if i == N - 1:
        print(mx - mn)
        return l
    l.append((mn, mx))
    A.remove(mn)
    A.remove(mx)
    A.append(mn - mx)
    return successive_subtraction(N, A, i + 1, l)

N = int(input())
A = [int(e) for e in input().split()]
A.sort()
l = []
for i in range(N - 2):
    (a, b, c) = (A[0], A[1], A[-1])
    if b < 0:
        l.append((c, a))
        A[-1] = c - a
    else:
        l.append((a, b))
        A[1] = a - b
    A.pop(0)
print(A[1] - A[0])
l.append((A[1], A[0]))
for v in l:
    print(v[0], v[1])

Buggy submission (verdict: Runtime Error):
def successive_subtraction(N, A, i=1, l=[]):
    mx = max(A)
    mn = min(A)
    if i == N - 1:
        print(mx - mn)
        return l
    l.append((mn, mx))
    A.remove(mn)
    A.remove(mx)
    A.append(mn - mx)
    return successive_subtraction(N, A, i + 1, l)

N = int(input())
A = list(map(int, input().split()))
l = successive_subtraction(N, A)
for v in l:
    print(v[0], v[1])
Problem p03032 (python)

Fixed submission:
from bisect import insort_right as ir

N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = [0]

def right(x, k, l, lim):
    if lim > k:
        lim = k
    for vr in V[::-1][:lim]:
        k -= 1
        ir(l, vr)
        if vr <= 0:
            x += 1
        ans.append(sum(l[min(k, x):]))    

x1, k1, l1, lim1 = 0, K, [], N
if lim1 > K:
    lim1 = K
right(0, K, [], N - 1)
for vl in V[:lim1]:
    k1 -= 1
    ir(l1, vl)
    if vl <= 0:
        x1 += 1
    ans.append(sum(l1[min(k1, x1):]))
    x2, k2, l2, lim2 = x1, k1, l1[:], N + k1 - K
    right(x2, k2, l2, lim2)
ans.append(sum(l1[min(k1, x1):]))
print(max(ans))

Buggy submission (verdict: Runtime Error):
import heapq

N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = []

x1, k1, l1, lim1 = 0, K, [], N
if lim1 > K:
    lim1 = K
lim1 += 1
for i in range(lim1):
    ans.append(sum(l1[min(k1, x1):]))
    x2, k2, l2, lim2 = x1, k1, l1[:], N - i
    if lim2 > k2:
        lim2 = k2 + 1
    for vr in V[:-lim2:-1]:
        k2 -= 1
        heapq.heappush(l2, vr)
        if vr <= 0:
            x2 += 1
        ans.append(sum(l2[min(k2, x2):]))
    vl = V[i]
    k1 -= 1
    heapq.heappush(l1, vl)
    if vl <= 0:
        x1 += 1
print(max(ans))
Problem p03037 (python)

Fixed submission:
N, M = list(map(int, input().split()))
L, R = [None] * M, [None] * M
for i in range(M):
    L[i], R[i] = list(map(int, input().split()))

l = max(L)
r = min(R)
ans = r - l + 1
if ans < 0:
    ans = 0
print(ans)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
L, R = [], []
for i in range(M):
    L[i], R[i] = list(map(int, input().split()))

ans = min(R) - max(L) + 1
if ans < 0:
    ans = 0
print(ans)
Problem p03166 (python)

Fixed submission:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
XY = [LI() for _ in range(M)]

w = [None] * N
links = [[] for _ in range(N)]
visit = [False] * N


def create_links():
    for x, y in XY:
        links[x - 1].append(y - 1)


def dfs(u):
    visit[u] = True
    n = 0
    for v in links[u]:
        if not visit[v]:
            w[v] = dfs(v)
        n = max(n, w[v])
    return n + 1


def main():
    create_links()
    for i in range(N):
        if not visit[i]:
            w[i] = dfs(i)
    ans = max(w) - 1
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
XY = [LI() for _ in range(M)]

w = [None] * N
links = [[] for _ in range(N)]
visit = [False] * N


def create_links():
    for x, y in XY:
        links[x - 1].append(y - 1)


def dfs(u):
    visit[u] = True
    n = 0
    for v in links[u]:
        if not visit[v]:
            w[v] = dfs(v)
        n = max(n, w[v])
    return n + 1


def main():
    create_links()
    for i in range(N):
        if not visit[i]:
            w[i] = dfs(i)
    ans = max(w) - 1
    print(ans)


if __name__ == "__main__":
    main()
Problem p03362 (python)

Fixed submission:
N = int(input())

MAX = 55555


def create_prime_list(n):
    if n < 2:
        return []
    prime_list = [2]
    x = 3
    while x <= n:
        flag = False
        for p in prime_list:
            if x < p ** 2:
                flag = True
                break
            if x % p == 0:
                break
        if flag:
            prime_list.append(x)
        x += 2
    return prime_list


def main():
    prime_list = create_prime_list(MAX)
    w = [x for x in prime_list if x % 5 == 1]
    print(*w[:N])
    

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
N = int(input())

MAX = 55555 * 5


def create_prime_list(n):
    if n < 2:
        return []
    prime_list = [2]
    x = 3
    while x <= n:
        flag = False
        for p in prime_list:
            if x < p ** 2:
                flag = True
                break
            if x % p == 0:
                break
        if flag:
            prime_list.append(x)
        x += 2
    return prime_list


def main():
    prime_list = create_prime_list(MAX)
    prime_set = set(prime_list)
    w = [[] for _ in range(6)]
    w[0].append(0)
    l = []
    i = 0
    while i < 5:
        p = prime_list[i]
        i += 1
        l.append(p)
        for j in range(3, -1, -1):
            for x in w[j]:
                w[j + 1].append(x + p)
    
    while len(l) < N:
        p = prime_list[i]
        i += 1
        flag = True
        for x in w[4]:
            if x + p in prime_set:
                flag = False
                break
        if flag:
            l.append(p)
            for j in range(3, -1, -1):
                for x in w[j]:
                    w[j + 1].append(x + p)
    
    print(*l)
    

if __name__ == "__main__":
    main()
Problem p03452 (python)

Fixed submission:
#!python3

import sys
sys.setrecursionlimit(200000)


# input
N, M = list(map(int, input().split()))
LRD = [tuple(map(int, input().split())) for _ in range(M)]


def judge(W, D, visit, i):
    visit[i] = True
    for j, d in W[i]:
        if D[j] is None:
            D[j] = D[i] + d
        else:
            if D[i] + d != D[j]:
                return True
        if visit[j]:
            continue
        if judge(W, D, visit, j):
            return True
    
    return False


def main():
    W = [[] for _ in range(N)]
    for l, r, d in LRD:
        W[l - 1].append((r - 1, d))
        W[r - 1].append((l - 1, -d))
    
    D = [None] * N
    visit = [False] * N
    for i in range(N):
        if visit[i]:
            continue
        D[i] = 0
        if judge(W, D, visit, i):
            print("No")
            return
    
    print("Yes")


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!python3

# input
N, M = list(map(int, input().split()))
LRD = [tuple(map(int, input().split())) for _ in range(M)]


def judge(W, D, visit, i):
    visit[i] = True
    for j, d in W[i]:
        if D[j] is None:
            D[j] = D[i] + d
        else:
            if D[i] + d != D[j]:
                return True
        if visit[j]:
            continue
        if judge(W, D, visit, j):
            return True
    
    return False


def main():
    W = [[] for _ in range(N)]
    for l, r, d in LRD:
        W[l - 1].append((r - 1, d))
        W[r - 1].append((l - 1, -d))
    
    D = [None] * N
    visit = [False] * N
    for i in range(N):
        if visit[i]:
            continue
        D[i] = 0
        if judge(W, D, visit, i):
            print("No")
            return
    
    print("Yes")


if __name__ == "__main__":
    main()
Problem p03676 (python)

Fixed submission:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
A = LI()

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 5
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = -inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def main():
    comb_init()
    d = {i: [] for i in range(1, N + 1)}
    x, y = [None] * 2
    for i in range(N + 1):
        d[A[i]].append(i)
        if len(d[A[i]]) == 2:
            x, y = d[A[i]]
            break
    
    for i in range(1, N + 2):
        ans = comb(N + 1, i)
        ans -= comb(N + x - y, i - 1)
        ans %= MOD
        print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
A = LI()

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 1
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = -inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def main():
    comb_init()
    d = {i: [] for i in range(1, N + 1)}
    x, y = [None] * 2
    for i in range(N + 1):
        d[A[i]].append(i)
        if len(d[A[i]]) == 2:
            x, y = d[A[i]]
            break
    
    for i in range(1, N + 2):
        ans = comb(N + 1, i)
        ans -= comb(N + x - y, i - 1)
        ans %= MOD
        print(ans)


if __name__ == "__main__":
    main()
Problem p02630 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
xy = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*xy)]

ans = 0

sum_all = 0
for cnt in range(n):
    sum_all += a[cnt]

a = sorted(a)
list_a_num = [0]*(10**5 + 1)
for cnt in range(n):
    list_a_num[a[cnt]] += 1

for cnt in range(q):
    sum_all += (c[cnt] - b[cnt]) * list_a_num[b[cnt]]
    list_a_num[c[cnt]] += list_a_num[b[cnt]]
    list_a_num[b[cnt]] = 0
    print(sum_all)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
q = int(input())
xy = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*xy)]

stuck_b = []
stuck_c = []
stuck_sum = []

sum = 0

for cnt_q in range(q):
    sum = 0
    if stuck_b[cnt_q] == b[cnt_q] and stuck_c[cnt_q] == c[cnt_q]:
        print(stuck_sum[cnt_q])
    else:
        for cnt_n in range(n):
            if a[cnt_n] == b[cnt_q]:
                a[cnt_n] = c[cnt_q]
        for num in range(n):
            sum += a[num]
        print(sum)
Problem p02536 (python)

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())
uf = UnionFind(N)

#H = list(map(int, input().split()))

#AB = [tuple(map(int, input().split())) for i in range(M)]

#丸暗記。隣接リストの初期化
graph = [[] for _ in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)

print(uf.group_count()-1)

Buggy 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())
uf = UnionFind(N)

#H = list(map(int, input().split()))

#AB = [tuple(map(int, input().split())) for i in range(M)]

#丸暗記。隣接リストの初期化
graph = [[] for _ in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  uf.union(a, b)

print(uf.group_count()-1)