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

N, *L = map(int, open(0).read().split())
cost = []
for m in zip(*[iter(L)]*N):
  cost.append(m)
ans = 0
for i in range(N):
  for j in range(i):
    for k in range(N):
      if k==i or k==j:
        continue
      if cost[i][j]>cost[i][k]+cost[k][j]:
        print(-1)
        import sys
        sys.exit()
      if cost[i][j]==cost[i][k]+cost[k][j]:
        break
    else:
      ans += cost[i][j]
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
dist = [[0]*N for i in range(N)]
log = defaultdict(int)
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    for k in range(N):
      if cost[i][j]>=cost[i][k]+cost[k][j]:
        m = min(m,cost[i][k]+cost[k][j])
        if k != i and k!= j:
          log[(min(i,j),max(i,j))] = 1
    dist[i][j] = m
    dist[j][i] = m
ans = 0
for i in range(N):
  for j in range(i+1,N):
    flag = False
    if dist[i][j]<cost[i][j]:
      print(-1)
      flag = True
      break
    elif log[(i,j)]==0:
      ans += cost[i][j]
  if flag:
    break
else:
  print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
a = []
b = []
for _ in range(m):
    a_, b_ = map(int, input().split())
    a_ -= 1
    b_ -= 1
    a.append(a_)
    b.append(b_)
good = list(range(n))
for a_, b_ in zip(a, b):
    if h[a_] == h[b_]:
        if a_ in good:
            good.remove(a_)
        if b_ in good:
            good.remove(b_)
    elif h[a_] < h[b_]:
        if a_ in good:
            good.remove(a_)
    else:
        if b_ in good:
            good.remove(b_)
print(len(good))

### FIXED CODE ###

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

good = set(range(n))
for _ in range(m):
    a_, b_ = map(int, input().split())
    a_ -= 1
    b_ -= 1
    if h[a_] == h[b_]:
        if a_ in good:
            good.remove(a_)
        if b_ in good:
            good.remove(b_)
    elif h[a_] < h[b_]:
        if a_ in good:
            good.remove(a_)
    else:
        if b_ in good:
            good.remove(b_)
print(len(good))
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for _ in range(K):
    counter = [0] * (N+2)
    for i, a in enumerate(A, 1):
        counter[max(0, i - a)] += 1
        counter[min(N+1, i + a + 1)] += -1
    for i in range(1, len(counter)): counter[i] += counter[i-1]
    A = counter[1:N+1]
    if sum(A) == N * N: break
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)
### BUGGY CODE ###

x=int(input())

c=100
a=0
while c<=x:
  c*=0.01
  c=int(c)
  a+=1
print(a)

### FIXED CODE ###

x=int(input())
c=100
a=0
while c<x:
  c+=c//100
  a+=1
print(a)
### BUGGY CODE ###

def inpl(): return map(int, input().split())
from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

 
size = 2 * 10**5
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD



N, K = inpl()
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = inpl()
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*N
P = [0]*N
searched = [0]*N
searched[0] = 1

def count(p):
    global C, searched
    cnt = 0
    for q in G[p]:
        if not searched[q]:
            P[q] = p
            searched[q] = 1
            cnt += 1
            count(q)
    C[p] = cnt
count(0)

ans = K * cmb(K-1, C[0], MOD) * g1[C[0]] % MOD
for i in range(1, N):
    if C[i] == 0:
        continue
    ans = ans * cmb(K-2, C[i], MOD) * g1[C[i]] % MOD

print(ans%MOD)

### FIXED CODE ###

def inpl(): return map(int, input().split())
from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


size = 2 * 10**5
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD



N, K = inpl()
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = inpl()
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*N
P = [0]*N
searched = [0]*N
searched[0] = 1

"""
def count(p):
    global C, searched
    cnt = 0
    for q in G[p]:
        if not searched[q]:
            P[q] = p
            searched[q] = 1
            cnt += 1
            count(q)
    C[p] = cnt
count(0)"""

Q = deque([0])
while Q:
    p = Q.popleft()
    for q in G[p]:
        if not searched[q]:
            P[q] = p
            searched[q] = 1
            C[p] += 1
            Q.append(q)


ans = K * cmb(K-1, C[0], MOD) * g1[C[0]] % MOD
for i in range(1, N):
    if C[i] == 0:
        continue
    ans = ans * cmb(K-2, C[i], MOD) * g1[C[i]] % MOD

print(ans%MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = 0
for i in range(0,N):
  B = A.count(i+1)
  print(B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = {}
for i in A:
  if i not in B:
    B[i] = 0
  B[i] += 1
  
for j in range(1,N+1):
  try:
    print(B[j])
  except KeyError:
    print(0)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W,K = map(int,readline().split())
S = np.array([list(line.rstrip()) for line in readlines()]).astype(np.int8) - ord('0')

# 下から上の順に
S = S[::-1]

def drop(S):
    for i in range(W):
        col = S[:,i]
        S[:,i] = drop_col(col)

def drop_col(col):
    x = np.zeros(H,np.int8)
    nonzero = col[col != 0]
    x[:len(nonzero)] = nonzero
    return x

def cnt_connection(S):
    # 横につながっている個数
    x = np.ones_like(S)
    equal = (S[:,:-1] == S[:,1:])
    for i in range(1,W):
        x[:,i] = x[:,i-1] * equal[:,i-1] + 1
    for i in range(W-2,-1,-1):
        x[:,i][equal[:,i]] = x[:,i+1][equal[:,i]]
    return x

def simulate(S,turn):
    # 落とす -> 消去、で1セット
    drop(S)
    conn = cnt_connection(S)
    remove = (conn >= K)
    before = S.sum()
    S *= (~remove)
    after = S.sum()
    if before == after:
        # 消えなかった
        return 0
    else:
        x = simulate(S,turn+1)
        return x + ((before - after) << turn)

def calc(i,j):
    T = S.copy()
    T[i,j] = 0
    return simulate(T,0)

answer = max(calc(i,j) for i in range(H) for j in range(W))
print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import time
start = time.time()

import numpy as np

H,W,K = map(int,readline().split())
S = np.array([list(line.rstrip()) for line in readlines()]).astype(np.int8) - ord('0')

# 下から上の順に
S = S[::-1].T

def drop(S):
    for i in range(W):
        col = S[i]
        S[i] = drop_col(col)

def drop_col(col):
    x = np.zeros(H,np.int8)
    nonzero = col[col != 0]
    x[:len(nonzero)] = nonzero
    return x

def cnt_connection(S):
    # 横につながっている個数
    x = np.ones_like(S)
    equal = (S[:-1] == S[1:])
    for i in range(1,W):
        x[i] = x[i-1] * equal[i-1] + 1
    for i in range(W-2,-1,-1):
        x[i][equal[i]] = x[i+1][equal[i]]
    return x

def simulate(S,turn):
    # 落とす -> 消去、で1セット
    drop(S)
    conn = cnt_connection(S)
    remove = (conn >= K)
    before = S.sum()
    S *= (~remove)
    after = S.sum()
    if before == after:
        # 消えなかった
        return 0
    else:
        x = simulate(S,turn+1)
        return x + ((before - after) << turn)

def calc(j):
    T = S.copy()
    T[j,0] = 0
    return simulate(T,0)

answer = 0
for i in range(H):
    x = max(calc(j) for j in range(W))
    if answer < x:
        answer = x
    H -= 1
    S = S[:,1:]
    if time.time() - start > 0.9:
        break
print(answer)
### BUGGY CODE ###

#d
def main():
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        tree[b[i]-1].append(a[i])
        
    used_colors=[[] for _ in range(n)]
    ans=dict()
    q = collections.deque([(1,0)])
    #while q:
    for _ in range(n):
        x,parent = q.pop()
        if parent!=0:
            current_color=list(set(color_list)-set(used_colors[parent-1]))[0]
            
            used_colors[parent-1].append(current_color)
            used_colors[x-1].append(current_color)
        
            ans[str(parent)+"_"+str(x)]=current_color
        for y in tree[x-1]:
            if y == parent:
                continue
            q.append((y,x))   
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s]+1)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        
    q = collections.deque([(0,1,0)])#親、子、色
    ans=dict()
    while q:
        parent,togo,old_color = q.popleft()
    #    print(parent,togo,old_color)
        col=1
        for togotogo in tree[togo-1]:
    #        print(togotogo)
            if togotogo == parent:
                continue
            if col == old_color:
                col+=1
            q.append((togo,togotogo,col))
            ans["_".join(map(str,(togo,togotogo)))]=col
            col+=1
        
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N,K=map(int,input().split())
    L=[int(x) for x in input().split()]
    LL=[L[i]*L[i+j] for i in range(0,N) for j in range(1,N-i)]
    print(sorted(LL)[K-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[None]*n for _ in range(n)]
for d in range(n):
  for l in range(n-d):
    r = l + d
    if d:
      dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1])
    else:
      dp[l][r] = a[l]
print(dp[0][n-1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[None]*n for _ in range(n)]
for d in range(n):
  for l in range(n-d):
    r = l + d
    if d:
      dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1])
    else:
      dp[l][r] = a[l]
print(dp[0][n-1])
### BUGGY CODE ###

def main():
    class rolling_hash():
        def __init__(self, seq, char_list=None):
            seq_size = self.seq_size = len(seq)  # 文字列の長さ
            mod = self.mod = 2**61-1  # mod
            base = self.base = 3
            Hash = self.Hash = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(seq_size):
                Hash[i+1] = Hash[i] + (seq[i]+1) * pow(base, i, mod)
    
        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash[r] - self.Hash[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % self.mod
    

    n = int(input())
    a, b = list(map(int, input().split())), list(map(int, input().split()))
    memo = []

    a1 = rolling_hash([a[i-1] ^ a[i] for i in range(n)] +
                      [a[i-1] ^ a[i] for i in range(n)])
    b_hash = rolling_hash([b[i-1] ^ b[i] for i in range(n)]).calc_hash(0, n)
    for i in range(n):
        if a1.calc_hash(i, i+n) == b_hash:
            memo.append(i)
    b0 = b[0]
    for i in memo:
        x = b0 ^ a[i]
        print(i, x)


main()


### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = [None]*25
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0, 3-b), min(5, w-b+3)):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i*5+j] = 1
                else:
                    temp[i*5+j] = 0
        for i in range(3):
            for j in range(3):
                cnt = [temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
                if None not in cnt:
                    ans[sum(cnt)-1].add((a+i-2, b+j-2))

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()


### FIXED CODE ###

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

n=int(input())
a=[list(map(int,input().split()))[::-1] for _ in range(n)]
cnt,tcnt=0,0
ans=0
chk=[]
while tcnt<n*(n-1)//2:
  cnt=0
  chk=[]
  for i in range(n-1):
    if i in chk:
      continue
    else:
      if a[i]:
        b=a[i][-1]-1
        if b in chk:
          continue
        else:
          if b>i and a[b][-1]-1==i:
            chk.append(a[i].pop()-1)
            chk.append(a[b].pop()-1)
            cnt+=1
  tcnt+=cnt
  ans+=1
  if cnt==0:
    ans=-1
    break
print(ans)

### FIXED CODE ###

from collections import deque
n=int(input())
x=lambda i:int(i)-1
a=[deque(list(map(x,input().split()))+[-1]) for _ in range(n)] 
tcnt,ans=n*(n-1),0
chk=set(range(n))
while tcnt>0:
    chk_next=set()
    for i in chk:
        if a[a[i][0]][0]==i:
            chk_next.add(i)
    if len(chk_next)==0:
        ans=-1
        break
    tcnt-=len(chk_next)
    chk=set()
    for i in chk_next:
        a[i].popleft()
        chk.add(i)
        if a[i][0]!=-1:
            chk.add(a[i][0])
    ans+=1

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

N = int(input())
A = input().split()
A = list(map(int,A))
sa = 0
sa_list = []

for i in range(1,N+1):
	sa = A[i-1]-i
	sa_list.append(sa)


useds = []
min_value = 10000000000000000000

for j in range(len(sa_list)):
	if((sa_list[j] not in useds)==True):
		useds.append(sa_list[j])
		b = int(sa_list[j])
		sum_As = 0
		for p in range(1,len(A)+1):
			sum_As += abs(A[p-1]-(b+p))

		if(sum_As<min_value):
			min_value = int(sum_As)

print(min_value)

### FIXED CODE ###

import statistics

N = int(input())
A = input().split()
A = list(map(int,A))
sa = 0
sa_list = []

for i in range(1,N+1):
	sa = A[i-1]-i
	sa_list.append(sa)

sa_list.sort()
if(len(sa_list)%2 != 0):
	b = statistics.median(sa_list)
	sum_As = 0
	for p in range(1,len(A)+1):
		sum_As += abs(A[p-1]-(b+p))
	print(sum_As)
else:
	b = statistics.median_low(sa_list)
	sum_As = 0
	for p in range(1,len(A)+1):
		sum_As += abs(A[p-1]-(b+p))
	
	b2 = statistics.median_high(sa_list)
	sum_As2 = 0
	for p in range(1,len(A)+1):
		sum_As2 += abs(A[p-1]-(b2+p))
	
	print(max(sum_As,sum_As2))
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
P = [0]*N
E = [0]*N
EV = [0]*(N-K+1)

for i in range(N):
    count = 0
    for j in range(1,p[i]+1):
        count = count+j
    P[i] = count
    E[i] = count/p[i]
if N==K:
    print(sum(E))
elif K==1:
    print(max(E))
else:
    for i in range(N-K+1):
        count = 0
        for j in range(K):
            count = count+E[i+j]
        EV[i] = count
    print(max(EV))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
P = [0]*N
E = [0]*N
ev = [0]*(N+1)
EV = [0]*(N-K+1)

for i in range(N):
    P[i] = (p[i]+1)*p[i]/2
    E[i] = P[i]/p[i]
if N==K:
    print(sum(E))
elif K==1:
    print(max(E))
else:
    for i in range(N):
        ev[i+1] = ev[i]+E[i]
    for i in range(N-K+1):
        EV[i]=ev[i+K]-ev[i]
    print(max(EV))
### BUGGY CODE ###

import collections
S = input()
N = len(S)
mod = 2019
div = [0]*N
for i in range(1, N+1):
    div[i-1] = int(S[N-i:N])%mod
d = collections.Counter(div)
print(sum(d.values())-len(d)+d[0])   

### FIXED CODE ###

import collections
S = input()
N = len(S)
mod = 2019
div = [0]*(N+1)
for i in range(N):
    div[i+1] = (div[i] + int(S[N-1-i])*pow(10,i,mod))%mod
d = collections.Counter(div[1::])
ans = d[0]
for i in d.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

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

while True:
  c -= b
  if c <= 0:
    print("Yes")
  a -= d
  if a <= 0:
    print("No")

### FIXED CODE ###

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

while True:
  c -= b
  if c <= 0:
    print("Yes")
    exit(0)
  a -= d
  if a <= 0:
    print("No")
    exit(0)
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,copy,collections

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0

  for i in range(h):
    for j in range(w):
      for k in range(h):
        for l in range(w):
          q=collections.deque()
          if field[i][j]=='#' or field[k][l]=='#':
            continue
          q.append((k,l,0))
          visited=[[-1]*w for _ in range(h)]
          while len(q)>0:
            y,x,c=q.popleft()
            visited[y][x]=c
            if y==i and x==j:
              ans=max(ans,c)
              break

            for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
              ny=y+dy
              nx=x+dx
              if 0<=ny<h and 0<=nx<w:
                if field[ny][nx]=='#':
                  continue
                if visited[ny][nx]!=-1:
                  continue
                q.append((ny,nx,c+1))

  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())