Harryxun/stf_run huggingface dataset:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)

if not (a==wf).all() :
    print(-1)
    exit()


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
wf=[list(map(int,input().split())) for i in range(n)]

ans=0
for i in range(n):
    for j in range(i+1,n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] > wf[i][h]+wf[h][j]:
                print(-1)
                exit()
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans))
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
a = LI()
c = list(Counter(a).items())
x = len(c)
H = []
for i,j in c:
    heappush(H,j)
for k in range(1,n+1):
    if k == 1:
        print(n)
        continue
    h = H.copy()
    x = len(h)
    if k > x:
        print(0)
        continue
    ans = 0
    while x >= k:
        ans += 1
        tmp = heappop(h)
        lst = []
        x -= 1
        for _ in range(k-1):
            s = heappop(h)
            s -= tmp
            if s == 0:
                x -= 1
                continue
            lst.append(s)
        for i in lst:
            heappush(h,i)
    print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
"""
.2分探索を考える
.各kに対してx回以上抜き出せるかという問いを考える
.各数の個数を数えて数iの個数をCiとする
.各数iを抜き出せるのはCiまで
 ⇒各数を抜き出す回数min(Ci,x)
.Σmin(Ci,x)はkx以上でなければいけない(k個x回抜き出すため)
.これを満たすときx回抜き出せる
.このままではO(n^2(logn))なので工夫する
.Σ(min(Ci,x))はk依存でないのでここを工夫する(Σ(min(Ci,x))をSxとする)
.SxはSx-1と比べてx以上のCiの数だけ増える(x以上のCiの数をDxとする)
.Sx := Sx-1 + Dx
.Dxを求める時はCのリストについてbisectを行う。
.Sx >= k*xとなるxの最大値を2分探索で求める。(O(nlogn))
"""
n = I()
a = LI()
cnt = list(Counter(a).values())
cnt.sort()
m = len(cnt)
S = [0]*(n+1)
for x in range(1,n+1):
    l = bl(cnt,x)
    S[x] = S[x-1] + (m-l)
for k in range(1,n+1):
    high,low = n+1,0
    while high - low > 1:
        mid = (high + low)//2
        if S[mid] >= k*mid:
            low = mid
        else:
            high = mid
    print(low)
N = input()
L = [int(e) for e in input().split()]
c = 0
for i in range(N):
  for j in range(i, N):
    for k in range(j, N):
      if L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
        if L[i] < L[j] + L[k] or L[j] > L[k] + L[i] or L[k] > L[i] + L[j]:
          c += 1
print(c)

### FIXED CODE ###

N = int(input())
L = [int(e) for e in input().split()]
c = 0

if len(set(L)) >= 3:
  for i in range(N-2):
    for j in range(i+1, N-1):
      for k in range(j+1, N):
        if L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
          if L[i] < L[j] + L[k] and L[j] < L[k] + L[i] and L[k] < L[i] + L[j]:
            c += 1
print(c)
def gcd(a,b):
    if a<b:
        a,b = b,a
    while b:
        a,b = b,a%b
    return a

N = int(input())
A = list(map(int,input().split()))
def L(i):
    if i == 0 or i == 1:
        return 0
    else:
        return(gcd(L(i-1),A[i-2]))
def R(i):
    if i == N+1:
        return 0
    else:
        return(gcd(R(i+1),A[i-1]))
gcd_max = 0
for i in range(1,N+1):
    gcd_max = max(gcd_max,gcd(L(i),R(i+1)))
print(gcd_max)

### FIXED CODE ###

def gcd(x,y):
    while y != 0:
        x,y = y,x%y
    return x
n = int(input())
a = list(map(int,input().split()))

L,R = [0],[0]
for i in range(1,n+1): #L[i]は左i個,R[i]は右i個
    L.append(gcd(L[-1],a[i-1]))
    R.append(gcd(R[-1],a[n-i]))
print(max(gcd(L[i],R[n-i-1]) for i in range(n)))
a, b, c, d = map(int, input().split())
print(min(a, b) + min(c, d))

### FIXED CODE ###

a, b, c, d = map(int, open(0))
print(min(a, b) + min(c, d))
#nyuuryoku
food=[]
for i in range (5):
  food.append(int(input()))
time = 0

#1keta toru 10 watte amari dasu
#amari wo dasu
machi = []
for i in range (5):
  if food[i]%10 == 0:
    time += food[i]
  else:
    time += food[i]+(10-(food[i]%10))
    machi.append(10-(food[i]%10)) 
    
print(time-max(machi))  
    

### FIXED CODE ###

#nyuuryoku
food=[]
for i in range (5):
  food.append(int(input()))
time = 0

#1keta toru 10 watte amari dasu
#amari wo dasu
machi = []
for i in range (5):
  if food[i]%10 == 0:
    time += food[i]
  else:
    time += food[i]+(10-(food[i]%10))
    machi.append(10-(food[i]%10)) 

if len(machi) == 0:
  print(time)
else:
  print(time-max(machi))
import math
a,b=map(str,input().split())
a=int(a)
b=float(b)

#x=int(a*b)
x=math.floor(a*b)
print(x)

### FIXED CODE ###

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

x=a[0]

if 0 not in a:
    for i in range (1,n):
        x=x*a[i]
        if x > pow(10,18):
            print(-1)
            exit()           
    print(x)         
else:
    print(0)
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
print(last)
"""if last >= N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))
"""


### FIXED CODE ###

N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if M == 1:
  print(0)
else:
  if last > N:
    print(sum(ls_mod[:N]))
  else:
    shou = (N-fast) // diff
    amari = (N-fast) % diff
    print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))
import sys
sys.setrecursionlimit(100000)

def dfs(v):
    global node_chk
    global edge_chk
    global B
    global connect
    global value

    node_chk[v] = 1
    connect[v] = value
    for x in B[v]:
        if(node_chk[x] == 0):
                dfs(x)



n,m = map(int,input().split())
B = [[]for i in range(n)] # 隣接リスト
edge_chk = [[]for i in range(n)]
node_chk = [0 for i in range(n)]
connect = [0 for i in range(n)]
value = 0

for i in range(m):
    A = list(map(int,input().split()))
    B[A[0]].append(A[1])
    B[A[1]].append(A[0])
    edge_chk[A[0]].append(0)
    edge_chk[A[1]].append(0)

for i in range(n):
    if(node_chk[i] == 1):
        continue
    dfs(i)
    value += 1


q = int(input())
for i in range(q):
    start,target = map(int,input().split())
    if(connect[start] == connect[target]):
        print("yes")
    else:
        print("no")


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

def dfs(v):
    global node_chk
    global B
    global connect
    global value

    node_chk[v] = 1
    connect[v] = value
    for x in B[v]:
        if(node_chk[x] == 0):
                dfs(x)



n,m = map(int,input().split())
B = [[]for i in range(n)] # 隣接リスト
node_chk = [0 for i in range(n)]
connect = [0 for i in range(n)]
value = 0

for i in range(m):
    A = list(map(int,input().split()))
    B[A[0]].append(A[1])
    B[A[1]].append(A[0])

for i in range(n):
    if(node_chk[i] == 1):
        continue
    dfs(i)
    value += 1


q = int(input())
for i in range(q):
    start,target = map(int,input().split())
    if(connect[start] == connect[target]):
        print("yes")
    else:
        print("no")
A,B = [int(x) for x in input().split()]
if(A%2==0 or B%2===0):
  print('No')
else:
  print('Yes')

### FIXED CODE ###

A,B = [int(x) for x in input().split()]
if(A%2==0 or B%2==0):
  print('No')
else:
  print('Yes')
d = {n: 'hon' for n in "24579"}
d.update({n: 'pon' for n in "0168"})
d.update({3: 'bon'})

print(d[input()[-1]])


### FIXED CODE ###

d = {n: 'hon' for n in "24579"}
d.update({n: 'pon' for n in "0168"})
d.update({"3": 'bon'})
 
print(d[input()[-1]])
a, b = map(int, input().split())
def kansu_return_flag(a,b):
    
    flag = 0
    if a>b:
        big = a
        small = b
    else:
        big = b
        small = a
        
    for i in range(small,big):
        a_ans = abs(big-i)
        b_ans = abs(small-i)
        if a_ans == b_ans:
            ans = i
            flag = 1
            break
    return flag,ans

flag,ans = kansu_return_flag(a,b)

if flag == 1:
    print(ans)
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

a, b = map(int, input().split())
def kansu_return_flag(a,b):
    ans = 0
    flag = 0

    if abs(a-b)%2 != 0:
        flag = 0
    else:
        ans = (a+b)/2
        flag = 1
    return flag,ans

flag,ans = kansu_return_flag(a,b)

if flag == 1:
    print(int(ans))
else:
    print('IMPOSSIBLE')
import sys

for x in stdin.sys.read().split():
    print len(str(x[0]+x[1])

### FIXED CODE ###

while True:
    try:
        a, b = map(int, raw_input().split())
        print len(str(a+b))
    except:
        break
import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
            if j!= i and a[j]==0:
                a[j]=2000
                path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


def mainasu_sycle(dist):   #負のサイクルがあるか確認する    第一引数: 重みを含む配列  実装を確認していない
    
    for i in range (0,len(dist)):
       if dist[i][i] != 0:
        print ("Negative cycle at : ", i+1)




#最短経路をたどる
def ConstructPath(p, i, j):
    i,j = int(i), int(j)
    print("i,j:",i,j)
    if(i==j):
      print (i,)
    elif(p[i][j] == -30000):
      print (i,'-',j)
    else:
      ConstructPath(p, i, p[i][j]);
      print(j,)




#フロイド・ワーシャル
def warshall_floyd(glath,path):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   path[i][j] = path[k][j]
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath,path





H, W = [int(x) for x in str(input()).split()]  #グラフの大きさ 

cost_graph,graph=make_list(10,10)
wall ,wall_graph= make_list(H,W)
    #print(cost_graph)

un_label=[]
for i in wall:
   for j in i: 
            if j !=-1 and j!=1:
                 un_label.append(j)
cost=0
 
all_cost,all_graph=warshall_floyd(cost_graph,graph)
    
   

for i in un_label:
        cost+=all_cost[i][1]

print(cost)

### FIXED CODE ###

import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath,path):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   path[i][j] = path[k][j]
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath,path





H, W = [int(x) for x in str(input()).split()]  #グラフの大きさ 

cost_graph,graph=make_list(10,10)
wall ,wall_graph= make_list(H,W)
    #print(cost_graph)

un_label=[]
for i in wall:
   for j in i: 
            if j !=-1 and j!=1:
                 un_label.append(j)
cost=0
 
all_cost,all_graph=warshall_floyd(cost_graph,graph)
    
   

for i in un_label:
        cost+=all_cost[i][1]

print(cost)
import math
def gcd(x, y):
    gcd=math.gcd(x, y)
    return gcd


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

if n==1:
    print(abs(x-a[0]))

else:
    for i in range(n):
        a[i]=abs(x-a[i])
    
    ans=gcd(a[0], a[1])

    for i in range(2, n):
        ans=gcd(ans, a[i])
    
    print(ans)

### FIXED CODE ###

import fractions
def gcd(x, y):
    gcd=fractions.gcd(x, y)
    return gcd

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

if n==1:
    print(abs(x-a[0]))

else:
    for i in range(n):
        a[i]=abs(x-a[i])
    
    ans=gcd(a[0], a[1])

    for i in range(2, n):
        ans=gcd(ans, a[i])
    
    print(ans)
#include <stdio.h>


int main()
{
int A,B,C,d;
scanf("%d %d %d",&A,&B,&C);


if (A&&B==5&&C==7)
    printf("YES\n");
else if (A&&C==5&&B==7)
    printf("YES\n");
else if(A==7&&B&&C==5)
    printf("YES\n");
else
printf("NO\n");

return 0;
}


### FIXED CODE ###

a=input().split(" ")
a=list(map(int,a))
b=a[0]*a[0]+a[1]*a[1]+a[2]*a[2]
if b==99:
    print("YES")
else :
    print("NO")
from scipy.misc import comb

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

kind = set(S)
each_char =[]

for char in kind:
    each_char.append(S.count(char))

length = len(kind)
over_stock = len(S) - len(kind)

count = 0
for i in range(over_stock + 1):
    count += (2 ** (length - i)) * comb(over_stock, i, exact=True)

print(count - 1)

### FIXED CODE ###

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

mod = 10 ** 9 + 7

kind = set(S)
each_char = []

for char in kind:
    each_char.append(S.count(char))

count = 1
for i in each_char:
    count = (count % mod) * ((i + 1) % mod) % mod

print((count - 1) % mod)
def e_friendships(N, K):
    if K > (N - 1) * (N - 2) // 2:
        return -1

    ans_edge = []
    for i in range(2, N + 1):
        ans_edge.append((1, i))  # スターの構成

    def append_edge(t, lst=[], count=0):  # t回最短距離が2の頂点を消すように辺を追加
        for i in range(2, N):
            for j in range(i + 1, N + 1):
                if count == t:
                    return lst
                lst.append((i, j))
                count += 1
        return lst

    ans_edge += append_edge((N - 1) * (N - 2) // 2 - K)
    ans = [(len(ans_edge),), *ans_edge]
    return ', '.join([' '.join(map(str, row)) for row in ans])

N, K = [int(i) for i in input().split()]
print(e_friendships(N, K))

### FIXED CODE ###

def e_friendships(N, K):
    if K > (N - 1) * (N - 2) // 2:
        return -1

    ans_graph = []
    for i in range(2, N + 1):
        ans_graph.append('{} {}'.format(1, i))  # スターの構成

    def append_edge(t, lst=[]):
        count = 0
        for i in range(2, N):
            for j in range(i + 1, N + 1):
                if count == t:
                    return lst
                lst.append('{} {}'.format(i, j))
                count += 1
        return lst

    ans_graph = append_edge((N - 1) * (N - 2) // 2 - K, ans_graph)
    return str(len(ans_graph)) + '\n' + '\n'.join(ans_graph)

N, K = [int(i) for i in input().split()]
print(e_friendships(N, K))
#!/usr/bin/env python
# -*- coding: utf-8 -*-

var = raw_input().split()

var = map(int, var)

if 0 < var[2] - var[4] or 0 < var[3] - var[4]:
	print "No"
	return None
elif var[0] < var[2] + var[4] or var[1] > var[3] + var[4]:
	print "No"
	return None
else:
	print "Yes"

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

var = raw_input().split()

var = map(int, var)

if 0 > var[2] - var[4] or 0 > var[3] - var[4]:
	print "No"
elif var[0] < var[2] + var[4] or var[1] < var[3] + var[4]:
	print "No"
else:
	print "Yes"
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

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

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        if 0 < y_tmp < n and a[y_tmp] != -1:
            ans += a[y_tmp]
            break
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()
a,b=int(input().split())
c=(a*b)%2
if c==1:
  print("Odd")
else:
  print("Even")

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2 == 1:
  print('Odd')
else:
  print('Even')
N = int(input())
A = list(input().split())

ans = float("inf")
for i in range(N):
  a = A[i]
  ans_tmp = 0
  while a%2==0:
    a = a//2
    ans_tmp += 1
  ans = min(ans_tmp, ans)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
ans = float("inf")
for i in range(N):
  a = A[i]
  ans_tmp = 0
  while a%2==0:
    a = a//2
    ans_tmp += 1
  ans = min(ans_tmp, ans)
print(ans)
n, m = map(int, input().split())
a = [int(i) for i in input().split()))]
l = [0 for i in range(n+1)]

for i in range(1, m+1):
    for j in range(n):
        if a[j]<=i and l[i-a[j]] == 0:
            l[i] = 1
            
if l[k] ==1:
    print("First")
else:
    print("Second")

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
 
dp = [0 for i in range(K+1)]
for i in range(K+1):
    if not dp[i]:
        for j in range(N):
            if i + A[j] < K + 1:
                dp[i+A[j]] = 1
 
if dp[K]: print("First")
else: print("Second")
(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines()]
d={}
g=0
for a,b in AB:
    if a in d:
        d[b] = d[a]
    elif b in d:
        b[a] = d[b]
    else:
        g += 1
        d[a] = d[b] = g
for i in range(1,N+1):
    if not i in d:
        g += 1
print(g - 1)

### FIXED CODE ###

(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines() if len(x)>1]

class UnionFind:
    def __init__(self, n):
        self.n=n
        self.parents=[-1 for i in range(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):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.parents[rx] > self.parents[ry]:
            rx,ry=ry,rx
        self.parents[rx] = self.parents[ry]
        self.parents[ry] = rx

    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()}


d=UnionFind(N)
for a,b in AB:
    d.union(a-1,b-1)
print(d.group_count() - 1)
import math
r = int(input())
ret = r * r * math.pi
print('{0:.5f} {1:.5f}'.format(ret, ret))

### FIXED CODE ###

import math
r = float(input())
print('{0:.6f} {1:.6f}'.format(r * r * math.pi, (r + r) * math.pi))
import math
x, y = map(int, input().split())

if x == y or x == 1 or y == 1:
  print(-1)
else:
  print(int(x * y / math.gcd(x, y) - x))

### FIXED CODE ###

x, y = map(int, input().split())
if x % y == 0:
  print(-1)
else:
  print(x)
S==input()
B="ABC"
if S==B:
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

S=input()
B="ABC"
if S==B:
    print("ARC")
else:
    print("ABC")
import bisect

N=int(input())
D=sorted([int(i) for i in input().split()])
M=int(input())
T=[int(i) for i in input().split()]

for t in T:
    bl=bisect.bisect_left(D,t)
    if D[bl]==t:
        del D[bl]
    else:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

from collections import defaultdict

N=int(input())
d = defaultdict(int)
for D in input().split():
    d[int(D)]+=1
M=int(input())
T=[int(i) for i in input().split()]

for t in T:
    if d[t]>=1:
        d[t]-=1
    else:
        print('NO')
        exit()
print('YES')
N = int(input())
s = int(len(N))

if N < 10 :
	print(N)
elif 10 <= N <= 99 :
	print(9)
elif 100 <= N <= 999 :
	print(9 + N -99)
elif 1000 <= N <= 9999 :
	print(909)
elif 10000 <= N <= 99999 :
	print(909 + N - 9999)
elif N = 100000 :
	print(90909)

### FIXED CODE ###

n = int(input())
 
if  n <= 9:
    print(n)
elif 10 <= n <= 99:
    print(9)
elif 100 <= n <= 999:
    print(n-99+9)
elif 1000 <= n <= 9999:
    print(909)
elif 10000 <= n <= 99999:
    print(n-9999+909)
elif n == 100000:
    print(90909)
while True:
  H, W = map(int, input().split())
  if H == 0 and W == 0 :
    break

for i in range(H):
    for j in range(W):
        if                       :
            print("#", end="")
        else:
            print(".", end="")
    print()


### FIXED CODE ###

while True:
  H, W = map(int, input().split())
  
  if H == 0 and W == 0 :
    break
  for i in range(H):
      for j in range(W):
          if i == 0 or i == H-1 or j == 0 or j == W-1 :
              print("#", end="")
          else:
              print(".", end="")
      print()
      
  print()
s = input()
c = Counter(s)
cnt = 0
a = list()
for v in c.values():
    a.append(v)
if max(a)-min(a)>=2:
    print("NO")
else:
    print("Yes")

### FIXED CODE ###

s = input()
abc = [0]*(3)
for i in range(len(s)):
    if s[i] == "a":
        abc[0] += 1
    elif s[i] =="b":
        abc[1] += 1
    else:
        abc[2] += 1
if max(abc)-min(abc) >= 2:
    print("NO")
else:
    print("YES")