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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, M = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(N-1+M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    to[A].append(B)
    fr[B].append(A)

depth = [-1] * N

def dfs(v, d):
    depth[v] = max(depth[v], d)
    nd = d + 1
    for nv in to[v]:
        dfs(nv, nd)

root = -1
for v in range(N):
    if len(fr[v]) == 0:
        root = v
        break

dfs(root, 0)

vlist = [[] for _ in range(N)]
for v, d in enumerate(depth):
    vlist[d].append(v)

for v in range(N):
    d = depth[v]
    if d == 0:
        print(0)
        continue
    parent = set(vlist[d-1]) & set(fr[v])
    print(parent.pop()+1)

### FIXED CODE ###

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

N, M = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(N-1+M):
    A, B = map(int,input().split())
    A -= 1; B -= 1
    to[A].append(B)
    fr[B].append(A)

# トポロジカルソート　計算量O(V+E)
# 有向グラフに用いる
# 閉路検出(DAGの判定)やDPの更新順序を明らかにするときなどに使える

# num[i] : iに入ってくる有効辺の本数
num = [0] * N

# グラフの構築でnumを更新しておく
num = [len(fr[v]) for v in range(N)]

S = deque()
L = []
#　例えば-1で初期化 dp = [-1] * N
'''  編集　'''

for v in range(N):
    if num[v] == 0:
        S.append(v)
        # 入次数0の頂点において例えば0で初期化　dp[v] = 0
        '''　編集　'''

while S:
    v = S.popleft()
    L.append(v)
    for nv in to[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
        # dpの更新　例えばmaxをとる dp[nv] = max(dp[nv], dp[v] + w[v])
        ''' 　編集 '''

# 閉路がある場合の処理
if len(L) != N:
    '''  編集　'''
    pass

index = [-1] * N
for i, v in enumerate(L):
    index[v] = i

for v in range(N):
    if v == L[0]:
        print(0)
        continue
    pv = -1
    d = N
    for cand in fr[v]:
        res = index[v] - index[cand]
        if res < d:
            d = res
            pv = cand
    pv += 1
    print(pv)
### BUGGY CODE ###

def main():
    n = int(input())
    As = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            ans += As[i] * As[j]
    ans %= mod
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np


def main():
    n = int(input())
    As = list(map(int, input().split()))
    mod = 10**9 + 7

    As_sum = np.sum(As) % mod
    ans = 0
    for i in range(n):
        As_sum -= As[i]
        As_sum %= mod
        ans += As_sum * As[i]
        ans %= mod
    ans %= mod
    print(ans)


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

import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=max(t[i*2+1],t[i*2+2]) 
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         L = max(L, t[a])
      if b&1==0:
         b-=1
         R = max(t[b], R)
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 j=bisect.bisect_left(dx,dx[i]+dd[i])
 tt=qr(i,j)
 ud(i,max(j-1,tt))
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

def check(S, A, B):
    for i in range(N):
        for j in range(i+1, N):
            # if j + B < N:
            #     b = j + B
            # else:
            #     b = j + B - N
            # if i + B < N:
            #     d = i + B
            # else:
            #     d = i + B - N
            if S[i][j+B-N] != S[j][i+B-N]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(S, 0, i)
print(cnt * N)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

def check(S, A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[i][j] != S[j][i]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(S[i:] + S[:i], 0, i)
print(cnt * N)
### BUGGY CODE ###

num,product = map(int,input().split())

cnt = 1
gcd = 1
while(True):
    cnt += 1
    calc = cnt ** num
    if calc > product:
        break
    elif product % calc == 0:
        gcd = cnt
    else:
        continue
print(gcd)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
from math import sqrt,floor
num,product = map(int,input().split())
cnt = int(sqrt(product) + 2)
dd = defaultdict(int)

for i in range(2,cnt):
    if product % i == 0:
        a = 0
        while product % i == 0:
            a += 1
            product = product // i
        dd[i] = a
if product != 1:
    dd[product] =  1
ans = 1
for p,n in dd.items():
    ans *= pow(p,floor(n/num))
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, s, t))
        cur += 1
    ans = -1
    while q and q[0][2] < d:
        heappop(q)
    if q:
        ans = q[0][0]
    print(ans)



### FIXED CODE ###

import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, t))
        cur += 1
    ans = -1
    while len(q) > 0:
        x, t = q[0]
        if d <= t:
            ans = x
            break
        else:
            heappop(q)
    print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for k in range(n):
    c=0
    b=a.copy()
    a.pop(k)
    for i in range(len(a)):
        for j in range(len(a)):
            if a[i]==a[j] and i!=j:
                c+=1
    print(int(c/2))
    a=b

### FIXED CODE ###

import collections as cl
import numpy as np
n=int(input())
a=list(map(int,input().split()))
b=cl.Counter(a)
a_=np.array(list(b.values()))
c=np.sum(a_*(a_-1)/2)
for k in range(n):
    x=b[a[k]]
    if x==2:
        print(int(c-1))
    elif x==1:
        print(int(c))
    else:
        print(int(c-(x-1)))
### BUGGY CODE ###

n = int(input())
a, b = [0]*n,[0]*n
count = 0
plus = 0
for i in range(n):
    a[i],b[i] = map(int,input().split())

while(n > 0):
    if((a[n-1]+plus)%b[n-1] == 0):
        n -= 1
        continue
    plus+=1
    count += 1

print(count)

### FIXED CODE ###

n = int(input())
a, b = [0]*n,[0]*n
count = 0
for i in range(n):
    a[i],b[i] = map(int,input().split())

while(n > 0):
    n -= 1
    count += (b[n] if (a[n]+count)%b[n]!=0 else 0)-(a[n]+count)%b[n]

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

n,m = map(int,input().split())
para_val = []
for i in range(m) :
    a,b = map(int,input().split())
    para_val.append([a,b])


ans = [[] for i in range(m+1)]
ans[0] = [(i+1) for i in range(n)]
for i in range(m):
    for j in range(len(ans[i])):
        if para_val[i][0] <= ans[i][j] <= para_val[i][1]:
            ans[i+1].append(ans[i][j])
print(len(ans[-1]))


### FIXED CODE ###

n,m = map(int,input().split())
para_val = []
for i in range(m) :
    a,b = map(int,input().split())
    para_val.append([a,b])

migi = []
hidari = []
for i,j in para_val:
    migi.append(i)
    hidari.append(j)

a = max(migi)
b = min(hidari)

if b - a >= 0 : print("{}".format(b-a+ 1))
else : print("0")
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
while True:
    a = sorted(list(set(a)))
    tmp = sorted(a[:])
    for i in tmp:
        if i == a[0]:
            continue
        elif i % a[0] == 0:
            a.remove(i)
        else:
            a.append(i % a[0])
            a.remove(i)
    if len(a) == 1:
        break
print(a[0])


### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
while True:
    a = sorted(list(set(a)))
    tmp = sorted(a[:])
    for i in tmp:
        if i == a[0]:
            continue
        elif i % a[0] == 0:
            a.remove(i)
        else:
            a.append(i % a[0])
            if i % a[0] == 1:
                print(1)
                exit()
            a.remove(i)
    if len(a) == 1:
        break
print(a[0])
### BUGGY CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10000)
from functools import lru_cache

@lru_cache(maxsize=100000)
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

@lru_cache(maxsize=100000)
def gcd3(a,b,c):
   return gcd(gcd(a,b),c)

n = int(stdin.readline().rstrip())

sum = 0

for i in range(n):
    for j in range(n):
        for k in range(n):
            a,b,c = sorted((i+1,j+1,k+1))
            sum += gcd3(a,b,c)

print(sum)


### FIXED CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10000)
import functools
from functools import lru_cache

#from math import gcd

@lru_cache(maxsize=1000000)
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def gcdn(nums):
    return functools.reduce(gcd, nums)

@lru_cache(maxsize=1000000)
def gcd3(a,b,c):
   return gcd(gcd(a,b),c)

n = int(stdin.readline().rstrip())

sum = 0
for i in range(n):
    sum += (i+1)
    for j in range(i+1,n):
        sum += 6*gcd(i+1,j+1)
        for k in range(j+1,n):
            #a,b,c = sorted((i+1,j+1,k+1))
            a,b,c = (i+1,j+1,k+1)
            sum += 6*gcdn((a,b,c))

print(sum)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(h, 3501):
        p = N * h * n
        q = 4 * h * n - N * h - N * n
        if q > 0 and p % q == 0:
            w = int(p / q)
            print(str(h) + ' ' + str(n) + ' ' + str(w))
            exit()

### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(h, 3501):
        q = 4 * h * n - N * h - N * n
        if q <= 0:
            continue
        p = N * h * n
        if p >= q and p % q == 0:
            w = int(p / q)
            print(str(h) + ' ' + str(n) + ' ' + str(w))
            exit()
### BUGGY CODE ###

k,s = map(int,input().split())
n = 0
for x in range(k+1):
    for y in range(k+1):
        xy = x+y
        z = s-(xy)
        if z < 0:
            z = 0
        elif z > k:
            z = k
        if xy+z==s:
            n += 1
                
print(n)
                

### FIXED CODE ###

k,s = map(int,input().split())
n = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-(x+y)
        if z <= k and z >= 0 and x+y+z==s:
            n += 1
print(n)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[0]*n
tmp=1
for i in range(k):
  tmp*=a[i]
  b[i]=tmp
for i in range(k,n):
  tmp*=a[i]
  tmp/=a[i-k]
  b[i]=tmp
  print('Yes' if b[i]>b[i-1] else 'No')

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
for i in range(k,n):
  print('Yes' if a[i]>a[i-k] else 'No')
### BUGGY CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count):
    S_list.reverse()
print(*S_list,sep="")


### FIXED CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")
### BUGGY CODE ###

import collections

s = input()
slen = len(s)
swox = s.replace('x','')
swox_rev = swox[::-1]
if swox != swox_rev:
    print(-1)
else:
    sl = list(s)
    sl_inv = list(s[::-1])
    cnt = 0
    while sl:
        if sl[0]== sl_inv[0]:
            sl.pop(0)
            sl_inv.pop(0)
        elif sl[0] == 'x' and sl_inv[0] !='x':
            sl.pop(0)
        elif sl[0] != 'x' and sl_inv[0] == 'x':
            cnt += 1
            sl_inv.pop(0)
        if sl_inv ==[]:
            break
        #print(sl,sl_inv,cnt)
    print(cnt+len(sl_inv))


### FIXED CODE ###

import collections

s = input()
slen = len(s)

sl = collections.deque(list(s))
sl_inv = collections.deque(list(s[::-1]))
cnt = 0
while len(sl)>0:
    if sl[0]== sl_inv[0]:
        sl.popleft()
        sl_inv.popleft()
    elif sl[0] == 'x' and sl_inv[0] !='x':
        sl.popleft()
    elif sl[0] != 'x' and sl_inv[0] == 'x':
        cnt += 1
        sl_inv.popleft()
    elif sl[0] != 'x' and sl_inv[0] != 'x' and sl[0]!=sl_inv[0]:
        print(-1)
        exit()
    if len(sl_inv) ==0:
        break
    #print(sl,sl_inv,cnt)
print(cnt+len(sl_inv))
### BUGGY CODE ###

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

from collections import deque
P_dq = deque(P, N)

P_sum = P
for i in range(K-1):
    P_dq.append(0)
    P_sum = list(map(sum, zip(P_sum, P_dq)))

max_sum = max(P_sum)

max_E = (max_sum + K) / 2
print(max_E)

### FIXED CODE ###

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

# 期待値
E = [(p+1)/2 for p in P]
#print(E)

# 累積和
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + E[i]
#print(S)

# 隣接K個を取り出して足す
max_E = 0
for i in range(N-K+1):
    tmp_E = S[i+K] - S[i]
    #print(tmp_E)
    if tmp_E > max_E:
        max_E = tmp_E

print(max_E)
### BUGGY CODE ###

from scipy.misc import comb

N = int(input())
num_list = list(map(int, input().split()))
num_set = set(num_list)

# 全数あるときの組み合わせ
ans_dict_1 = {}
# 1個抜いたときの組み合わせ
ans_dict_2 = {}

for i in num_set:
  ans_dict_1[i] = comb(num_list.count(i),2,exact=True)
  ans_dict_2[i] = comb(num_list.count(i)-1,2,exact=True)

for i in num_list:
  print(sum(ans_dict_1.values()) - ans_dict_1[i] + ans_dict_2[i])

### FIXED CODE ###

from scipy.misc import comb
from collections import Counter
import datetime

N = int(input())
num_list = list(map(int, input().split()))
# num_set = set(num_list)
num_dict = {}

num_counter = Counter(num_list)
  
# 全数あるときの組み合わせ
ans_dict_1 = {}
# 1個抜いたときの組み合わせ
ans_dict_2 = {}
rap_2 = datetime.datetime.now()
for k, v in num_counter.most_common():
  ans_dict_1[k] = comb(v,2,exact=True)
  ans_dict_2[k] = comb(v-1,2,exact=True)

total = sum(ans_dict_1.values())

for i in num_list:
  print(total - ans_dict_1[i] + ans_dict_2[i])
### BUGGY CODE ###

from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
kurai = 1
for i in range(len(S) - 1, -1, -1):
    # s += int(S[i]) * ((10 ** (len(S) - 1 - i)) % 2019)
    # s %= 2019
    if i == len(S) - 1:
        s += int(S[i]) * kurai
    else:
        s += int(S[i]) * kurai
    kurai *= 10
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)


### FIXED CODE ###

from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
kurai = 1
for i in range(len(S) - 1, -1, -1):
    # s += int(S[i]) * ((10 ** (len(S) - 1 - i)) % 2019)
    # s %= 2019
    if i == len(S) - 1:
        s += int(S[i]) * kurai
    else:
        s += int(S[i]) * kurai
    kurai *= 10
    kurai %= 2019
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)
### BUGGY CODE ###

def remove(ref_list, target):
    # リスト内部からtargetを削除する
    ref_list.remove(target)
    return ref_list[0]


    # 友達関係の把握
[N, M] = list(map(int, input().split()))
relations_list = []
for i in range(M):
    relations_list.append(list(map(int, input().split())))
relations_list = list(map(sorted, relations_list))
# グループ分け
remain_list = list(range(1, 1+N))
group_list = []
while remain_list != []:
    # グループ構成員を求める
    group = []
    group.append(remain_list[0])
    search_list = []
    search_list.append(remain_list[0])
    while search_list != []:
        search = search_list.pop(0)
        # searchに関わるrelationの抽出
        candidate_relations = [
            relation for relation in relations_list if search in relation]
        # 今後検索しないため，relations_listからcandidate_relationsを削除
        for candidate_relation in candidate_relations:
            relations_list.remove(candidate_relation)
        candidate_list = [remove(i, search) for i in candidate_relations]
        search_list.extend(candidate_list)
        group.extend(candidate_list)
        # 検索候補とグループ内部の重複をなくす
        search_list = list(set(search_list))
        group = list(set(group))
    for student in group:
        remain_list.remove(student)
    group_list.append(group)

# 最小グループ数の求め
print(max([len(group) for group in group_list]))


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
n,m = map(int, input().split())

uf = UnionFind(n)

for i in range(m):
    a,b = map(int, input().split())
    uf.union(a-1, b-1)
ans = 0
roots = uf.roots()
cnt = []
for r in roots:
    cnt.append(uf.size(r))
cnt.sort(reverse=True)
ans = cnt[0]
print(ans)
### BUGGY CODE ###

from collections import deque

N = int(input())
ad = [[] for _ in range(N*N)]
num = [0] * (N*N)

for i in range(N):
    a = [int(e)-1 for e in input().split()]
    for k in range(N-2):
        j = a[k]
        nj = a[k+1]
        v = N*max(i,j) + min(i,j)
        nv = N*max(i,nj) + min(i,nj)
        ad[v].append(nv)
        num[nv] += 1

S = deque()
L = []

for v in range(N*N):
    if num[v] == 0:
        S.append((v,1))

while S:
    v, d = S.popleft()
    L.append(d)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append((nv, d+1))

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

ans = max(L)
print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())
ad = [[] for _ in range(N*N)]
num = [0] * (N*N)

for i in range(N):
    a = [int(e)-1 for e in input().split()]
    for k in range(N-2):
        j = a[k]
        nj = a[k+1]
        v = N*max(i,j) + min(i,j)
        nv = N*max(i,nj) + min(i,nj)
        ad[v].append(nv)
        num[nv] += 1

S = deque()
L = []

for v in range(N*N):
    if num[v] == 0:
        S.append((v,1))

while S:
    v, d = S.popleft()
    L.append(d)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append((nv, d+1))

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

ans = max(L)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)


N, M = map(int, input().split())
x, y, z = [], [], []
for _ in range(N):
    xyz = list(map(int, input().split()))
    x += [xyz[0]]
    y += [xyz[1]]
    z += [xyz[2]]


def func(i, j, fx, fy, fz, v):
    if i > N - 1 or j > M - 1:
        return v
    r1 = func(i + 1, j + 1, fx + x[i], fy + y[i], fz + z[i],
              abs(fx + x[i]) + abs(fy + y[i]) + abs(fz + z[i]))
    r2 = func(i + 1, j, fx, fy, fz, v)
    v = max(r1, r2)
    return v


print(func(0, 0, 0, 0, 0, 0))


### FIXED CODE ###

N, M = map(int, input().split())
xyz = []
ans = 0
for _ in range(N):
    xyz += [list(map(int, input().split()))]
for b in range(2 ** 3):
    pm = [1] * 3
    for j in range(3):
        if (b >> j) & 1:
            pm[j] *= -1
    r = []
    for i in range(N):
        r += [pm[0] * xyz[i][0] + pm[1] * xyz[i][1] + pm[2] * xyz[i][2]]
    r.sort(reverse=True)
    ans = max(ans, sum(r[:M]))
print(ans)
### BUGGY CODE ###

S=input()
for i in range(1,100000)[::-1]:
    s = "S"*i +"T"*i
    while s in S:
        S=S.replace(s,"")
print(len(S))

### FIXED CODE ###

from collections import deque
S=list(map(lambda x: 1 if x=="T" else 0,input()))

q=deque()

for i in S:

    if i:
        if (not q) or q[-1]!=0:
            q.append(i)
        elif q and q[-1]==0:
            q.pop()
    else:
        q.append(i)
print(len(q))
### BUGGY CODE ###

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

for i in range(n+1):
    for j in range(2000-i+1):
        for k in range(2000-i-j+1):
            if i+j+k == n and i*10000 + j * 5000 + k * 1000 == y:
                print(i,j,k)
                exit()

print(-1,-1,-1)



### FIXED CODE ###

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

for i in range(y//10000+1):
    if i > n:
        break
    for j in range((y-i*10000)//5000+1):
        if i + j > n:
            break
        if i * 10000 + j * 5000 + (n-i-j) * 1000 == y:
            print(i,j,n-i-j)
            exit()

print(-1,-1,-1)