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

import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
    if not update:
        break
    if count == N and b == N:
        print("inf")
        sys.exit()

print(-distance[N - 1])

### FIXED CODE ###

import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

for n in range(N):
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            if b == N and n == N - 1:
                print("inf")
                sys.exit()

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

import sys

def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v

# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))

# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]

# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))

# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])

# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))

### FIXED CODE ###

import sys
 
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
 
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
 
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
 
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
 
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
 
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))
### BUGGY CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())

n = I()
s = list(S())

ans = 0
for i in range(len(s)-2):
    color = {s[i]}
    for j in range(i+1,len(s)-1):
        if not s[j] in color:
            color.add(s[j])
            for k in range(j+1,len(s)):
                if not s[k] in color:
                    if k-j != j-i:
                        ans += 1
            color = {s[i]}

print(ans)

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
 
n = I()
s = list(S())

r = s.count('R')
g = s.count('G')
b = s.count('B')
 
ans = r*g*b
for i in range(n-1):
    for j in range(1,n):
        if i-j<0 or n<=i+j:
            break
        else:
            if s[i-j]!=s[i] and s[i]!=s[i+j] and s[i-j]!=s[i+j]:
                ans-=1
 
print(ans)
### BUGGY CODE ###

e,M=enumerate,10**9+7
n,k,*a=map(int,open(0).read().split())
dp=[[0]*(k+1)for _ in range(n+1)]
dp[0][0]=1
for i,(b,d,a)in e(zip(dp,dp[1:],a),1):
  t=0
  for j,v in e(b):
    t+=v
    if j>a:t-=b[~a+j]
    t%=M
    d[j]=t
print(t)

### FIXED CODE ###

def main():
  e,M=enumerate,10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[0]*(k+1)for _ in range(n+1)]
  dp[0][0]=1
  for i,(b,d,a)in e(zip(dp,dp[1:],a),1):
    t=0
    for j,v in e(b):
      t+=v
      if j>a:t-=b[~a+j]
      t%=M
      d[j]=t
  print(t)
main()
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
count = [0] * n
MAX = 0
for j in range(n):
	for i in range(j,n-1):
		if h[i] >= h[i+1]:
			count[j] += 1
		else:
			i = j
			break

for i in range(n):
	if MAX < count[i]:
		MAX = count[i]
	i = count[i] + 2

print(MAX)


### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
count = [0] * n
MAX = 0

j = 0
for i in range(j,n-1):
	if h[i] >= h[i+1]:
		count[j] += 1
	else:
		j += 1

for i in range(n):
	if MAX < count[i]:
		MAX = count[i]
	i = count[i] + 2

print(MAX)
### BUGGY CODE ###

D, G = map(int, input().split())
problems = []
for i in range(D):
    b = (i + 1) * 100
    p, c = map(int, input().split())
    problems.append((b, p, c))  # 基本点, 問題数, ボーナス

nsolved = {0: 0}  # 総合点 → 必要問題数

for b, p, c in problems:
    nsolved2 = {}
    for k in nsolved:
        for n in range(p + 1):
            s = b * n + (0 if n < p else c)  # n問解いたときの総合点
            g = min(k + s, G)                # 総合点
            if g not in nsolved2:
                nsolved2[g] = nsolved[k] + n
            else:
                nsolved2[g] = min(nsolved2[g], nsolved[k] + n)
    nsolved = nsolved2

print(nsolved[G])


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
from math import ceil
 
D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)
 
def minsolve(G, p, c, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return float('inf')
    n = min(ceil(G / (100 * i)), p[i-1])
    s = 100 * i * n
    if n == p[i-1]:
        s += c[i-1]
    if s >= G:
        return min(n, minsolve(G, p, c, i-1))
    else:
        return min(n + minsolve(G - s, p, c, i-1), minsolve(G, p, c, i-1))
 
m = min(minsolve(G, p, c, i) for i in range(1, D+1))
print(m)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for j in range(min(k, 41)):
  b = [0]*n
  for i in range(n):
    l = max(0, i-a[i])
    r = min(n, i+a[i]+1)
    b[l] += 1
    if r < n:
      b[r] -= 1
  for i in range(1, n): 
    b[i]+=b[i-1]
  a = b

print(" ".join(list(map(str, a))))
      
  


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for j in range(min(k, 41)):
  b = [0]*n
  for i in range(n):
    l = max(0, i-a[i])
    r = min(n, i+a[i]+1)
    b[l] += 1
    if r < n:
      b[r] -= 1
  for i in range(1, n): 
    b[i]+=b[i-1]
  a = b

print(" ".join(list(map(str, a))))
### BUGGY CODE ###

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

    ln[i]=list(range(ln[i][0],ln[i][1]+1))

nxl=ln[0]
for i in range(1,m):
    nxl=set(nxl)&set(ln[i])
print(len(list(nxl)))


### FIXED CODE ###

n,m=map(int,input().split())
l=[]
r=[]
t=[]
for i in range(m):
    t.append(list(map(int,input().split())))
    l.append(t[i][0])
    r.append(t[i][1])

print(max(min(r)-max(l)+1,0))
### BUGGY CODE ###

S=input()
Q=int(input())

for i in range(Q):
  a=input().split()
  if a[0]=="1":
    S=S[::-1]
  else:
    if a[1]=="1":
      S=a[2]+S
    else:
      S=S+a[2]
      
print(S)

### FIXED CODE ###

S=input()
Q=int(input())
import sys
from collections import deque
d=deque()
for _ in S:
  d.append(_)
flag=False

for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    if flag:
      flag=False
    else:
      flag=True
  else:
    if s[2]=="1":
      if flag:
        d.append(s[4])
      else:
        d.appendleft(s[4])
    else:
      if flag:
        d.appendleft(s[4])
      else:
        d.append(s[4])
      
if flag:
  d.reverse()
  
print("".join(d))
### BUGGY CODE ###

N = int(input())
inputData = input().split()
A = [int(x) for x in inputData]

B = [0] * N
ans = ''
for i, num in enumerate(A):
    B[num-1] = i + 1
for j in B:
    ans = ans + ' ' + str(j)
print(ans[1:])

### FIXED CODE ###

N = int(input())
inputData = input().split()
A = [int(x) for x in inputData]

B = [0] * N
ans = ''
for i, num in enumerate(A):
    B[num-1] = i + 1
print(' '.join(map(str, B)))
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = 0
sum_a = [0]
for i in range(n):
  if t + a[i] <= k:
    t += a[i]
    sum_a.append(t)
  else:
    break
sum_b = [0]
t = 0
for i in range(m):
  if t + b[i] <= k:
    t += b[i]
    sum_b.append(t)
  else:
    break

ans = []
for i in range(len(sum_a)):
  for j in range(len(sum_b)):
    if sum_a[i] + sum_b[len(sum_b) - j - 1] <= k:
      ans.append(i + len(sum_b) - j - 1)
      break
print(max(ans))

### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = 0
sum_a = [0]
for i in range(n):
  if t + a[i] <= k:
    t += a[i]
    sum_a.append(t)
  else:
    break
sum_b = [0]
t = 0
for i in range(m):
  if t + b[i] <= k:
    t += b[i]
    sum_b.append(t)
  else:
    break
ans = []
j = 0
for i in range(len(sum_a)):
  while sum_a[i] + sum_b[len(sum_b) - j - 1] > k:
    j += 1
  ans.append(i + len(sum_b) - j - 1)
print(max(ans))
### BUGGY CODE ###

from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in S[::-1]:
  t = int(s)%mod
  t *= d
  r += t
  r %= mod
  d *= 10
  p[r] += 1

#p.append(0)
#ans = 0
#c = Counter(p)
#for k,n in c.most_common():
#  if n > 1:
#    ans += 1
#  else:break
  
print(sum([i*(i-1)//2 for i in p]))

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

In = input().split(" ")
T = int(In[0])
A = int(In[1])
K = int(In[2])
 
if K>=T+A:
  print("0 0")
else:
  if (K > T):
    print("0 {0}".format(A-(K-T)))
  elif (T > K):
    print("{0} {1}".format(T-K, A))
  else:
    for i in range(K):
      if T >= 1:
        T -= 1
      else:
        if A >= 1:
          A -= 1
        else:
          break
    print("{0} {1}".format(T, A))

### FIXED CODE ###

In = input().split(" ")
T = int(In[0])
A = int(In[1])
K = int(In[2])
 
if K <= T:
  print("{0} {1}".format(T-K,A))
elif K <= T+A:
  print("0 {0}".format(A-(K-T)))
else:
  print("0 0")
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

print(max(ans))



### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    vis[u] = True
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
        vis[u] = True

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

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

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
a = Counter(A)
b = list(a.keys())
B = [-1]*(N+1)

for i in range(N):
  count = 0
  k = A[i]
  if B[k] != -1:
    print(int(B[k]))
  else:
    for j in b:
      if j == k:
        count += (a[j]-1)*(a[j]-2)/2
      else:
        count += a[j]*(a[j]-1)/2
    B[k] = count
    print(int(count))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
a = Counter(A)
b = list(a.keys())
B = [0]*(N+1)
for i in b:
  B[i] = int(a[i]*(a[i]-1)/2)
total = sum(B)

for i in range(N):
  k = A[i]
  change = (a[k]-1)*(a[k]-2)/2
  print(int(total-B[k]+change))
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(N):
    for j in reversed(range(i+1, N)):
        if len(S[i:j]) <= ans:
            break
        #print(S[i:j], S[j:])
        if S[i:j] in S[j:]:
            ans = max(ans, len(S[i:j]))
            break
print(ans)
    
    


### FIXED CODE ###

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for j, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()
### BUGGY CODE ###

# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))

total = 0
comb = np.zeros(N)
comb_idx = 0

while comb_idx < 2**N:
  tmp = bin(comb_idx)[2:]
  comb[-len(tmp):] = np.array(list(map(int, list(tmp))))
  if np.dot(A, comb) == S:
    R = 1
    while True:
      if tmp[-R] == "1":
        break
      else:
        R += 1
    total += (N-len(tmp)+1) * R
    comb_idx += 1
  else:
    comb_idx += 1
print(total % 998244353)

### FIXED CODE ###

# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
  if A[n] < S:
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
  dt[n,:] %= 998244353
print(dt[N,S] % 998244353)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main(N,K,A,B):
    while(0<K):
        tmp = min(A)
        idx = A.index(min(A))
        K -= B[idx]
        A.pop(idx)
        B.pop(idx)
    print(tmp)
    
if __name__ == '__main__':
    N, K = map(int, input().split())
    A, B = [], []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    main(N,K,A,B)

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main(N,K,A):
    A = sorted(A, key=lambda x:x[0])
    tmp = A[0][0]
    for a, b in A:
        tmp = a
        if(0<K-b):
            K -= b
        else:
            print(tmp)
            break
    
if __name__ == '__main__':
    N, K = map(int, input().split())
    A = [[int(i) for i in input().split()] for i in range(N)]
    main(N,K,A)
### BUGGY CODE ###

k, s = input().split()
k, s = int(k), int(s)
ans = 0
for x in range(0, k+1):
  for y in range(0, k+1):
    for z in range(0, k+1):
      if x+y+z==s:
        ans += 1
print(ans)

### FIXED CODE ###

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

# coding: utf-8
# Your code here!
n = int(input())

timelist =list(map(int,input().split()))

for i in range(n):
    for j in range(len(timelist)):
        if(timelist[j]==i+1):
            print(j+1,end=" ")
        

### FIXED CODE ###

n = int(input())

timelist =list(map(int,input().split()))
numberList = ["."]*n
for i in range(len(timelist)):
    numberList[timelist[i]-1]=str(i+1)
for a in numberList:
    print(a,end=" ")
### BUGGY CODE ###

from itertools import combinations
from functools import lru_cache
import math


@lru_cache(maxsize=None)
def solve(a, b):
    x = a * b
    return x - int(x) == 0


n = int(input())
arr = [float(input()) for _ in range(n)]
arr = [x for x in arr if min(x - int(x), math.ceil(x) - x) >= 0.000005 or x == int(x)]

ans = []
for x, y in combinations(arr, 2):
    ans.append(solve(x, y))

print(sum(ans))

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

from collections import deque

INF = float('inf')

dr = (-1, 0, 0, 1)
dc = (0, -1, 1, 0)

H, W = map(int, input().split())

s = []
total_white_count = 0
for _ in range(H):
    t = tuple(map(lambda x: 1 if x == '.' else 0, list(input())))
    s.append(t)
    total_white_count += sum(t)
p = [[INF for _ in range(W)] for _ in range(H)]

ans = -1

dq = deque()
dq.append((0, 0, 1))
while dq:
    r, c, d = dq.pop()

    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        nd = d + 1
        if not (0 <= nr < H and 0 <= nc < W): continue
        if s[nr][nc] == 0 : continue
        if p[nr][nc] <= nd: continue
        p[nr][nc] = nd
        if nr == H - 1 and nc == W - 1:
            ans = total_white_count - nd
            break
        dq.append((nr, nc, nd))

print(ans)


### FIXED CODE ###

from collections import deque

INF = float('inf')

dr = (-1, 0, 0, 1)
dc = (0, -1, 1, 0)

H, W = map(int, input().split())

s = []
total_white_count = 0
for _ in range(H):
    t = input()
    s.append(t)
    total_white_count += t.count('.')
p = [[INF for _ in range(W)] for _ in range(H)]

ans = -1

dq = deque()
dq.append((0, 0, 1))
while dq:
    r, c, d = dq.popleft() # 直した

    nd = d + 1
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if not (0 <= nr < H and 0 <= nc < W): continue
        if s[nr][nc] == '#' : continue
        if p[nr][nc] <= nd: continue
        p[nr][nc] = nd
        if nr == H - 1 and nc == W - 1:
            ans = total_white_count - nd
            break
        dq.append((nr, nc, nd))
    else:
        continue
    break

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

def t(a):
    b = 0
    n = 0
    while n < len(a):
        if a[n] == n + 1:
            n += 1
        else:
            a.pop(n)
            b += 1
    return b if len(a) != 0 else -1


if __name__ == '__main__':
    n = input()
    a = list(map(int, input().split()))
    print(t(a))


### FIXED CODE ###

def t(a):
    b = [False] * len(a)
    c = 1
    for i, j in enumerate(a):
        if j == c:
            b[i] = True
            c += 1

    return b.count(False) if any(b) else -1


if __name__ == '__main__':
    n = input()
    a = list(map(int, input().split()))
    print(t(a))
### BUGGY CODE ###


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

CN = C
DN = D
while True:
    if CN % D == 0:
        break
    CN += C

CD = CN

#print(CD)

C_count = B//C - (A-1)//C 
D_count = B//D - (A-1)//D
CD_count = B//CD - (A-1)//CD 



#print(C_count, D_count, CD_count)

print(B - A + 1 - C_count - D_count + CD_count)

### FIXED CODE ###


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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)


CD = lcm(C, D)

#print(CD)

C_count = B//C - (A-1)//C 
D_count = B//D - (A-1)//D
CD_count = B//CD - (A-1)//CD 



#print(C_count, D_count, CD_count)

print(B - A + 1 - C_count - D_count + CD_count)
### BUGGY CODE ###

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
for ii in range(5000):
  player_in_this_game = set()
 
  for m in range(n): #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun:
        if m in player_in_this_game or teki - 1 in player_in_this_game:
          #自分または相手に既に試合が組まれている
          pass
        else: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
          a[m].popleft() #自分の予定を消す
          a[teki - 1].popleft() #相手の予定を消す
          player_in_this_game.add(m) #自分を試合中にする
          player_in_this_game.add(teki - 1) #相手を試合中にする
          nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()