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

import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

A = 10**18
B = 10**9

dx = []
dy = []
cost = []

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0: continue
        elif (i, j) in [(-1,0),(1,0),(0,-1),(0,1)]:
            dx.append(i)
            dy.append(j)
            cost.append(0)
        else:
            dx.append(i)
            dy.append(j)
            cost.append(1)

d[(ch-1) * w + (cw-1)] = 0
q = [(ch-1)*A + (cw-1)*B + 0]
use = [0] * (h * w)

for x in q:
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B
    tmp = curh * w + curw
    if d[tmp] < cnt or use[tmp]: continue
    d[tmp] = cnt
    use[tmp] = 1

    for i in range(24):
        nh = curh + dx[i]
        nw = curw + dy[i]
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt + cost[i]:
            d[nh * w + nw] = cnt + cost[i]
            use[nh * w + nw] = 0
            q.append(nh*A + nw*B + cnt + cost[i])

gh -= 1
gw -= 1
if d[gh*w + gw] == INF: print(-1)
else: print(d[gh*w + gw])


### FIXED CODE ###

import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)
### BUGGY CODE ###

s=input()


i=0
c=0
flag=0
while True:
	if i>len(s)-3: break
	if s[i:i+3]=="ABC":
		j=i
		d=0
		while True:
			if j<0: break
			if s[j]=="A":
				d+=1
				j-=1
			else: break
		s=s[:i-d+1]+"BC"+"A"*d+s[i+3:]
		c+=d
		i+=1
		continue
	else: i+=1

print(c)


### FIXED CODE ###

s=input()


i=0
c=0
flag=0
while True:
	if i>len(s)-2: break
	if s[i]=="A":
		flag+=1
		i+=1
	elif flag and s[i:i+2]=="BC":
		c+=flag
		i+=2
	else:
		flag=0
		i+=1

print(c)
### BUGGY CODE ###

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

total = sum(A)

barlen = total/2

costs = [0 for x in range(N-1)]
for i in range(1, N):
#  print(abs(sum(A[:i]) - sum(A[i:])))
  costs[i-1] = abs(sum(A[:i]) - sum(A[i:]))
  
print(min(costs))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
costs = [0 for x in range(N-1)]
mem = [0 for x in range(N-1)]

for i in range(1, N):
  if i == 1:
    mem[i-1] = A[i-1] * 2
  else:
    mem[i-1] = mem[i-2] + A[i-1] * 2
  costs[i-1] = abs(total - mem[i-1])
  
print(min(costs))
### BUGGY CODE ###

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

sumli = [0]
sum = 0
acum = 0

for i in ali:
    sum = sum + i
    sumli.append(sum)

while len(sumli)!=0:
    s=sumli[0]
    ss=sumli.count(s)
    acum = acum+(ss*(ss-1))//2
    for x in range(ss):
        sumli.remove(s)

print(acum)


### FIXED CODE ###

from collections import Counter

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

sumli = [0]
sum = 0
acum = 0

for i in ali:
    sum = sum + i
    sumli.append(sum)

sumc = Counter(sumli)

for j in list(sumc):
    acum = acum+(sumc[j]*(sumc[j]-1))//2

print(acum)
### BUGGY CODE ###

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

def cnt(a): #階乗の計算
    res = 1
    for i in range(1,a+1):
        res *= i

    return res


if abs(n-m) >= 2:
    print(0)

else:
    if n==m:
        ans1 = cnt(n)
        ans2 = cnt(m)
        print(2*ans1*ans2)
    

    else:
        ans1 = cnt(n)
        ans2 = cnt(m)
        print(ans1*ans2)
        

### FIXED CODE ###

p = 10 ** 9 + 7
N = (10 ** 5)*2 +10  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

n,m = map(int,input().split())
if abs(n-m) > 1:
    print(0)
elif n==m:
    m1 = fact[n]
    print(((m1**2)*2)%p)
else:
    m1 = fact[n]
    m2 = fact[m]
    print((m1*m2)%p)
### BUGGY CODE ###

import heapq

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

l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)

l.sort()
q = []
ans = 0
for i in range(1,m+1):
    while len(l) > 0 and l[0][0] == i:
        tmp = l.pop(0)
        heapq.heappush(q,-tmp[1])
    
    if len(q) != 0:
        ans += -heapq.heappop(q)

print(ans)

### FIXED CODE ###

import heapq

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

l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)

l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)

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

N, Q = map(int, input().split())

to = [[] for _ in range(N)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  to[a].append(b)
  to[b].append(a)

cnt = [0 for _ in range(N)]
for _ in range(Q):
  p, x = map(int, input().split())
  p -= 1
  cnt[p] += x

queue = [[0, -1]]
while len(queue) > 0:
  q = queue.pop(0)
  if q[0] != 0:
    cnt[q[0]] += cnt[q[1]]
  for i in to[q[0]]:
    if i != q[1]:
      queue.append([i, q[0]])

for c in cnt:
  print(c)

### FIXED CODE ###

from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i == k[1]:
            q.append((i, k[0]))

print(*count[1:])
### BUGGY CODE ###

import numpy as np

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

dp = np.full(n, np.inf)

dp[0] = 0
dp[1] = np.abs(h[1] - h[0])

def chmin(a, b):
    if a < b:
        return a
    else:
        return b

for i in range(2, n):
    if i > k:
        k = i
    for j in range(1, k):
        dp[i] = chmin(dp[i], dp[i - j] + np.abs(h[i] - h[i - j]))

print(int(dp[-1]))


### FIXED CODE ###

import numpy as np

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

dp = np.full(n, np.inf)

dp[0] = 0
dp[1] = np.abs(h[1] - h[0])

# def chmin(a, b):
#     if a < b:
#         return a
#     else:
#         return b

for i in range(2, n):

    # 1回目の投稿：for文。ほぼTLE。遅すぎ。
    # for j in range(1, k):
    #     dp[i] = chmin(dp[i], dp[i - j] + np.abs(h[i] - h[i - j]))
    # 2回目の投稿：ベクトル化。最後4つTLE。少し早いけどまだだめ。
    # tmp1 = dp[max(i - k, 0):i + 1 - 1]
    # tmp2 = np.abs(h[i] - h[max(i - k, 0):i + 1 - 1])
    # dp[i] = np.min(tmp1 + tmp2)
    # 3回目の投稿：
    start = max(i - k, 0)
    dp[i] = np.min(dp[start:i] + np.abs(h[i] - h[start:i]))

print(int(dp[-1]))
### BUGGY CODE ###

inf = float('inf')

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

dp = [inf] * n
dp[0] = 0

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

print(dp[n - 1])


### FIXED CODE ###

INF = 10 ** 10

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [INF for _ in range(N)]
dp[0] = 0
# 0-indexed

for i in range(1, N):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))

print(dp[N - 1])
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)

dp = [[-1 for i in range(1001)] for j in range(n)]

cnt = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    tgt = l[i] - l[j]
    if dp[j+1][tgt] != -1:
      cnt += dp[j+1][tgt]
    else:
      lcnt = 0
      for k in range(j+1, n):    
        if l[k] > tgt:
          cnt += 1
          lcnt += 1
        else:
          break
      dp[j+1][tgt] = lcnt

print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)

lptr = [-1] * 1001
lptr[0] = n - 1
for i in range(1, 1001):
  maxptr = n -1
  minptr = 0
  fixed = [-1] * n
  cptr = (maxptr + minptr + 1) // 2

  while fixed[cptr] == -1:

#    print(str(cptr)+','+str(l[cptr]))
    if l[cptr] > i:
      fixed[cptr] = 0
      minptr = cptr
    else:
      fixed[cptr] = 1
      maxptr = cptr
    cptr = (maxptr + minptr + 1) // 2
      
  lptr[i] = cptr - fixed[cptr]

#print(lptr)

    
cnt = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    tgt = l[i] - l[j]
    if lptr[tgt] > j:
      cnt += lptr[tgt] - j

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

R, G, B, N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(3001):
        if N - r * R - g * G >= 0 and (N - r * R - g * G) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

def solve():
    R, G, B, N = map(int, input().split())
    ans = 0
    for r in range(N + 1):
        for g in range(N + 1):
            v = N - r * R - g * G
            if v >= 0 and v % B == 0:
                ans += 1
    print(ans)

solve()
### BUGGY CODE ###

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

ans = sum([a[i]*sum(a[i+1:n]) for i in range(n)])
  
print(ans % (1000000000+7))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
zenbu = sum(a)
ans = 0

for i in range(n):
  ans += a[i]*(zenbu-a[i])
 
print(ans // 2 % 1000000007)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    min = N
    for i in range(0, N):
        m = S[i]
        l = S[:i]
        r = S[i:]
        c = 0
        for h in l:
            if h != 'E': c += 1
        for h in r:
            if h != 'W': c += 1
        if min > c: min = c
    print(min)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ec = S.count('E')
    tec = ec
    for k in S:
        if k == 'E':
            tec -= 1
        else:
            tec += 1
        ec = min(ec, tec)
    print(ec)

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

a,b=map(int,input().split())
import fractions
n=fractions.gcd(a,b)
import math

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
kosuu=0
for i in primes(n+1):
    if n%i==0:
        kosuu+=1
print(kosuu+1)

### FIXED CODE ###

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
#print(factorization(n))
if factorization(n)==[[1,1]]:
  print(1)
else:
  print(len(factorization(n))+1)
### BUGGY CODE ###

N=int(input())
for i in range(2,10**6):
  a=10**20
  for j in range(2,10**6):
    if i*j==N:
      a=min(a,j+i-2)
print(a)

### FIXED CODE ###

N=int(input())
a=10**12
for i in range(1,int(N**.5)+1):
    if N%i==0:
        a=min(a,N//i+i-2)
print(min(N,a))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1;
for i in range(n):
    if ans > 10**18:
        break
    ans *= a[i]
if 0 in a:
    print(0)
elif ans <= 10**18:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
inf = 10 ** 15
dp = [inf for _ in range(n)]
edges = []
for _ in range(m):
    l, r, c = map(int, input().split())
    edges.append((l-1, r-1, c))

edges.sort(key=lambda x: x[0])

dp[0] = 0
for l, r, c in edges:
    for i in range(l+1, r+1):
        dp[i] = min(dp[i], dp[l] + c)

print(dp[n-1] if dp[n-1] < inf else -1)

### FIXED CODE ###

n, m = map(int, input().split())
inf = 10 ** 15
edges = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    edges[l-1].append((r-1, c))
for i in range(n-1):
    edges[i+1].append((i, 0))

from heapq import heappop, heappush
d = [inf for _ in range(n)]
def dijkstra(s):
    que = []
    d[s] = 0
    heappush(que, (0, s))

    while len(que):
        dist, node = heappop(que)

        if d[node] < dist:
            continue
        for to, cost in edges[node]:
            if d[to] > dist + cost:
                d[to] = dist + cost
                heappush(que, (d[to], to))

dijkstra(0)

print(d[n-1] if d[n-1] != inf else -1)
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in input().split()]
ans = 0
for i in range(0, N-1):
    ans += A[i]*sum(A[i+1:])
print(ans%(10**9+7))


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 + 7
sum_A = sum(A)
ans = 0
for i in A:
  ans += i * (sum_A := sum_A - i) % mod
  
print(ans % mod)
### BUGGY CODE ###

from bisect import bisect_right,bisect_left
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
pos = np.sort(a[a>0])
neg = np.sort(np.abs(a[a<0]))
zero = (a==0).sum()

INF = 2*(10**18)
l = -INF
r = INF

while(r-l>1):
    mid = (l+r)//2
    cnt = 0
    if mid >= 0:
        cnt = len(pos)*len(neg)  #(+) * (-)
        cnt += (len(pos)+len(neg)) * zero # 0 * (non-zero)
        cnt += (zero*(zero-1))//2 # 0 * 0
        x = np.searchsorted(pos, mid//pos, side='right').sum() #(+) * (+)
        x += np.searchsorted(neg, mid//neg, side='right').sum() #(-) * (-)
        x -= (pos*pos<=mid).sum()
        x -= (neg*neg<=mid).sum()
        cnt += x/2
    else:
        #積がmid以上になれば良い -> midよりも小さい
        cnt = (len(neg) - np.searchsorted(neg, abs(mid)//pos + (mid%pos!=0), side='left')).sum()
    #print(mid, cnt)
    #cnt := 積がmid以下になる物の数
    #k番目の数　-> それ以下のものがk個以上ある事が必要
    #cntがk個よりも少ない -> 条件を満たしていない
    #cntがそれ以上ならok
    if cnt < k:
        l = mid
    else:
        r = mid
print(r)
### BUGGY CODE ###

s = input().strip()
k = int(input())
ss = []
for i in range(1, len(s) + 1):
    for j in range(len(s) + 1 - i):
        ss.append(s[j:j + i])
ss = list(set(ss))
ss.sort()
print(ss[k - 1])

### FIXED CODE ###

s = input().strip()
k = int(input())
ss = []
n = len(s)
for i in range(n):
    for j in range(1, 6):
        if i + j <= n:
            ss.append(s[i:i + j])
ss = list(set(ss))
ss.sort()
print(ss[k - 1])
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
monster = {}
x = []
for i in range(n):
    xx, hh = MAP()
    monster[xx] = hh
    x.append(xx)
x.sort()
cnt = 0
for i in range(n):
    cx, ch = x[i], monster[x[i]]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    j = i + 1
    while j < n:
        nx = x[j]
        if nx <= cx + 2*d:
            monster[nx] -= cn * a
            j += 1
        else:
            break
    
print(cnt)

### FIXED CODE ###

from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)
### BUGGY CODE ###

n, s = int(input()), input()
a = ["R", "G", "B"]
cnt = [0, 0, 0]
for i in s:
    cnt[a.index(i)] += 1
c = cnt[0] * cnt[1] * cnt[2]
for i in range(1, n+1):
    for j in range(i+1, n+1):
        k = 2 * j - i
        if j < k <= n:
            if s[i-1] != s[j-1] and s[j-1] != s[k-1] and s[k-1] != s[i-1]:
                c -= 1

print(c)

### FIXED CODE ###

n, s = int(input()), input()
a = ["R", "G", "B"]
cnt = [0, 0, 0]
for i in s:
    cnt[a.index(i)] += 1
c = cnt[0] * cnt[1] * cnt[2]
for i in range(1, n-1):
    for j in range(i+1, n):
        k = 2 * j - i
        if j-1 < k-1 < n:
            if s[i-1] != s[j-1] and s[j-1] != s[k-1] and s[k-1] != s[i-1]:
                c -= 1

print(c)
### BUGGY CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
S= np.zeros_like(T, dtype='bool')
d=0
c=deque()

for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c+=[i,j]
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        m = c.popleft()
                        n = c.popleft()
                        S[m][n]=True
                        if m != H-1:
                                if T[m+1][n]==0 and S[m+1][n]==0:c+=[m+1,n]
                        if m != 0:
                                if T[m-1][n]==0 and S[m-1][n]==0:c+=[m-1,n] 
                        if n != W-1:
                                if T[m][n+1]==0 and S[m][n+1]==0:c+=[m,n+1]
                        if n != 0:
                                if T[m][n-1]==0 and S[m][n-1]==0:c+=[m,n-1]
                        #c += (chk_route([c.popleft(),c.popleft()]))
                
        #print(T)
        d = max(d,s)
        S= np.zeros_like(T, dtype='bool')
        
print(d-2)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
### BUGGY CODE ###

n = int(input())
a = [list(map(lambda s: int(s) - 1, input().split())) for _ in range(n)]

def f():
    day = 0
    ptrs = [0] * n

    while True:
        if all(ptr == n - 1 for ptr in ptrs):
            return day

        visited = set()
        ok = False
        for i in range(n):
            if ptrs[i] == n - 1 or i in visited:
                continue
            
            x = a[i][ptrs[i]] # iの次候補
            if ptrs[x] == n - 1 or x in visited:
                continue

            y = a[x][ptrs[x]] # xの次候補
            if i == y:
                ptrs[i] += 1
                ptrs[x] += 1
                visited.add(i)
                visited.add(x)
                ok = True

        # すべて未訪問の場合
        if not ok:
            return -1
        day += 1

print(f())

### FIXED CODE ###

import collections

n = int(input())
a = [collections.deque(int(s) - 1 for s in input().split()) for _ in range(n)]

day = 0
players = set(range(n))
while any(v for v in a):
    nxt_players = set()
    for player in players:
        if len(a[player]) == 0 or player in nxt_players:
            continue
        
        other = a[player][0]
        if len(a[other]) == 0 or other in nxt_players:
            continue
        
        if player == a[other][0]:
            a[player].popleft()
            a[other].popleft()
            nxt_players.add(player)
            nxt_players.add(other)

    if nxt_players:
        day += 1
        players = nxt_players
    else:
        print(-1)
        exit()

print(day)