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

from collections import deque
N, K, C = map(int, input().split())
S = input()

fastest = deque([])
latest = deque([])
ans = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] != 'o':
        date += 1
        if date > N:
            break
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] != 'o':
        date += 1
        if date > N:
            break
    latest.appendleft(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[i]:
        ans.append(fastest[i])

print(*ans)    

### FIXED CODE ###

N, K, C = map(int, input().split())
S = input()

fastest = []
latest = []


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.append(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[- (i + 1)]:
        print(fastest[i])
### BUGGY CODE ###

N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        G1.append([MIN,cnt])
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])

# print(G1,G2,G3,G4)

cnt = 0
for L in G1:
    cnt += L[1]
G2.sort(reverse=True)
for L in G2:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
G4.sort()
for L in G4:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
for L in G3:
    cnt += L[1]

if cnt == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
G2,G4 = [],[]
cnt2 = 0
cnt3 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        cnt3 += cnt
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += cnt3

if cnt2 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*n

dp[1] = abs(h[1]-h[0])
for i in range(2, n):
  for j in range(1,min(i+1,k+1)):
    if j == 1:
      dp[i] = dp[i-1]+abs(h[i]-h[i-1])
    #print([i,j], dp[i-j]+abs(h[i]-h[i-j]), dp[i])
    dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
#print(h)
print(dp[-1])

### FIXED CODE ###

def main():
  n, k = map(int, input().split())
  h = [int(n) for n in input().split()]
  dp = [0]*n
  for i in range(1, n):
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])  
  print(dp[-1])

if __name__ == "__main__":
  main()
### BUGGY CODE ###

# 2019/09/01

n=int(input())
cnt=0
for i in range(1,n):
    cnt+=i
print(cnt)

### FIXED CODE ###

# 2019/09/01

n=int(input())

ans=(1+n-2)*n//2
print(ans)
### BUGGY CODE ###

N = input()
a = [0] * 2050
n = 0
p = 1
for i in range(len(N)):
    n += int(N[len(N)-1-i]) * p
    p *= 10
    a[int(n) % 2019] += 1
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)


### FIXED CODE ###

N = input()
a = [0] * 2050
n = 0
p = 1
for i in range(len(N)):
    n += int(N[len(N)-1-i]) * p
    p *= 10
    p %= 2019
    a[int(n) % 2019] += 1
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d=[999999999999999]*n
d[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            break 
        d[i]=min(d[i],d[i-j]+abs(a[i]-a[i-j]))
print(d[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d=[999999999999999]*n
d[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            break 
        d[i]=min(d[i],d[i-j]+abs(a[i]-a[i-j]))
print(d[n-1])
### BUGGY CODE ###

count = 0
def merge(A,left,mid,right):
    n1 = mid- left
    n2 = right - mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]

    for i in range(n1):
        L[i]= A[left+i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = float("INFINITY")
    R[n2] = float("INFINITY")
    i = 0
    j = 0
    for k in range(left,right):
        global count 
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j += 1
            
def mergeSort(A,left,right):
    if left + 1 < right:
        mid = (left+ right) //2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(A,0,n)

print(" ".join(map(str,A)))
print(count)

### FIXED CODE ###

from collections import deque
SENIAL = 10**9
count = 0

def merge(A,left,mid,right):
    L = deque(A[left:mid])
    R = deque(A[mid:right])
    L.append(SENIAL)
    R.append(SENIAL)
    
    global count
    
    for k in range(left,right):
        count +=1
        if L[0] <= R[0]:
            A[k] = L.popleft()
 
        else:
            A[k] = R.popleft()

            
def mergeSort(A,left,right):
    if left + 1 < right:
        middle = (left + right) //2
        mergeSort(A,left,middle)
        mergeSort(A,middle,right)
        merge(A,left,middle,right)
        
input()
l = list(map(int,input().split()))
mergeSort(l,0,len(l))
print(" ".join(map(str,l)))
print(count)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()
  a=getPrimeList(n)

  ans=inf
  b=len(a)
  for i in range(2**b//2):
    _a=_b=1
    for j in range(b):
      if ((i >> j) & 1):
        _a*=a[j]
      else:
        _b*=a[j]
    ans=min(ans,_a+_b-2)
  return ans

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  ans=inf
  for x in range(1,int(math.sqrt(n))+1):
    if n%x==0:
      ans=min(ans,x+n//x-2)
  return ans

# main()
print(main())
### BUGGY CODE ###

n=int(input())
s=input()
sl=[c for c in s]
ans=0
l=[]
for i in range(n):
  for j in range(i+1,n):
    if not sl[i]+sl[j] in l:
      l.append(sl[i]+sl[j])
      ans+=len(set(sl[j+1:]))
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000):
  v=str(i)
  v=v.zfill(3)
  ss=s
  if not v[0] in ss:
    continue  
  ss=ss[ss.index(v[0])+1:]
  if not v[1] in ss:
    continue
  ss=ss[ss.index(v[1])+1:]
  if not v[2] in ss:
    continue
  ans+=1
print(ans)
### BUGGY CODE ###

s = input()

# step1: pre-process "BC" を Xに置き換える
tmp = ""
flag = False  # skip用
for i in range(1, len(s)):
    if flag:
        flag = False
        continue
    elif s[i - 1] + s[i] == "BC":
        tmp += "X"
        flag = True
    else:
        tmp += s[i - 1]

if not flag:
    tmp += s[-1]

cnt = 0
ans = 0
# step:2 Xより左側にあるAの数を数える。
# ただし、B、Cが現れると、カウンターリセット
# （そのB、Cを越えてSwapできないため）
for i in range(len(tmp)):
    if tmp[i] == "A":
        cnt += 1
    elif tmp[i] == "B" or tmp[i] == "C":
        cnt = 0
    elif tmp[i] == "X":
        ans += cnt

print(ans)


### FIXED CODE ###

s = input()

tmp = ""
cnt = 0
ans = 0
flag = False  # skip用
for i in range(0, len(s) - 1):
    if flag:
        flag = False
        continue
    if s[i] == "A":
        cnt += 1
    elif s[i] + s[i + 1] == "BC":
        ans += cnt
        flag = True
    else:
        cnt = 0

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

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ma = 0
for i in range(2**n):
	a = bin(i)
	if len(a) < n+2:
		b = "0" * (n+2-len(a))
		a = a[:2] + b + a[2:]
	get = 0
	pay = 0
	for j in range(n):
		if a[j+2] == '1':
			get += v[j]
			pay += c[j]
	if ma < (get - pay):
		ma = (get - pay)

print(ma)


### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ma = 0
for i in range(2**n):
	a = bin(i)
	if len(a) < n+2:
		b = "0" * (n+2-len(a))
		a = a[:2] + b + a[2:]
	get = 0
	pay = 0
	for j in range(n):
		if a[j+2] == '1':
			get += v[j]
			pay += c[j]
	if ma < (get - pay):
		ma = (get - pay)

print(ma)
### BUGGY CODE ###

import math
S=int(input())
ss=math.sqrt(S)
s=math.floor(ss)
for i in range(s):
    n=s-i
    if S%n==0:
        t=n
        break
print(0,0,0,t,round(S/t),0)


### FIXED CODE ###

import math
S=int(input())
ss=math.sqrt(S)
s=math.ceil(ss)
t=s*s-S
if t>10**9:
    for n in range(2,t+1):
        if t%n==0:
            k=n
            break
elif t>0:
    k=1
    print(0,0,s,k,round(t/k),s)
if t==0:
    print(0,0,s,0,0,s)
### BUGGY CODE ###

n, k = map(int,input().split())
while True:
  i = 1
  x = k
  if (x >= n):
    print(i)
    break
  else:
    i = i + 1
    x = x*k
    

### FIXED CODE ###

n, k = map(int,input().split())
i = 1
x = k
while True:
  if (x > n):
    print(i)
    break
  else:
    i = i + 1
    x = x*k
### BUGGY CODE ###


import numpy as np

def read_input():
    n, a = map(int, input().split())
    xlist = list(map(int, input().split()))
    return n, a, xlist


def submit():
    n, a, xlist = read_input()

    dp = np.zeros((n + 1, n + 1, (n + 1) * max(max(xlist), a)))

#   dp[j][k][s] : j枚目までのカードでk枚選び、合計sにする方法の数
#         (1) dp[0][0][0] : 1枚も選ばずに合計0にする方法は1種類
#               j = k = s = 0のとき
#         (2) dp[j][k][s] = dp[j - 1][k][s] if xj > s : j枚目のカードがsより大きいとき、sを作りようがないのでj-1枚目までの手法と一緒
#               j > 0, xj > sのとき
#         (3) dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xj]
#               : xj <= sのとき、j-1枚目まででsを作る方法と、j-1枚目まででs-xjをつくり、j枚目を選んでk枚にする
#               j > 0, k > 0, s >= xjのとき
#         (4) dp上記以外は無理なので0

    for j in range(n + 1):
        for k in range(n + 1):
            for s in range((n + 1) * max(xlist)):
                if j == k == s == 0:
                    dp[j][k][s] = 1
                elif j > 0 and xlist[j - 1] > s:
                    dp[j][k][s] = dp[j - 1][k][s]
                elif j > 0 and k > 0 and xlist[j - 1] <= s:
                    dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xlist[j - 1]]
                else:
                    dp[j][k][s] = 0

    methods = 0
    for i in range(1, n + 1):
        methods += dp[n][i][i * a]

    print(int(methods))


if __name__ == '__main__':
    submit()


### FIXED CODE ###

def read_input():
    n, a = map(int, input().split())
    xlist = list(map(int, input().split()))
    return n, a, xlist


def make_matrix():
    dp = [
        [
            [0] * ((n + 1) * max(max(xlist), a)) for _ in range(n + 1)
        ] for _ in range(n + 1)
    ]



def submit():
    n, a, xlist = read_input()

    dp = [
        [
            [0] * ((n + 1) * max(max(xlist), a)) for _ in range(n + 1)
        ] for _ in range(n + 1)
    ]

#   dp[j][k][s] : j枚目までのカードでk枚選び、合計sにする方法の数
#         (1) dp[0][0][0] : 1枚も選ばずに合計0にする方法は1種類
#               j = k = s = 0のとき
#         (2) dp[j][k][s] = dp[j - 1][k][s] if xj > s : j枚目のカードがsより大きいとき、sを作りようがないのでj-1枚目までの手法と一緒
#               j > 0, xj > sのとき
#         (3) dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xj]
#               : xj <= sのとき、j-1枚目まででsを作る方法と、j-1枚目まででs-xjをつくり、j枚目を選んでk枚にする
#               j > 0, k > 0, s >= xjのとき
#         (4) dp上記以外は無理なので0

    dp[0][0][0] = 1

    for j in range(n + 1):
        for k in range(n + 1):
            for s in range((n + 1) * max(xlist)):
                if j > 0 and xlist[j - 1] > s:
                    dp[j][k][s] = dp[j - 1][k][s]
                elif j > 0 and k > 0 and xlist[j - 1] <= s:
                    dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - xlist[j - 1]]

    methods = 0
    for i in range(1, n + 1):
        methods += dp[n][i][i * a]

    print(int(methods))


if __name__ == '__main__':
    submit()
### BUGGY CODE ###

n = int(input())
s = input()

count = 0
 
for i,first in enumerate(s[:-2]):
    for j,second in enumerate(s[i+1:n-1]):
        if first != second:
            if 'R' != first and 'R' != second:
                third = 'R'
            elif 'G' != first and 'G' != second:
                third = 'G'
            else:
                third = 'B'
            count += s[i+j+2:].count(third)
            if i+j+2+j <= n-1 and s[i+j+2:][j] == third:
                count -= 1
 
print(count)

### FIXED CODE ###

n = int(input())
s = input()

r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

count = r_count*g_count*b_count


for i,elem in enumerate(s):
    length = min(i,n-1-i)
    for j in range(1,length+1):
        elem_2 = s[i-j]
        elem_3 = s[i+j]
        if elem != elem_2 and elem != elem_3 and elem_2 != elem_3:
            count -= 1

print(count)
### BUGGY CODE ###

import collections as col
import itertools as ite
import numpy as np
import math as ma

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD
def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    ans *= comb(val + n-1, n-1)
    ans %= MOD
print(ans)


### FIXED CODE ###

import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= spm.comb(val + n-1, n-1, exact=1)
    ans %= MOD
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
list=[]
for i in range(n):
    a,b=map(int,input().split())
    for j in range(b):
        list.append(a)
list.sort()
print(list[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
list=[]
for i in range(n):
    a,b=map(int,input().split())
    list.append([a,b])
list.sort()
sum=0
for x in list:
    sum+=x[1]
    if sum >=k:
        print(x[0])
        break
### BUGGY CODE ###


def solve():
    for n in range(1,N+1):
        cnt = 0
        for x in range(1,int(n**0.5)+1):
            for y in range(1,x+1):
                for z in range(1,x+1):
                    if x**2+y**2+z**2+x*y+y*z+z*x==n:
                        if x==y==z:
                            cnt += 1
                        else:
                            cnt += 3
                            x += 1
        print(cnt)

if __name__=="__main__":
    N = int(input())
    solve()


### FIXED CODE ###

N = int(input())
ls = [0]*(N+2)
 
for i in range(1,151):
    for j in range(1,151):
        for k in range(1,151):
            t = i*i + j*j + k*k + i*j + j*k + k*i 
            if t <= N :
                ls[t] += 1
 
for p in range(1,N+1):
    print(ls[p])
### BUGGY CODE ###

def main():
    n, m = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    for _ in range(m):
        b, c = [int(i) for i in input().split()]
        a.extend([c] * b)
    a = sorted(a)[-n:]
    print(sum(a))


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n, m = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    
    bc = []
    for _ in range(m):
        b, c = map(int, input().split())
        bc.append((b, c))

    total = 0
    for num, v in sorted(bc, key=lambda x: -x[1]):
        total += num
        a.extend([v]*num)
        if total >= n:
            break
    print(sum(sorted(a)[-n:]))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s=input()
s=s.strip("\n")
n=len(s)
res=0
d={key:0 for key in range(2019)}
t=[0]*(n+1)
d[0]=1
for i in range(1,n+1):
    t[n-i]=(t[n-i+1]+(int(s[n-i])*10**(i-1))%2019)%2019
    d[t[n-i]]+=1
for i in d.values():
    if i<2:
      continue
    res+=int(i*(i-1)/2)
print(res)


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()
### BUGGY CODE ###

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

j = 0

for i in range(1,n+1):
  lii = min(li[0:i])
  if lii == li[i-1]:
    j = j + 1
  if lii == 1:
    break

print(j)

### FIXED CODE ###

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

i = 0
j = 0
a = 10**6
for i in range(i,n):
  a = min(a,li[i])
  if a == li[i]:
    j = j + 1

print(j)
### BUGGY CODE ###

N = int(input())
a = [int(x) for x in input().split()]


for i in range(1,N+1):
    answer = a.count(i)
    print(answer)

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
answer = [0] * N
for i in range(1,N):
    x = a[i-1]
    answer[x-1] +=1

for i in range(N):
    print(answer[i])
### BUGGY CODE ###

n,m,k=map(int,input().split())

class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for i in range(n)]

    def find(self,x):
        if(self.parent[x]==x):
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):
            pass
        elif(self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[y] = x
            if(self.rank[x] == self.rank[y]):
                self.rank[x]+=1

    def same(self,x,y):
        return self.find(x)==self.find(y)

uf=UnionFind(n)
friendlist=[set() for _ in range(n)]
blocklist=[set() for _ in range(n)]


for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friendlist[a].add(b)
    friendlist[b].add(a)
    uf.unite(a,b)

for i in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    blocklist[c].add(d)
    blocklist[d].add(c)

grouplist={}
rootlist=[]
for i in range(n):
    rooti=uf.find(i)
    rootlist.append(rooti)
    groupi=grouplist.get(rooti, set())
    groupi.add(i)
    grouplist[rooti]=groupi

ans=[]
for i in range(n):
    ans.append(len(grouplist[rootlist[i]] - friendlist[i] - blocklist[i] ) - 1)
print(*ans)


### FIXED CODE ###

n,m,k=map(int,input().split())

class UnionFind:
    def __init__(self,n):
        self.group=[i for i in range(n)]
        self.size=[1 for i in range(n)]

    def find(self,x):
        if(self.group[x]==x):
            return x
        else:
            return self.find(self.group[x])

    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):
            pass
        elif(self.sizeof(y) > self.sizeof(x)):
            self.group[x] = self.group[y]
            self.size[y] += self.size[x]
            self.size[x]=0
        else:
            self.group[y] = self.group[x]
            self.size[x] += self.size[y]
            self.size[y]=0

    def sizeof(self,a):
        return self.size[self.find(a)]

    def same(self,x,y):
        return self.find(x)==self.find(y)

uf=UnionFind(n)
friends=[0 for _ in range(n)]
blocks=[0 for _ in range(n)]


for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friends[a]+=1
    friends[b]+=1
    uf.unite(a,b)

for i in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if(uf.same(c, d)):
        blocks[c]+=1
        blocks[d]+=1

ans=[]
for i in range(n):
    ans.append(uf.sizeof(i) - friends[i] - blocks[i]  - 1)
print(*ans)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
ab = []
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
                ab.append((i, j))
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
for i in range(n):
    dq = deque()
    dist = [-1] * n
    dq.append((i, 0))
    ok = True
    while dq:
        v, d = dq.popleft()
        if dist[v] == -1:
            dist[v] = d
        elif dist[v] != d:
            ok = False
            break
        for item in edge[v]:
            if dist[item] == -1:
                dq.append((item, d+1))
    if ok:
        ans = max(ans, max(dist))

if ans > 0:
    print(ans + 1)
else:
    print(-1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((0, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == d:
        continue
    if dist[v] == -1:
        dist[v] = d
    else:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)