Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from math import ceil as C, floor as F, gcd as G, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data)

  
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_ = I()
xs = list(S())

rs, gs, bs = [], [], []
for i, x in enumerate(xs, 1):
    if x == 'R':
        rs.append(i)
    if x == 'G':
        gs.append(i)
    if x == 'B':
        bs.append(i)

ans = 0
seen = D(lambda: False)
s = sorted([rs, gs, bs], key=lambda x: len(x))
for a in s[0]:
    for b in s[1]:
        ans += len(s[2])

        if a < b:
            i, j = a, b
        else:
            j, i = a, b

        if i - (j-i) in s[2]:
            if not seen[(i - (j-i), i, j)]:
                ans -= 1
                seen[(i - (j-i), i, j)] = True
        if j + (j-i) in s[2]:
            if not seen[(i, j, j+(j-i))]:
                ans -= 1
                seen[(i, j, j+(j-i))] = True
        if (i+j)/2 in s[2]:
            if not seen[(i, (i+j)/2, j)]:
                ans -= 1
                seen[(i, (i+j)/2, j)] = True

print(ans)

### FIXED CODE ###

import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ
from operator import mul

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def prod(list): return R(mul, list, 1)
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n = I()
rgb = S()

cnt = CNT(list(rgb))
ans = prod([cnt[c] for c in ['R', 'G', 'B']])

for i, r in enumerate(rgb):
    for j, g in enumerate(rgb[i+1:], start=i+1):
        k = j + (j - i)
        if k < len(rgb):
            if r != g and g != rgb[k] and r != rgb[k]:
                ans -= 1

print(ans)
### BUGGY CODE ###

N=int(input())
S=list(input())
ans=0
R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i)
    elif S[i]=="G":
        G.append(i)
    else:
        B.append(i)
for r in R:
    for g in G:
        for b in B:
            a=r+g+b
            e=max(r,g,b)
            d=min(r,g,b)
            c=a-e-d
            if e-c!=c-d:
                ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())
ans=0
R=0
G=0
B=0
for i in range(N):
    if S[i]=="R":
        R=R+1
    elif S[i]=="G":
        G=G+1
    else:
        B=B+1
ans=R*G*B
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k=2*j-i
            if N<=k:
                continue
            if S[i]!=S[k] and S[k]!=S[j]:
                ans=ans-1
print(ans)
### BUGGY CODE ###

n, k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
d={i:a.count(i) for i in set(a)}
p=len(d)-k
l=[]
for i in range(p):
  t=list(d.items())[0]
  for j in d.items():
    if t[1]>j[1]:
      t=j
  l.append(t[1])
  d.pop(t[0], None)
if p>0: print(sum(l))
else: print("0")


### FIXED CODE ###

n, k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
d={i:0 for i in set(a)}
for i in a: d[i]+=1
print(n-sum([t[1] for t in sorted(d.items(), key=lambda x:-x[1])][:k]))
### BUGGY CODE ###

import numpy as np
a = list(map(int,input().split()))
N = a[0]
K = a[1]
b = list(map(int,input().split()))
li = list(set(b))
c = np.array(b)
d = np.array([])
h = len(li) -K
Num = 0
if K >= len(li):
  print(0)
  exit()
for i in li :
  ind = c[np.where(c== i)]
  d = np.append(d,ind.shape)
d = np.sort(d)
for i in range(h):
  Num += d[i]
print(int(Num))

### FIXED CODE ###

import numpy as np
from collections import Counter
import collections
a = list(map(int,input().split()))
N = a[0]
K = a[1]
d = np.array([])
b = list(map(int,input().split()))
li = list(set(b))
c = np.array(b)
l = Counter(b)
h = len(li) -K
Num = 0
if K >= len(li):
  print(0)
  exit()
d = np.append(d,list(l.values()))
d = np.sort(d)
for i in range(h):
  Num += d[i]
print(int(Num))
### BUGGY CODE ###

# vim: set fileencoding=utf-8 :
x, y = map(int, raw_input().split())

if x == y:
    print(-1)
    exit()

n = 1
top = pow(10, 18)

while True:
    t = n * x
    if t >= top:
        print(-1)
        break

    if t % y != 0:
        print(t)
        break

    n += 1


### FIXED CODE ###

# vim: set fileencoding=utf-8 :
x, y = map(int, raw_input().split())

if x % y == 0:
    print(-1)
    exit()

n = 1
top = pow(10, 18)

while True:
    t = n * x
    if t >= top:
        print(-1)
        break

    if t % y != 0:
        print(t)
        break

    n += 1
### BUGGY CODE ###

from fractions import gcd
import functools
a,b=map(int,input().split())

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

def is_prime(q):
  q = abs(q)
  if q == 2: return True
  if q < 2 or q&1 == 0: return False
  return pow(2, q-1, q) == 1

frac=cf(a,b)
n=len(frac)
ans=0
for i in range(n):
  if is_prime(frac[i]):
    ans+=1
print(ans+1)

### FIXED CODE ###

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

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors

import random

def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True
  
div=list(set(make_divisors(a))&set(make_divisors(b)))
n=len(div)
ans=0
for i in range(n):
  if is_prime(div[i]):
    ans+=1
print(ans+1)
### BUGGY CODE ###

n=int(input())
a=list(input().split())
ans=1
f=0
i=0
while(i<n):
    if i==n-1:
        ans=ans*int(a[i])
    else:
        ans=ans*int(a[i])*int(a[i+1])
    if f==0 and ans>1000000000000000000:
        f=1
    if ans==0:
        print(0)
        exit()
    i+=2
if f==1:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

n=int(input())
a=list(input().split())
ans=1
f=0
i=0
while(i<n):
    if f==0:
        ans=ans*int(a[i])
    if f==0 and ans>1000000000000000000:
        f=1
    if int(a[i])==0:
        print(0)
        exit()
    i+=1
if f==1:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

At,Ba,K = (int(x) for x in input().split())

for i in range(K):
    if At >= 1:
        At -= 1
    elif Ba >= 1:
        Ba -= 1
    
print(At)
print(Ba)

### FIXED CODE ###

At,Ba,K = (int(x) for x in input().split())

if K <= At:
    print(At - K)
    print(Ba)
elif K <= At + Ba:
    print(0)
    print(Ba - (K - At))
else :
    print(0)
    print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
d=[INF]*(W+2)*(H+2)
direction=[[0]*4 for _ in range((H+2)*(W+2))]
d[st]=0
di=(-1,1,W+2,-(W+2))

def main():
    for i in range(H):
        c.extend(['@']+list(input())+['@'])
    c.extend(['@']*(W+2))
    que=deque()
    que.append(st)
    while que:
        v=que.popleft()
        for k in range(4):
            nv=v+di[k]
            if c[nv]=='.':
                if direction[v][k]>0:
                    if d[nv]>d[v]:
                        direction[nv]=[0]*4
                        direction[nv][k]=direction[v][k]-1
                        d[nv]=d[v]
                        que.append(nv)
                    elif d[nv]==d[v]:
                        direction[nv][k]=direction[v][k]-1
                else:
                    if d[nv]>d[v]+1:
                        direction[nv]=[0]*4
                        direction[nv][k]=K-1
                        d[nv]=d[v]+1
                        que.append(nv)
                    elif d[nv]==d[v]+1:
                        direction[nv][k]=K-1
    print(d[gl] if d[gl]!=INF else -1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
for i in range(H):
    c.extend(['@']+list(input())+['@'])
c.extend(['@']*(W+2))
que=deque()
dist=[INF]*(W+2)*(H+2)
que.append(st)
dist[st]=0
d=(-1,1,W+2,-(W+2))
while que:
    v=que.popleft()
    for k in range(4):
        nv=v
        for _ in range(K):
            nv+=+d[k]
            if c[nv]=='.' and dist[nv]>dist[v]:
                if dist[nv]==INF:
                    dist[nv]=dist[v]+1
                    que.append(nv)
            else:
                break
print(dist[gl] if dist[gl]!=INF else -1)
### BUGGY CODE ###


n,a=map(int,input().split())
x=list(map(int,input().split()))

#n=4
#a=8
#x=[7,9,8,9]

#n=8
#a=5
#x=[3,6,2,8,7,6,5,9]

for i in range(n):
    x[i]=x[i]-a
    
n2=n//2
n3=n-n2

y=[]
for i in range(n3):
    y.append(x[i+n2])

xsum=dict()
for i in range(2 ** n2):
    isum=0
    for j in range(n2):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            isum=isum+x[j]
    if isum in xsum:
        xsum[isum]=xsum[isum]+1
    else:
        xsum[isum]=1
#print(xsum)        
    
icnt=0
for i in range(2 ** n3):
    isum=0
    for j in range(n3):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            isum=isum+y[j]
#    print(isum)
    for xs in xsum.items():
        if xs[0]==-isum:
            icnt=icnt+(xs[1])
#            print(isum,xs[1],(xs[1]),icnt)

print(icnt-1)


### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))

for i in range(n):
    x[i]=x[i]-a
    
nx=n*n
dp=[[0]*(2*nx+1) for i in range(n+1)]

#print(dp)

dp[0][nx]=1

for j in range(1,n+1):
    jj=j-1
    for t in range(2*nx+1):
        if t-x[jj]<0 or 2*nx<t-x[jj]:
            dp[j][t]=dp[j-1][t]
        elif 0<t-x[jj] and  t-x[jj]<2*nx:
            dp[j][t]=dp[j-1][t]+dp[j-1][t-x[jj]]
        else:
            dp[j][t]=0

print(dp[n][nx]-1)
### BUGGY CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
l=[1]*(2*10**5+2)
for i in range(1,2*10**5+1):
    l[i]=l[i%str(bin(i)).count("1")]+1
for i in range(n):
    p=1
    if x[i]=="1":
        p=-1
    if (c+p)==0:
        print(0)
        continue
    nex=(m+p*(2**(n-i-1)))%(c+p)
    if nex==0:
        print(1)
    else:
        print(l[nex])

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
l=[1]*(2*10**5+2)
for i in range(1,2*10**5+1):
    l[i]=l[i%str(bin(i)).count("1")]+1
deka=0
for i in range(n):
    if x[i]=="1":
        deka+=pow(2,n-i-1,c+1)
        deka%=c+1
tiisa=0
if c!=1:
    for i in range(n):
        if x[i]=="1":
            tiisa+=pow(2,n-i-1,c-1)
            tiisa%=c-1

for i in range(n):
    if x[i]=="0":
        nex=(deka+pow(2,n-i-1,c+1))%(c+1)
    else:
        if c-1==0:
            nex=-1
        else:
            nex=(tiisa-pow(2,n-i-1,c-1))%(c-1)
    if nex==0:
        print(1)
    elif nex==-1:
        print(0)
    else:
        print(l[nex])
### BUGGY CODE ###

import bisect

N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
Price_List.sort()
for i in range(M):
    New_Price = Price_List.pop(-1)
    Price_List.insert(bisect.bisect(Price_List,New_Price//2),New_Price//2)
print(sum(Price_List))


### FIXED CODE ###

import bisect
 
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
Price_List.sort()
for i in range(M):
    New_Price = Price_List.pop(-1)//2
    Price_List.insert(bisect.bisect(Price_List,New_Price),New_Price)
print(sum(Price_List))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

n = int(readline())
x = list(map(int, readline().split()))
memo = sorted(x)
for xx in x:
    dx = deepcopy(memo)
    dx.remove(xx)
    if n % 2 == 0:
        print(dx[(n - 1) // 2])
    else:
        print((dx[(n - 1) // 2] + dx[(n - 1) // 2 - 1]) / 2)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
x = list(map(int, input().split()))
sort_x = sorted(x)
check = sort_x[n//2]
for i in range(n):
    if check <= x[i]:
        ans = sort_x[n//2-1]
    else:
        ans = check
    print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
up = [[0 for i in range(w)] for j in range(h)]
down = [[0 for i in range(w)] for j in range(h)]
right = [[0 for i in range(w)] for j in range(h)]
left = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    # init up
    if grid[0][i] == ".":
        up[0][i] = 1
    else:
        up[0][i] = 0
    #init down
    if grid[-1][i] == ".":
        down[-1][i] = 1
    else:
        down[-1][i] = 0
for i in range(h):
    #init right
    if grid[i][-1] == ".":
        right[i][-1] = 1
    else:
        right[i][-1] = 0
    
    #init left
    if grid[i][0] == ".":
        left[i][0] = 1
    else:
        left[i][0] = 0
for i in range(h):
    for j in range(1,w):
        if grid[i][j] == ".":
            left[i][j] = left[i][j-1] + 1
        else:
            left[i][j] = 0
for i in range(h):
    for j in range(w-2,-1,-1):
        if grid[i][j] == ".":
            right[i][j] = right[i][j+1] + 1
        else:
            right[i][j] = 0

for i in range(1,h):
    for j in range(w):
        if grid[i][j] == ".":
            up[i][j] = up[i-1][j] + 1
        else:
            up[i][j] = 0
for i in range(h-2,-1,-1):
    for j in range(w):
        if grid[i][j] == ".":
            down[i][j] = down[i+1][j] + 1
        else:
            down[i][j] = 0
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, up[i][j] + down[i][j] + left[i][j] + right[i][j] - 3)
print(ans)

### FIXED CODE ###

h, w = map(int,input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
L = [[0 for i in range(w)] for j in range(h)]
R = [[0 for i in range(w)] for j in range(h)]
U = [[0 for i in range(w)] for j in range(h)]
D = [[0 for i in range(w)] for j in range(h)]
#Uを決める
for i in range(w):
    if grid[0][i] == '#':
        U[0][i] = 0
    else:
        U[0][i] = 1
for i in range(1,h):
    for j in range(w):
        if grid[i][j] == '#':
            U[i][j] = 0
        else:
            U[i][j] = U[i-1][j] + 1
 #Dを決める
for i in range(w):
    if grid[-1][i] == '#':
        D[-1][i] = 0
    else:
        D[-1][i] = 1
for i in range(h-2, -1,-1):
    for j in range(w):
        if grid[i][j] == '#':
            D[i][j] = 0
        else:
            D[i][j] = D[i+1][j] + 1
# R を決める
for i in range(h):
    if grid[i][-1] == '#':
        R[i][-1] = 0
    else:
        R[i][-1] = 1
for i in range(h):
    for j in range(w-2,-1,-1):
        if grid[i][j] == '#':
            R[i][j] = 0
        else:
            R[i][j] = R[i][j+1] + 1
#Lを決める
for i in range(h):
    if grid[i][0] == '#':
        L[i][0] = 0
    else:
        L[i][0] = 1
for i in range(h):
    for j in range(1,w):
        if grid[i][j] == '#':
            L[i][j] = 0
        else:
            L[i][j] = L[i][j-1] + 1
ans = 0
for i in range(h):
    for j in range(w):
        #print("x:{} y:{} L:{} R:{} U:{} D:{}".format(j+1,i+1,L[i][j],R[i][j],U[i][j],D[i][j]))
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
keys=[]
values=[]
for i in A:
  if i in keys:
    pass
  else:
    counts=A.count(i)
    keys.append(i)
    values.append(counts)
ans=0
for j in values:
  ans+=j*(j-1)/2
for k in A:
  a=keys.index(k)
  print(int(ans-values[a]+1))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in A:
  if i not in dic.keys():
    dic.update({i:1})
  else:
    dic[i]+=1
ans=sum([int(j*(j-1)/2) for j in dic.values()])
for k in A:
  num=dic[k]
  if num>=1:
    print(int(ans-num+1))
  else:
    print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
S = input()

sum = 0
for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if j - i != k - j:
                if (S[i] != S[j]) and (S[i] != S[k] and S[j] != S[k]):
                    sum += 1

print(sum)


### FIXED CODE ###

import itertools
from collections import Counter

N = int(input())
S = input()

C=Counter(S)
r = C['R']
g = C['G']
b = C['B']


cnt = r * g * b

for i in range(0,N-2):
    for j in range(i,N-1):
        k = j + j - i
        if k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                cnt -= 1

print(cnt)
### BUGGY CODE ###

import math

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

if a > b:
    a, b = b, a

# a_sq = int(math.sqrt(a)) + 1

com_div = []
# for i in range(1, a_sq + 1):
for i in range(1, a):
    if a % i == 0 and b % i == 0:
        com_div.append(i)
if len(com_div) == 1:
    print(1)
    exit()
    
ans = [1]
for i in range(1, len(com_div)):
    flg = 0
    for j in range(1, i):
        if com_div[i] % com_div[j] == 0:
            flg = 1
            break
    if flg == 0:
        ans.append(com_div[i])
print(len(ans))

### FIXED CODE ###

import math

a, b = map(int, input().split())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
ab_gcd = gcd(a, b)

gcd_sq = int(math.sqrt(ab_gcd) + 1)

ans = []
curr_num = ab_gcd
for i in range(2, gcd_sq):
    if curr_num % i != 0:
        continue
    cnt = 0
    while curr_num % i == 0:
        curr_num = curr_num // i
        cnt += 1
    ans.append([i, cnt])
if curr_num != 1:
    ans.append([curr_num, 1])
print(len(ans) + 1)
### BUGGY CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)

for i in range(m):
  a, b = map(int, input().split())
  linked[a].add(a)
  linked[b].add(b)
  linked[a] |= linked[b]

  linked[b] = linked[a]
  for t in linked[b]:
    linked[t] = linked[a]
all = set()
groups = set()
for s in linked.values():
  if s:
    groups.add(tuple(s))
    all |= s
    s.clear()
print((n - len(all)) + (len(groups) - 1))


### FIXED CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(list)
i2group = dict()

gid = n + 1
def get_root(i):
  if i not in linked:
    return i
  j = get_root(linked[i])
  linked[i] = j
  return j

def get_groups():
  return [get_root(i) for i in range(1, n + 1)]

for i in range(m):
  a, b = map(int, input().split())
  ra, rb = get_root(a), get_root(b)
  if ra == rb: continue
  linked[ra] = gid
  linked[rb] = gid
  gid += 1

g = get_groups()
print(len(set(g)) - 1)
exit()

n_connected = 0
n_group = 0
for s in linked.values():
  s = s[0]
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))
### BUGGY CODE ###

N,M = map(int,input().split())
cnt = 0
while N >= 0 or M > 1:
    if N >= 1:
        if M >= 2:
            M -= 2
            N -= 1
            cnt += 1
        else:
            print(cnt)
            exit()
    else:
        if M >= 4:
            M -= 4
            cnt += 1
        else:
            print(cnt)
            exit()

### FIXED CODE ###

N,M = map(int,input().split())
cnt = 0

m = int(M/2)

if N >= m:
    cnt = m
elif m > N:
    cnt = N
    M -= 2*N
    cnt += int(M/4)

print(cnt)
### BUGGY CODE ###

def BinSearch(A, hi, lo):
    b = (hi + lo) // 2
    tmp0 = FindAns(A, b - 1)
    tmp1 = FindAns(A, b)
    tmp2 = FindAns(A, b + 1)
    if hi == lo:
        return min(tmp0, tmp1, tmp2)
    if tmp0 < tmp1:
        return BinSearch(A, b - 1, lo)
    else:
        return BinSearch(A, hi, lo + 1)
    
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

from bisect import  bisect_left as bl
n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1
    
hi = max(A)
lo = min(A)

print(BinSearch(A, hi, lo))

### FIXED CODE ###

def BinSearch(A, hi, lo):
    b = (hi + lo) // 2
    tmp0 = FindAns(A, b - 1)
    tmp1 = FindAns(A, b)
    if hi == lo:
        tmp2 = FindAns(A, b + 1)
        return min(tmp0, tmp1, tmp2)
    if tmp0 < tmp1:
        return BinSearch(A, b - 1, lo)
    else:
        return BinSearch(A, hi, b + 1)
    
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1
    
hi = max(A)
lo = min(A)

print(BinSearch(A, hi, lo))
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*number):
    return reduce(math.gcd, number)
n = int(input())
a, b, c = 1, 1, 1
sum = 0
while True:
    sum += gcd(a, b, c)
    if n > c:
        c += 1
    elif n == c and n == b and n == a:
        break
    elif n == c and n == b:
        a += 1
        b = 1
        c = 1
    elif n == c:
        b += 1
        c = 1
print(sum)

### FIXED CODE ###

from math import gcd
n = int(input())
sum = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd(gcd(i, j), k)
print(sum)
### BUGGY CODE ###


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

num = 1
result = 1

for i in range(p):

    compare = num ** n

    if compare > p:
        break

    if p % compare == 0:
        result = num

    num += 1

print(result)



### FIXED CODE ###

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

pp = p
# 2のべき乗チェック
count_2 = 0
while True:
    if pp % 2 == 0:
        pp = pp / 2
        count_2 += 1
    else:
        break


result = 2 ** (count_2 // n)

p = p / (2 ** count_2)

kisu = True if p / 2 != 0 else False

num2 = int(p ** (1/n)) + 1
if kisu:
    num2 = num2 - 1 if num2 % 2 == 0 else num2
else:
    num2 = num2 - 1 if num2 % 2 != 0 else num2


for i in range(num2, 1, -2):
    if p % (i ** n) == 0:
        print(result * i)
        break

else:
    print(result * 1)