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

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
def bfs(i,j):
    global h,w,s,dp
    if i>0:
        if dp[i-1][j]!=-1:
            if dp[i-1][j]>dp[i][j]:
                dp[i-1][j]=dp[i][j]
                bfs(i-1,j)
    if j>0:
        if dp[i][j-1]!=-1:
            if dp[i][j-1]>dp[i][j]:
                dp[i][j-1]=dp[i][j]
                bfs(i,j-1)
    if i<h-1:
        if dp[i+1][j]!=-1:
            if dp[i+1][j]>dp[i][j]:
                dp[i+1][j]=dp[i][j]
                bfs(i+1,j)
    if j<w-1:
        if dp[i][j+1]!=-1:
            if dp[i][j+1]>dp[i][j]:
                dp[i][j+1]=dp[i][j]
                bfs(i,j+1)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w:
                if dp[i+k][j+l]!=-1:
                    if dp[i+k][j+l]>dp[i][j]+1:
                        dp[i+k][j+l]=dp[i][j]+1
                        bfs(i+k,j+l)

bfs(c[0],c[1])
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

### FIXED CODE ###

#辺の重み(変化量)が0である場合は01DFSって特別なやつ
#0の場合はそこでBFSできる
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        if i>0:
            if dp[i-1][j]!=-1:
                if dp[i-1][j]>dp[i][j]:
                    dp[i-1][j]=dp[i][j]
                    now.appendleft([i-1,j])
        if j>0:
            if dp[i][j-1]!=-1:
                if dp[i][j-1]>dp[i][j]:
                    dp[i][j-1]=dp[i][j]
                    now.appendleft([i,j-1])
        if i<h-1:
            if dp[i+1][j]!=-1:
                if dp[i+1][j]>dp[i][j]:
                    dp[i+1][j]=dp[i][j]
                    now.appendleft([i+1,j])
        if j<w-1:
            if dp[i][j+1]!=-1:
                if dp[i][j+1]>dp[i][j]:
                    dp[i][j+1]=dp[i][j]
                    now.appendleft([i,j+1])
        for k in range(-2,3):
            for l in range(-2,3):
                if 0<=i+k<h and 0<=j+l<w:
                    if dp[i+k][j+l]!=-1:
                        if dp[i+k][j+l]>dp[i][j]+1:
                            dp[i+k][j+l]=dp[i][j]+1
                            now.append([i+k,j+l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)
### BUGGY CODE ###

import numpy as np

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp=np.zeros((n,k+1),dtype="int64")
    dp[0][0] = 1
    dpi = dp[0]
    for i, a in enumerate(a_s[:-1]):
        dpi1 = dp[i + 1]
        dpi1[0] = s = dp[i][0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
        dpi = dpi1
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

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

data = [0] * 100001

def my_sum(d):
    retval = 0

    for i in range(len(d)):
        if d[i] == 0:
            continue
        retval += d[i] * i
    return retval

for i in A:
    data[i] += 1
 
for i in range(Q):
    B, C = map(int, input().split())

    if data[B] != 0:
        data[C] += data[B]
        data[B] = 0
 
    print(my_sum(data))

### FIXED CODE ###

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

data = [0] * 100001

def my_sum(d):
    retval = 0

    for i in range(len(d)):
        if d[i] == 0:
            continue
        retval += d[i] * i
    return retval

for i in A:
    data[i] += 1

sum_val = my_sum(data)

for i in range(Q):
    B, C = map(int,input().split())

    sum_val = sum_val - (data[B] * B) + (data[B] * C)

    data[C] += data[B]
    data[B] = 0

    print(sum_val)
### BUGGY CODE ###


import fractions

A, B = map(int, input().split())

G = fractions.gcd(A, B)
g = G
ans = 1


for i in range(G-1):
    if (g < i):
        break
    if(g % (i+2) == 0):
        ans += 1
        j = 1
        while(g % (i+2) == 0):
            g /= i+2
            j += 1

print(ans)


### FIXED CODE ###

import fractions
from math import sqrt

A, B = map(int, input().split())

G = fractions.gcd(A, B)
N = int(sqrt(max(A,B)))+1
g = G
ans = 1

for i in range(2, N+3):
    if(g % i == 0):
        ans += 1
        while(g % i == 0):
            g = g/i
            
if g != 1:
    ans += 1

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

a,b,c,k=map(int,input().split())
ans=[]
for i in range(a+1):
    for j in range(b+1):
        ans.append(i+j*0-(k-i-j))
print(max(ans))

### FIXED CODE ###

a,b,c,k=map(int,input().split())
ans=[]
if k <= a:
    print(k)
elif k == a+b:
    print(a)
else:
    print(a+b*0-(k-a-b))
### BUGGY CODE ###

N = int(input())
S = list(input())
min = N - 1
for i in range(N):
  cnt = S[:i].count('W') + S[i+1:].count('E')
  if cnt < min:
    min = cnt
print(min)

### FIXED CODE ###

N = int(input())
S = list(input())
W = 0
E = S[1:].count('E')
Turn = []
Turn.append(E)

for i in range(1, N):
  if S[i] == 'E':
    E -= 1
  if S[i-1] == 'W':
    W += 1
  Turn.append(E+W)

print(min(Turn))
### BUGGY CODE ###

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

k = 0
idx = -1
while True:
  if k + 1 in a[(idx + 1):]:
    idx += a[(idx + 1):].index(k + 1) + 1
    k += 1
  else:
    break

print(n - k if k > 0 else -1)

### FIXED CODE ###

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

k = 0

for i in range(n):
  if a[i] == k + 1:
    k += 1

print(n - k if k > 0 else -1)
### BUGGY CODE ###

from bisect import insort,bisect_left

N,M = map(int,input().split())
PY = [list(map(int,input().split())) for _ in range(M)]

d = {}

for py in PY:
    tmp = d.get(py[0],[])
    insort(tmp,py[1])
    d[py[0]] = tmp

for py in PY:
    s1 = str(py[0])
    s1 = ("0"*(6-len(s1)))+s1
    s2 = str(bisect_left(d[py[0]],py[1])+1)
    s2 = ("0"*(6-len(s2)))+s2

    print(s1+s2)


### FIXED CODE ###

N,M = map(int,input().split())
PY = [list(map(int,input().split()))+[i] for i in range(M)]

num = [0]*N
ans = [""]*M

PY.sort(key = lambda x:x[1])

for p,y,i in PY:
    num[p-1] += 1
    ans[i] = str(p).zfill(6) + str(num[p-1]).zfill(6)

for a in ans:
    print(a)
### BUGGY CODE ###

x = int(input())
from math import gcd
c = 0
for i in range(1,x+1):
    for j in range(1, x+1):
        for k in range(1, x+1):
            a = gcd(i, j)
            b = gcd(a, k)
            c += b
print(c)

### FIXED CODE ###

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

def main():
  import fractions
  import math

  a,b = map(int,input().split())
  
  d = [1]
  num = 2

  while num <= min(a,b):
    #print("num",num)
    if a%num == 0 and b%num == 0:
      d.append(num)
    while a%num == 0 and a>1:
      a = a//num
      #print(a)
    while b%num == 0 and b>1:
      b = b//num
      #print(b)
    num += 1
  
  print(len(d))

if __name__ == "__main__":
  main()



### FIXED CODE ###

def main():
  import fractions
  import math

  a,b = map(int,input().split())
  g = fractions.gcd(a,b)
  
  d = [1]
  num = 2

  while num**2 <= g:
    #print("num",num)
    if g%num == 0:
      d.append(num)
    while g%num == 0 and g>1:
      g = g//num
      #print(g)
    num += 1
  
  print(len(d) + (g > 1))

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

K = int(input())
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

temp = []

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            temp.append(gcd(i,j,k))
print(sum(temp))

### FIXED CODE ###

K = int(input())
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


temp = []

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            temp.append(gcd(i,j,k))
print(sum(temp))
### BUGGY CODE ###

import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

def maxim(i,char):
    if i<0:
        return 0
    if d[i,char]!=-1:
        ##print('hi')
        ##print(i,char)
        return d[i,char]
    if char=='C':
        d[i,char]= max(c[i]+maxim(i-1,'B'),c[i]+maxim(i-1,'A'))
        return d[i,char]
    if char=='B':
        d[i,char]= max(b[i] + maxim(i - 1, 'A'), b[i] + maxim(i - 1, 'C'))
        return d[i,char]
    if char=='A':
        d[i,char]= max(a[i] + maxim(i - 1, 'B'), a[i] + maxim(i - 1, 'C'))
        return d[i,char]
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    d=dict()
    for i in range(n):
        d[i,'A']=-1
        d[i,'B']=-1
        d[i,'C']=-1
    a.append(x)
    b.append(y)
    c.append(z)
ans1=maxim(n-1,'C')
ans2=maxim(n-1,'B')
ans3=maxim(n-1,'A')
print(max(ans1,ans2,ans3))




### FIXED CODE ###

import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(3)]for j in range(n)]
li[0][0],li[0][1],li[0][2]=a[0],b[0],c[0]
for i in range(1,n):


        li[i][0] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])

        li[i][1] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])

        li[i][2] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
print(max(li[n-1]))
### BUGGY CODE ###

N = int(input())
A_list = [int(input()) for _ in range(N)]
lst = []
for A in A_list:
    next = -1
    for l in lst:
        if (l < A):
            next += 1
    if (next == -1):
        tmp = lst
        lst = [A]
        lst.extend(tmp)
    elif (next == len(lst)):
        lst.append(A)
    else:
        lst[next] = A
print(len(lst))


### FIXED CODE ###

from collections import deque
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
queue = deque()
for a in A:
    pos = bisect_left(queue, a)
    if (pos == 0):
        queue.appendleft(a)
    else:
        queue[pos-1] = a
print(len(queue))
### BUGGY CODE ###

n,k,q = map(int,input().split())
points = [k]*n
for i in range(q):
    winner = int(input())
    for j in range(n):
        points[j] -= 1
    points[winner - 1] += 1
for i in points:
    if i > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
points = [k-q]*n
for i in range(q):
    winner = int(input())
    points[winner - 1] += 1
for i in points:
    if i >0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

input()
ans = 1
for i in map(int, input().split()):
  ans *= i
  
if ans > 10**18:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

input()
ans = 1
l = list(map(int, input().split()))
if 0 in l:
  print(0)
  exit()
for i in l:
  ans *= i
  if ans > 10**18:
    print(-1)
    exit()
  

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


n, m, p = map(int, input().split())
arr = [0]*(m)
for i in range(m):
	arr[i] = tuple(map(int, input().split()))
# n, m, p = 4, 5, 10
# arr = [[1, 2, 1], [1, 4, 1], [3, 4, 1], [2, 2, 100], [3, 3, 100]]

# n, m, p = 2, 2, 10
# arr = [(1, 2, 100), (2, 2, 100)]

# n, m, p = 3, 3, 10
# arr = [(1, 2, 20), (2, 3, 30), (1, 3, 45)]

dist = [float('inf')]*(n+1)

dist[1] = 0
parent = [-1]*(n+1)
for k in range(n-1):
	for i in range(m):
		u, v, c = arr[i]
		c = max(c-p, 0)
		if dist[u] - c < dist[v]:
			dist[v] = dist[u] - c
			if v != u: parent[v] = u
path = []
end = n
while parent[end] != -1:
	path.append(end)
	end = parent[end]
# print(parent)	
# print(dist)
path.append(1)
path.reverse()
old_dist = list(dist)

for i in range(m):
	u, v, c = arr[i]
	c = max(c-p, 0)
	if old_dist[u] - c < dist[v]:
		old_dist[v] = old_dist[u] - c
# print(old_dist)
for ele in path:
	if old_dist[ele] != dist[ele]:
		neg_cycle = True
		break
	neg_cycle = False

if neg_cycle:
	print(-1)
else:
	print(-1 if n not in path else -dist[n])

### FIXED CODE ###

import sys

n, m, p = map(int, sys.stdin.readline().split())

abc = []
# edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, sys.stdin.readline().split())
	abc.append((a-1, b-1, p-c))
	rev_edge[b-1].append(a-1)

def dfs(e, s):
	v_set = {s, }
	stack = [s]

	while stack:
		v = stack.pop()
		for next_v in e[v]:
			if not next_v in v_set:
				stack.append(next_v)
				v_set.add(next_v)
	return v_set

def bellman_ford(sub_abc, n):
	dist = [float('inf')]*n 
	dist[0] = 0

	for _ in range(n):
		updated = False
		for ele in sub_abc:
			a, b, d = ele
			if dist[a] + d < dist[b]:
				dist[b] = dist[a] + d 
				updated = True
		if not updated:
			break
	else:
		return -1

	return max(-dist[n-1], 0)

use = dfs(rev_edge, n-1)
print(bellman_ford([(a, b, c) for a, b, c in abc if a in use and b in use], n))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache

    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
    
    @lru_cache(None)
    def transaction(self, money, stock, i):
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock = stock
        _money = money
        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            # print("buy",money,stock,i)
            self.transaction(money, stock, i + 1)
        # backtracking
        money,stock = _money,_stock

        ## sell
        if stock > 0:
            stock, money = 0, stock * self.prices[i] + money
            if money > 1000:
                self.transaction(money, 0, i + 1)
        # backtracking
        money,stock = _money,_stock

        ## do nothing
        self.transaction(money, stock, i + 1)


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0)
    print(solver._max)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
 

def maxProfit(prices) -> int:
    if len(prices) < 2:
        return 0
    ans = 1000
    for i in range(1,len(prices)):
        if prices[i] > prices[i - 1]:
            stock = ans // prices[i - 1]
            ans += stock * (prices[i] - prices[i - 1]) 
    return ans

def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = maxProfit(A)
    print(ans)


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

N=int(input())
l=list()
for n in range(N):
  A=int(input())
  l.append(A)
  
for n in range(N):
  if l[n]==max(l):
    ll=sorted(l,reverse=True)
    print(ll[1])
  else:
    print(max(l))

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
ll=sorted(A)
a=max(A)
b=ll[-2]
  
for n in A:
  if n==a:
    print(b)
  else:
    print(a)
### BUGGY CODE ###

n,w = map(int,input().split())
v = []
wt = []
for _ in range(n):
    x,y=map(int,input().split())
    wt.append(x)
    v.append(y)
a = [[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n+1):
    for j in range(w+1):
        if i == 0 or j==0:
            a[i][j]=0
        elif wt[i-1]<=j:
            a[i][j]=max(a[i-1][j],(v[i-1]+a[i-1][j-wt[i-1]]))
        else:
            a[i][j]=a[i-1][j]
print(a[n][w])

### FIXED CODE ###

n,w = map(int,input().split())
v = []
wt = []
for _ in range(n):
    x,y=map(int,input().split())
    wt.append(x)
    v.append(y)
a = [[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n+1):
    for j in range(w+1):
        if i == 0 or j==0:
            a[i][j]=0
        elif wt[i-1]<=j:
            a[i][j]=max(a[i-1][j],(v[i-1]+a[i-1][j-wt[i-1]]))
        else:
            a[i][j]=a[i-1][j]
print(a[n][w])
### BUGGY CODE ###

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

def solve(a,b,c,d):
  if a < b or d < b:
    return True

  mi=a-b
  ma=a-c
  cnt=gcd(b,d)
  for i in range(mi+1,ma):
    if i%cnt==0:
      return True
  return False

T=int(input())
for i in range(T):
  A,B,C,D=map(int,input().split())
  if solve(A,B,C,D):
    print("No")
  else:
    print("Yes")
    

### FIXED CODE ###

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

def solve(a,b,c,d):
  if a < b or d < b:
    return True

  cnt=gcd(b,d)
  mi=a-b
  ma=a-c
  if ma-mi > cnt :
    return True
  elif ma-mi <= 1:
    return False
  elif (mi+cnt)//cnt*cnt < ma:
    return True
  else:
    return False

T=int(input())
for i in range(T):
  A,B,C,D=map(int,input().split())
  if solve(A,B,C,D):
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

n,k = map(int,raw_input().split())
jis = [map(int, raw_input().split()) for _ in range(k)]
jis.sort()
dp = [0 for _ in range(n)]
dp[0] = 1
mod = 998244353
for i in range(1,n):
	flag = True
	for u,v in jis:
		if flag is False: break
		for w in range(u,v+1):
			if i-w>=0:
				dp[i] += dp[i - w]
				dp[i] %= mod
			else:
				flag = False
				break
print dp[n-1]

### FIXED CODE ###

n,k = map(int,raw_input().split())
jis = [map(int, raw_input().split()) for _ in range(k)]
jis.sort()

dp = [0 for _ in xrange(n)]
dp[0] = 1
pre = [0 for _ in xrange(n)]
pre[0] = 1
mod = 998244353
for i in range(1,n):
	flag = True
	for u,v in jis:
		uu,vv = i - v, i - u
		
		if vv >= 0:
			dp[i] += pre[vv] - (pre[uu - 1] if uu - 1 >= 0 else 0)
			dp[i] %= mod
	pre[i] += dp[i] + pre[i-1]
	pre[i] %= mod

print dp[n-1]
### BUGGY CODE ###

import os
import sys
from collections import defaultdict
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

import time

st = time.time()

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# グラフつくる
nodes = set()
graph = defaultdict(list)
ins = defaultdict(int)
sources = []
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        a, b = min(a, b), max(a, b)
        c, d = i, A[i][j + 1] - 1
        c, d = min(c, d), max(c, d)

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1
        sources.append(a * N + b)

        nodes.add(a * N + b)
        nodes.add(c * N + d)

# トポロジカルソート
S = []
for v in nodes:
    if ins[v] == 0:
        S.append(v)
L = []
while S:
    if time.time() - st >= 1.98:
        print(-1)
        exit()

    v = S.pop()
    L.append(v)
    for u in graph[v]:
        ins[u] -= 1
        if ins[u] == 0:
            S.append(u)

if len(L) != len(nodes):
    print(-1)
    exit()

seen = []


@lru_cache(maxsize=None)
def dfs(v):
    ret = 0
    for u in graph[v]:
        ret = max(ret, dfs(u))
    return ret + 1


ans = 0
for v in sources:
    ans = max(ans, dfs(v))
print(ans)


### FIXED CODE ###

import os
import sys
from collections import defaultdict, deque
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

N=int(input())
P=list(map(int, input().split()))
a=1
b=0
for i in P:
	Q=P[:a]
	M=min(Q)
	if M==i:
		b+=1
	a+=1
print(b)

### FIXED CODE ###

_ = input()
p = list(map(int, input().split()))
m = float("inf")
c = 0
for i in p:
  c += i <= m
  m = min(m, i)
print(c)
### BUGGY CODE ###

n = int(input())
lst = list(map(int,input().split()))
s = 0
for i in range(n-1):
  for j in range(i+1,n):
    a = (lst[i]*lst[j])% (10**9+7)
    s += a
    
print(s%(10**9+7))    
    



### FIXED CODE ###

import numpy as np
n = int(input())
lst = list(map(int,input().split()))
s = 0
t = 0
for x in lst:
  s += x
  t += (x ** 2) % (10**9+7)

w = (s**2-t) % (10**9+7)
if w % 2 == 0:
  print(w//2)
else:
  print((w+10**9+7)//2)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
arr = list(map(int, input().split())) + [0] * k

INF = 1 << 60

# dp初期化
dp = [INF] * (n + k)
dp[0] = 0

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

print(dp[n - 1])

### FIXED CODE ###

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

# dp初期化
dp = [float("inf")] * n
dp[0] = 0

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

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

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

def main():
    if N == 1:
        return K
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    history = {1}
    stack = d[1]
    b = len(stack)
    if K - 1 < b:
        return 0
    d.pop(1)
    ans = K * perm(K - 1, b)
    a = K - 2
    lim = max([len(x) for x in d.values()])
    if lim - 1 > a:
        return 0
    lim += 1
    perm_list = [None] * lim
    perm_list[0] = 1
    for i in range(1, lim):
        perm_list[i] = perm_list[i-1] * (a + 1 - i)
    while stack:
        node = stack.pop()
        history.add(node)
        ans *= perm_list[len(d[node]) - 1]
        for i in d[node]:
            if i not in history:
                stack.add(i)
    return ans
    
print(main() % 1000000007)

### FIXED CODE ###

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

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)