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

from collections import deque
n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

for kkk in range(n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit = visit.union({a_list[k].popleft(), a_list[j].popleft()})                                              
    if (len(visit) == 0):
        day = -1
        break
    if num >= n * (n - 1) // 2:
        break
print(day)

### FIXED CODE ###

from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)
### BUGGY CODE ###

N,M =[int(i)for i in input().split()]
ko =[[] for i in range(N)]
tyo =set([i for i in range(N)])
for _ in range(N+M-1):
    A,B = [int(i)for i in input().split()]
    tyo = tyo - {B-1}
    ko[A-1].append(B-1)
tyo =list(tyo)
tyouten =tyo[0]
rank =[[-1,-1]for _ in range(N)]
def keisan(num,no,bef):
    if rank[num][0] < no:
        rank[num]=[no,bef]
    else:
        return
    for i in ko[num]:
        keisan(i,no+1,num)

keisan(tyouten,0,-1)
for i in rank:
    print(i[1]+1)

### FIXED CODE ###

import queue
N,M =[int(i)for i in input().split()]
adlist =[[]for i in range(N)] #隣接リスト
oyalist =[[]for i in range(N)] #親ノードリスト
for _ in range(N+M-1):
    A,B =[int(i)-1 for i in input().split()]
    adlist[A].append(B)
    oyalist[B].append(A)

iri =[0]*N #入次数のリスト
for i in range(N):
    iri[i] =len(oyalist[i])

topo =[0]*N #トポロジカルソートの番号
tyouten =oyalist.index([]) #頂点
num = 0 #ソート番号
q =queue.Queue()
q.put(tyouten)
topo[tyouten]=num

while num != N-1:
    now = q.get()
    for i in adlist[now]:
        iri[i] -=1
        if iri[i] == 0:
            q.put(i)
            num += 1
            topo[i] =num

#出力
oyalist[tyouten].append(-1)
for i in range(N):
    oyalist[i] =sorted(oyalist[i],key=lambda x:topo[x],reverse=True)
    print(oyalist[i][0]+1)
### BUGGY CODE ###

H,N=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())

INF=10**9
dp=[INF]*(H+1)
# dp[x]:xダメージを与えるための最小魔力
dp[0]=0
for i in range(N):
  for j in range(len(dp)):
    if dp[j]!=INF:
      if j+A[i]<len(dp):
        if dp[j+A[i]]>dp[j]+B[i]:
          dp[j+A[i]]=dp[j]+B[i]
      else:
        if dp[len(dp)-1]>dp[j]+B[i]:
          dp[len(dp)-1]=dp[j]+B[i]
print(dp[-1])

### FIXED CODE ###

H,N=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())

INF=10**9
dp=[INF]*(H+1)
# dp[x]:xダメージを与えるための最小魔力
dp[0]=0
for i in range(N):
  for j in range(len(dp)):
    if dp[j]!=INF:
      if j+A[i]<len(dp):
        if dp[j+A[i]]>dp[j]+B[i]:
          dp[j+A[i]]=dp[j]+B[i]
      else:
        if dp[len(dp)-1]>dp[j]+B[i]:
          dp[len(dp)-1]=dp[j]+B[i]
print(dp[-1])
### BUGGY CODE ###

S = input()
ans = 0
for i in range(len(S)-3):
    for j in range(i+4, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length
ans = [0] * 2019
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = [i for i in ans if i != 0]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(len(ans_c))]) / 2) + ans[0])
### BUGGY CODE ###

import fractions
n=int(input())
ans=0
for i in range(1,n+1):
    for j in range(i,n+1):
        g=fractions.gcd(i,j)
        for k in range(j,n+1):
            l=fractions.gcd(g,k)
            if i==j and j==k:
                ans+=l
            elif i==j or j==k or k==i:
                ans+=3*l
            else:
                ans+=6*l
print(ans)

### FIXED CODE ###

import fractions
n=int(input())
ans=0
for i in range(1,n+1):
    for j in range(i,n+1):
        g=fractions.gcd(i,j)
        for k in range(j,n+1):
            l=fractions.gcd(g,k)
            if i==j and j==k:
                ans+=l
            elif i==j or j==k or k==i:
                ans+=3*l
            else:
                ans+=6*l
print(ans)
### BUGGY CODE ###

from itertools import combinations
n=int(input())
l=[int(i)for i in input().split()]
l2=list(combinations(l, 3))
sum=0
for i in range(len(l2)):
    a=l2[i][0]
    b=l2[i][1]
    c=l2[i][2]
    if(a<b+c and b<c+a and c<a+b):
        sum+=1
print(sum)

### FIXED CODE ###

import bisect

n = int(input())
l = [int(i) for i in input().split()]
l.sort()

cnt = 0
for a in range(n):
    for b in range(a+1, n):
        c = bisect.bisect_left(l, l[a] + l[b])
        if c > b:
            cnt += c - b - 1
print(cnt)
### BUGGY CODE ###

import sys,bisect
input = sys.stdin.readline
n = int(input())
p = tuple(map(float,input().split()))

dp = [[0.0]*(n+1) for i in range(n+1)]
dp[0][0] = 1.0
for i in range(1,n+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j]*(1-p[i-1])
        if j > 0:
            dp[i][j] += dp[i-1][j-1]*p[i-1]

res = 0.0
for i in range((n+1)//2,n+1):
    res += dp[-1][i]
print(res)

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline
n = int(input())
p = tuple(map(float,input().split()))

dp = [[0.0]*(n+1) for i in range(n+1)]
dp[0][0] = 1.0
for i in range(1,n+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j]*(1-p[i-1])
        if j > 0:
            dp[i][j] += dp[i-1][j-1]*p[i-1]

res = 0.0
for i in range((n+1)//2,n+1):
    res += dp[-1][i]
print(res)
### BUGGY CODE ###

p = int(input())
A = list(map(int,input().split()))
a = list(range(1,p+1))
count = 0
for j,i in zip(a,A):
  if A.count(j) != 0 and i == a[A.index(j)]:
    A.pop(A.index(j))
    count += 1
print(count)

### FIXED CODE ###

p = int(input())
ans = 0
*A,= map(int,input().split())
for j,i in enumerate(A):
  if A[A[j]-1]==j+1:
    ans+=1
print(ans//2)
### BUGGY CODE ###

from collections import deque

s = deque(input())

q = int(input())

for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        s.reverse()
    else:
        if A[1] == '1':
            s.appendleft(A[2])
        else:
            s.append(A[2])
print("".join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())

q = int(input())
r = 0
for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        r = (r + 1)%2
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] == '2' and r % 2 == 1):
            s.appendleft(A[2])
        else:
            s.append(A[2])

if r == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

l = input()
m = l.split(" ")
n = int(m[0])
k = int(m[1])
while (abs(n-k)<n):
  n = abs(n-k)
print(n)


### FIXED CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])

while N>K:
  N = N%K
  
print(min([N,K-N]))
### BUGGY CODE ###

import bisect


class SegTree:

    def __init__(self, n):
        # supposed that n = 2**m
        INF = 10 ** 12
        self.n = n
        self.val = [INF] * (2 * n - 1)

    def _update(self, a, b, v, k, l, r):
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = min(v, self.val[k])
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)

    def update(self, a, b, v):
        # 区間[a, b)上の値がvより大きければvに更新
        self._update(a, b, v, 0, 0, self.n)

    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = min(ret, self.val[k])
        return ret


def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for _ in range(N)]
    # 工事は出発地から近い順に並べておく
    work_list.sort(key=lambda work: work[2])
    D = [int(input()) for _ in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree.update(left, right, w)
    for q in range(Q):
        w = tree.query(q)
        if w >= N:
            print(-1)
        else:
            print(work_list[w][2])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        # 区間[a, b)上の値をvに更新
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for n in range(N)] 
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for q in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree._update(left, right, w, 0, 0, QQ)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    *N, = map(int, open(0).read().split())
    h = N[2:]
    K = N[1]
    N = N[0]

    D = [[] for i in range(0, N)]
    for i in range(0, N):
        for j in range(0, N):
            if not i == j:
                D[i].append(abs(h[i] - h[j]))
        D[i].sort()
    S = []
    for i in range(0, N):
        S.append(sum(D[i][0:K - 1]))

    print(min(S))


main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    *N, = map(int, open(0).read().split())
    h = N[2:]
    K = N[1]
    N = N[0]

    h.sort(reverse=True)
    ans = max(h) - min(h)
    for i in range(0, N - K + 1):
        d = h[i] - h[i + K -1]
        if d < ans:
            ans = d
    print(ans)


main()
### BUGGY CODE ###

import numpy as np

def main():
  N, K = list(map(int, input().split()))
  h = np.asarray(list(map(int, input().split())))

  if N == 2:
    print(abs(h[1] - h[0]))
    exit()
  
  DP = np.full(N, int(10e10), dtype = np.int32)

  mi = min(N, K + 1)
  DP[1: mi] = np.abs(h[1: mi] - h[0])
  for i in range(1, N - 1):
    mi = min(N - 1, i + K + 1)
    T = np.asarray(np.abs(h[i + 1: mi + 1] - h[i]) + DP[i])
    DP[i + 1: mi + 1] = np.where(T < DP[i + 1: mi + 1], T, DP[i + 1: mi + 1])
  print(DP[N-1])
  
main()


### FIXED CODE ###

def main():
  N, K = list(map(int, input().split()))
  h = tuple(map(int, input().split()))

  if N == 2:
    print(abs(h[1] - h[0]))
    exit()

  DP = [0 for i in range(N)]

  mi = min(N, K + 1)
  for i in range(1, mi):
    DP[i] = abs(h[i] - h[0])
  for i in range(1, N - 1):
    mi = min(N, i + K)
    for j in range(i, mi):
      t = DP[i] + abs(h[j] - h[i])
      if DP[j] > t:
        DP[j] = t
    if i + K <= N - 1:
      DP[i+K] = DP[i] + abs(h[i+K] - h[i])
  print(DP[N-1])
  
main()
### BUGGY CODE ###

N,M= map(int,input().split())
gate=[list(map(int,input().split())) for i in range(M)]
count2=0

for i in range(1,N+1):
  count=0
  for j in gate:
    if j[0]<=i<=j[1]:
      count+=1
    else:
      break
  if count==M:
    count2+=1
print(count2)

### FIXED CODE ###

N,M= map(int,input().split())
gate=[list(map(int,input().split())) for i in range(M)]
count2=0

min1=1
max1=N

for j in gate:
  if j[0]>min1:
    min1=j[0]
  if j[1]<max1:
    max1=j[1]
if max1>=min1:
  print(max1-min1+1)
else:
  print(0)
### BUGGY CODE ###

s = input()
t = input()

n = len(s)

if set(list(t)) != (set(list(s)) & set(list(t))): ans = -1
else:
    dct = {}

    for i, ss in enumerate(s):
        if ss in dct:
            dct[ss].append(i)
        else: dct[ss] = [i]

    idx = -1
    ans = 0
    for i, tt in enumerate(t):
        jdg = True
        for j in dct[tt]:
            if idx < j:
                idx = j
                jdg = False
                break
        if jdg:
            idx = dct[tt][0]
            ans += n
    ans += idx + 1

print(ans)

### FIXED CODE ###

from bisect import bisect_right
s = input()
t = input()

n = len(s)

if set(list(t)) != (set(list(s)) & set(list(t))): ans = -1
else:
    dct = {}

    for i, ss in enumerate(s):
        if ss in dct:
            dct[ss].append(i)
        else: dct[ss] = [i]
    idx = -1
    ans = 0
    for tt in t:
        m = bisect_right(dct[tt], idx)
        if m == len(dct[tt]):
            idx = dct[tt][0]
            ans += n
        else:
            idx = dct[tt][m]
    ans += idx + 1

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

n = int(input())
a = []
result = 0
for i in range(n):
    a.append(int(input()))

paper = set(a)
for j in paper:
    count = a.count(j)
    if count % 2 == 1:
        result += 1

print(result)


### FIXED CODE ###

import collections
n = int(input())
a = [int(input()) for _ in range(n)]
result = 0
cnt = collections.Counter(a)
for i in cnt.values():
    if i % 2 == 1:
        result += 1

print(result)
### BUGGY CODE ###

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
counter = set([])
for i in range(n - 1):
    a_np = np.roll(np.array(a), i + 1)
    counter = counter | set(np.where(a % a_np == 0)[0])
print(n - len(counter))

### FIXED CODE ###

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0 for _ in range(a[-1] + 1)]

for x in a:
    for j in range(x, a[-1] + 1, x):
        dp[j] += 1
ans = 0
for x in set(a):
    #print(x)
    if dp[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
e=[ set() for _ in range(n+1) ]
c=[0]*(n+1)
s1=set()
s2=set()
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    s1.add(a)
    s2.add(b)
    e[a].add(b) 

s1=s1-s2
# print(s1)
i=0
q=[ list(s1) ]
while q:
    t=[]
    for lst in q:
        for w in lst:
            if e[w]: t.append(e[w])
            c[w]=i
    q=t
    i=i+1

print(i-1) 

### FIXED CODE ###

n, m = map(int, input().split())
dp=[0]*(n+1)
e=[ set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    e[a].add(b)
    dp[b]+=1

q=[0]*(n+1)
j=0
for z in range(len(dp)):
    if dp[z]==0:
        q[j]=z
        j=j+1
color=0
i=1
while i<j:
    end=j
    for qel in range(i, end):
        for w in e[q[qel]]:
            dp[w]-=1
            if dp[w]==0: 
                q[j]=w
                j=j+1
    i=end
    color=color+1

print(color-1)
### BUGGY CODE ###

from itertools import chain, groupby

def main():
    N,K,Q,*A=map(int,open(0).read().split())
    s=sorted
    print(min((s(chain.from_iterable((v[:max(0,len(v)-K+1)]for v in(k*s(v)for k,v in groupby(A,lambda a:a>=Y)))))[Q-1:]or[2e9])[0]-Y for Y in A))

main()

### FIXED CODE ###

N, K, Q, *A = map(int, open(0).read().split())

ans = float("inf")
for Y in A:
    C = []
    tmp = []
    for a in A:
        if a >= Y:
            tmp.append(a)
        else:
            if len(tmp) >= K:
                C += sorted(tmp)[:len(tmp) - K + 1]
            tmp = []
    if len(tmp) >= K:
        C += sorted(tmp)[:len(tmp) - K + 1]

    if len(C) >= Q:
        C.sort()
        X = C[Q - 1]
        ans = min(ans, X - Y)

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

n = int(input())
s = [sorted(input()) for i in range(n)]

count = 0

for i in range(n):
  c = s[i]
  for j in range(i+1,n):
    if c == s[j]:
      count += 1
      
print(count) 

### FIXED CODE ###

import collections

n = int(input())
s = []
for i in range(n):
  s_ = sorted(input())
  s.append(s_[0]+s_[1]+s_[2]+s_[3]+s_[4]+s_[5]+s_[6]+s_[7]+s_[8]+s_[9])

c = collections.Counter(s)
count = 0

for i in c:
  if c[i] != 1:
    count += c[i]*(c[i]-1)/2

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

n = int(input())
a = list(map(int, input().split()))
 
m = (10**9 + 7)
result = [(a[i]*a[j])%m for i in range(n) for j in range(n) if i < j]
print(sum(result)%m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = (10**9 + 7)

result = 0

sum_a = 0
for i in range(n):
    sum_a = (sum_a + a[i]) % m

result = 0
for i in range(n):
    x = a[i]
    sum_a -= x
    result = (result + x*sum_a) % m

if(result < 0):
    result += m
print(result)
### BUGGY CODE ###

# 2019/04/29
# AtCoder Beginner Contest 085 - C

# Input
n, y = map(int,input().split())

cashl = [1000, 5000, 10000]
ansl = [-1, -1, -1]
eflg = False

# Search AC and make Accumed sum
for i in range(n+1):
    for j in range(0, n+1):
        if i + j > n:
            break
        
        subt = i * cashl[0] + j * cashl[1]
        st = int((y - subt) / 10000)
        
        for k in range(st, n+1):
            total = i * cashl[0] + j * cashl[1] + k * cashl[2]
            bcnt = i + j + k
            if bcnt > n or total > y:
                break
            if total == y and bcnt == n:
                ansl[0] = i
                ansl[1] = j
                ansl[2] = k
                eflg = True
                break
        if eflg == True:
            break
    if eflg == True:
        break

# Output
print(ansl[2], ansl[1], ansl[0])


### FIXED CODE ###

# 2019/04/29
# AtCoder Beginner Contest 085 - C

# Input
n, y = map(int,input().split())

cashl = [10000, 5000, 1000]
ansl = [-1, -1, -1]
eflg = False

# Search AC and make Accumed sum
for i in range(n+1):
    for j in range((n+1)-i):
        subt = i * cashl[0] + j * cashl[1]
        k = int((y - subt) / 1000)

        total = subt + k * cashl[2]
        bcnt = i + j + k

        if total == y and bcnt == n:
            ansl[0] = i
            ansl[1] = j
            ansl[2] = k
            eflg = True
            break

    if eflg == True:
        break

# Output
print(ansl[0], ansl[1], ansl[2])
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 1000000007
nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1
for i in range(2,n+1):
  if i in a: continue
  nums[i] = nums[i-1] + nums[i-2]

print(nums[n]%mod)

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
inf = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0
  
for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] %= inf
  
print(dp[n])
### BUGGY CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[set() for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].add(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            for nxt in dp[i-1][j]:
                dp[i][j] = dp[i][j].union(dp[0][nxt])
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N*3)]
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].add(N*1+v)
        adj[N*1+u].add(N*2+v)
        adj[N*2+u].add(v)
    S, T = map(int, input().split())
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost//3)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


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

def main():
  import sys
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  B = []
  for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
  for i in range(h):
    row = list(map(int, input().split()))
    B.append(row)
 
  dp = [[[0 for k in range(12801)] for j in range(w+1)] for i in range(h+1)]
  dp[0][0][(abs(A[0][0] - B[0][0]))] = 1
  for i in range(h):
    for j in range(w):
      for item, f in enumerate(dp[i][j]):
        if not f:
          continue
        if j < w - 1:
          dif = abs(A[i][j+1] - B[i][j+1])
          dp[i][j+1][item+dif] = 1
          dp[i][j+1][abs(item-dif)] = 1
        if i < h - 1:
          dif = abs(A[i+1][j] - B[i+1][j])
          dp[i+1][j][item+dif] = 1
          dp[i+1][j][abs(item-dif)] = 1
  print(min([k for k, f in enumerate(dp[h-1][w-1]) if f]))
if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()