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

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v):
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return d

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

ans = 0
for v in range(ls):
  if B[v]:
    tmp = max(dfs(pt,v))
    if tmp>ans:
      ans = tmp

print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

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

import heapq

N, M, S = map(int, input().split())
Cost = [[[-1, -1] for _ in range(N)] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
for i in range(M):
    u, v, a, b = map(int, input().split())
    Cost[u-1][v-1][0] = a
    Cost[u-1][v-1][1] = b
    Cost[v-1][u-1][0] = a
    Cost[v-1][u-1][1] = b
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d

def dijkstra(N, start, Cost, Change):
    minHeap = []
    used = [10**12]*N
    used[start] = 0
    heapq.heappush(minHeap, (0, S, start))

    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        j = 1
        for i in range(N):
            if used[i] > c:
                j = 0
                break
        if j == 1:
            break
        for road in range(N):
            if Cost[current][road][0] != -1:
                if used[road] > c + Cost[current][road][1] and hold >= Cost[current][road][0]:
                    used[road] = c + Cost[current][road][1]
                if hold >= Cost[current][road][0]:
                    heapq.heappush(minHeap, (c + Cost[current][road][1], hold - Cost[current][road][0], road))
        if hold + Change[current][0] <= 2500:
            heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return used

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(i)


### FIXED CODE ###

import heapq

N, M, S = map(int, input().split())
Cost = [[] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
A_m = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    A_m = max(A_m, a)
    Cost[u-1].append([v-1, a, b])
    Cost[v-1].append([u-1, a, b])
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d
if S > A_m*N:
    S = A_m*N

def dijkstra(N, start, Cost, Change):
    rich = [[] for _ in range(N+1)]
    Ans = [10**18]*N
    Ans[0] = 0
    minHeap = []
    used = [[10**18]*(A_m*N + 1) for _ in range(N)]
    used[start][S] = 0
    heapq.heappush(minHeap, (0, S, start))
    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        if rich[current] and rich[current][-1] >= hold:
            continue
        rich[current].append(hold)
        j = 1
        for i in range(N):
            if Ans[i] > c:
                j = 0
                break
        if j == 1:
            break
        for P in Cost[current]:
            road, a, b = P
            if hold >= a:
                if used[road][hold - a] > c + b:
                    used[road][hold - a] = c + b
                    heapq.heappush(minHeap, (c + b, hold - a, road))
                if Ans[road] > c + b:
                    Ans[road] = c + b
        if hold + Change[current][0] <= A_m*N:
            if used[current][hold + Change[current][0]] > c + Change[current][1]:
                heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return Ans

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(i)
### BUGGY CODE ###

import fractions
k = int(input())

sum = 0
for x1 in range(1,k+1):
  for x2 in range(1,k+1):
    for x3 in range(1,k+1):
      for i in range(1, 2):
        ans = fractions.gcd(x1,x2)
        ans = fractions.gcd(ans,x3)
        sum += ans

print(sum)

### FIXED CODE ###

import fractions
k = int(input())

l = [[-1 for _ in range(k+1)] for _ in range(k+1)]

for i in range(1,k+1):
  for j in range(1,k+1):
     if l[i][j] == -1:
        ans = fractions.gcd(i,j)
        l[i][j] = ans
        l[i][i] = ans
sum = 0
#1種類
for i in range(1,k+1):
  sum += i
#２種類
for i in range(1,k):
  for j in range(i+1,k+1):
    sum += l[i][j]*6

#3種類
for i in range(1,k-1):
  for j in range(i+1,k):
    for m in range(j+1,k+1):
      sum += l[l[i][j]][m]*6

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

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

for i in range(k):
    if len(li) > 0:
        m = li.index(max(li))
        li.pop(m)

print(sum(li))

### FIXED CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
ls = sorted(li, reverse=True)
if k >= len(li):
    print(0)
else:
    print(sum(ls[k:]))
### BUGGY CODE ###

n,m=(int(i) for i in input().split())
a=[]
b=[]
for i in input().split():
  a.append((int(i)+1)/2)
for i in range(n-m+1):
  l=sum(a[i:i+m])
  b.append(l)
print(max(b))

### FIXED CODE ###

n,m=(int(i) for i in input().split())
l=[]
for i in input().split():
  l.append((int(i)+1)/2)
s=sum(l[0:m])
maxe=s
for i in range(n-m):
  s+=l[m+i]
  s-=l[i]
  if s>maxe:
    maxe=s
print(maxe)
### BUGGY CODE ###

n = int(input())
s = [str(input()) for i in range(n)]
ss = [sorted(i) for i in s]
ans = 0 
for i in range(n):
    for j in range(i+1,n):
        b = 0
        for k in range(9,-1,-1):
            if ss[i][k] != ss[j][k]:
                b = 1
                break
        if b == 0:    
            ans += 1
                
print(ans)

### FIXED CODE ###

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

ss = [''.join(sorted(i)) for i in s]
ans = 0
key_dict = {}

for i in ss:
    if i in key_dict:
        key_dict[i] += 1
    else:
        key_dict[i] = 1

a = key_dict.values()
al = [i * (i-1) / 2 if i > 1 else 0 for i in a]

ans = int(sum(al))
print(ans)
### BUGGY CODE ###

abc = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
s = input()
x = [[-1 for i in range(26)] for j in range(len(s))]
for k in range(2):
    for i in range(len(s)-1,-1,-1):
        if i == 0:
            ib = len(s)-1
        else:
            ib = i-1
        for j in range(26):
            if j == ord(s[i])-97:
                x[ib][j] = i
            else:
                x[ib][j] = x[i][j]
t = input()
i = len(s)-1
count = 0
for j in range(len(t)):
    nxt = x[i][ord(t[j])-97]
    if nxt == -1:
        print(-1)
        exit()
    elif nxt <= i:
        count += 1
        i = nxt
    else:
        i = nxt
print(len(s)*(count-1)+i+1)


### FIXED CODE ###

s = input()
ns = len(s)
x = {}
for i in range(len(s)):
    if s[i] in x:
        x[s[i]] += [i]
    else:
        x[s[i]] = [i]
t = input()
i = len(s)-1
count = 0
import bisect
for j in range(len(t)):
    if t[j] in x:
        ni = bisect.bisect_right(x[t[j]],i)
        if ni == len(x[t[j]]):
            i = x[t[j]][0]
            count += 1
        else:
            i = x[t[j]][ni]
    else:
        print(-1)
        exit()
    
print(len(s)*(count-1)+i+1)
### BUGGY CODE ###

n = int(input())
strings_list = ["".join(sorted(list(input()))) for i in range(n)]
counter = 0

while True:
    if len(strings_list) == 0 or len(strings_list) == 1:
        break
    else:
        if strings_list[0] not in strings_list[1:]:
            strings_list.pop(0)
        else:
            counter += strings_list[1:].count(strings_list[0])
            strings_list.pop(0)
print(counter)


### FIXED CODE ###

n = int(input())
strings_list = [list(input()) for i in range(n)]
counter = 0
dict = {}

for strings in strings_list:
    strings = "".join(sorted(strings))
    if strings in dict.keys():
        counter += dict[strings]
        dict[strings] += 1
    else:
        dict[strings] = 1
print(counter)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

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


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i, ai in enumerate(a):
        if ai > 0:
            idx = bisect_right(a, x // ai)
            cnt += max(idx - i - 1, 0)
        elif ai < 0:
            idx = bisect_left(a, -(x // abs(ai)))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # ai == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


# lb = -10**18  # False
# ub = +10**18  # True
lb = min(a[0]**2, a[0] * a[-1], a[-1]**2) - 1  # False
ub = max(a[0]**2, a[0] * a[-1], a[-1]**2) + 1  # True

while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

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

a_minus = a_zero = a_plus = 0
for i in range(n):
    if a[i] > 0:
        a_plus += 1
    elif a[i] == 0:
        a_zero += 1
    else:
        a_minus += 1

aa_minus = a_minus * a_plus
aa_zero = a_zero * (n - a_zero) + a_zero * (a_zero - 1) // 2


def check_minus(x):
    # k番目の数がx(<0)以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    j = a_minus + a_zero
    for i in range(a_minus):
        # a[i] < 0
        while j < n and a[i] * a[j] > x:
            j += 1
        cnt += n - j

    return cnt >= k


def check_plus(x):
    # k番目の数がx(>0)以下であるか
    # x以下の数字がk個以上あるか

    def func(b, m):
        # 昇順ソート済みの数列b (長さm)
        # 掛け算してx以下となる数を求める
        c = 0
        j = m - 1
        for i in range(m):
            while j > 0 and b[i] * b[j] > x:
                j -= 1
            c += max(j - i, 0)
        return c

    cnt = aa_minus + aa_zero
    cnt += func(a[-a_plus:], a_plus)
    cnt += func(list(reversed(a[:a_minus])), a_minus)
    return cnt >= k


if k <= aa_minus:
    # k番目の数は負の数
    lb = a[0] * a[-1] - 1  # False
    ub = 0  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub
elif k <= aa_minus + aa_zero:
    # k番目の数は0
    ans = 0
else:
    # k番目の数はプラス
    lb = 0  # False
    ub = max(a[0]**2, a[-1]**2) + 1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub

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

n,k = map(int,input().split())
l = list(map(int,input().split())) + [float("inf") for _ in range(k)]

dist = [float("inf") for _ in range(n+k)]
dist[n-1]= 0
for x in range(n-2,-1,-1):
    dist[x] = min(dist[y] + abs(l[x]-l[y]) for y in range(x+1,x+1+k))
print (dist[0])


### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split())) + [2**26 for _ in range(k)]

dist = [2**26 for _ in range(n+k)]
dist[n-1]= 0
for x in range(n-2,-1,-1):
    a = l[x]
    #dist[x] = min(dist[y] + abs(a-l[y]) for y in range(x+1,x+1+k))
    dist[x] = min(y + abs(a-b) for b,y in zip(l[x+1:x+1+k],dist[x+1:x+1+k]))
print (dist[0])
### BUGGY CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)

### FIXED CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
for i in range(k):
	h.remove(max(h))
	if len(h) == 0:
		break
print(sum(h))

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h.sort(reverse=True)
h = h[k:]
print(sum(h))
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
num = list(map(int, input().split()))
for i in range(m):
  num.sort()
  cnt, changeNum = map(int, input().split())
  for j in range(cnt):
    if num[j] >= changeNum:
      break
    else:
      num[j] = changeNum
print(sum(num))

### FIXED CODE ###

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
n, m = map(int, input().split())
heap = []

for i in map(int, input().split()):
  heappush(heap, i)

bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key = lambda x: -x[1])#cが大きいものから順に操作を加える

for b,c in bc:
  for j in range(b):
    a = heappop(heap)
    if a < c:
      heappush(heap, c)
    else:
      heappush(heap, a)
      break
print(sum(heap))
### BUGGY CODE ###

import numpy as np
[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = np.zeros((N+1,M+1))
ta[0,0]=1
wa = np.zeros((N+1,M+1))
wa[0,:]=1
wa[:,0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i,j]=wa[i-1,j-1]%(10**9+7)
            wa[i,j]=(wa[i-1,j]+wa[i,j-1])%(10**9+7)
        else:
            wa[i,j]=(wa[i-1,j]+wa[i,j-1]-wa[i-1,j-1])%(10**9+7)
output = wa[N,M]
print(int(output))

### FIXED CODE ###

[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = [[0] * (M+1) for i in range(N+1)]
ta[0][0]=1
wa = [[0] * (M+1) for i in range(N+1)]
wa[0][:]=[1]*(M+1)
for i in range(N+1):
    wa[i][0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i][j]=wa[i-1][j-1]
            wa[i][j]=(wa[i-1][j]+wa[i][j-1])%(10**9+7)
        else:
            wa[i][j]=(wa[i-1][j]+wa[i][j-1]-wa[i-1][j-1]+(10**9+7))%(10**9+7)
output = wa[N][M]
print(int(output))
### BUGGY CODE ###

import sys
import math
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    U = [0]*(max(A)+1)
    for e in A:
        U[e] += 1
    ans = 0
    for k in range(1,max(A)+1):
        if U[k] == 1:
            ans += 1
        if U[k] > 0:
            for l in range(2*k,max(A)+1,k):
                if U[l] > 0:
                    U[l] += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,10**6+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = flag2 = flag3 = False
            for l in range(n):
                if not flag1 and str(i) == s[l]:
                    flag1 = True
                    continue
                if flag1 and not flag2 and not flag3 and str(j) == s[l]:
                    flag2 = True
                    continue
                if flag1 and flag2 and not flag3 and str(k) == s[l]:
                    flag3 = True
                    continue
            if flag1 and flag2 and flag3:
                cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(10):
    a = s.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = s.find(str(j), a + 1)
        if b == -1:
            continue
        for k in range(10):
            c = s.find(str(k), b + 1)
            if c != -1:
                cnt += 1
print(cnt)
### BUGGY CODE ###

# -*- coding:utf-8 -*-                                                                                     
import sys

def is_unbalanced(n, li_part):
    li_uniq = set(li_part)

    for c in li_uniq:
        if li_part.count(c) > n/2. :
            return 1

    return 0

li_c = list(input())
N = len(li_c)

for size_frame in range(2, N+1):
    i = 0

    while(i + size_frame <= N):
        if(is_unbalanced(size_frame, li_c[i:i+size_frame]) == 1):
            print( i+1, i+1 + size_frame -1)
            sys.exit()
        i = i + 1

print(-1, -1)


### FIXED CODE ###

# -*- coding:utf-8 -*-                                                                                     
import sys

def is_unbalanced(n, li_part):
    li_uniq = set(li_part)

    for c in li_uniq:
        if li_part.count(c) > n/2. :
            return 1

    return 0

li_c = list(input())
N = len(li_c)

for size_frame in range(2, 4):
    i = 0

    while(i + size_frame <= N):
        if(is_unbalanced(size_frame, li_c[i:i+size_frame]) == 1):
            print( i+1, i+1 + size_frame -1) # 自然な文字列の順番にする                                    
            sys.exit()

        i = i + 1

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

n=int(input())
S=[]
S=input().split()
q=int(input())
T=[]
T=input().split()
point=0
for i in range(q):	
	for j in range(n):
		if T[i]==S[j]:
			point+=1
			break		
print(point)


### FIXED CODE ###

#16D8101014F 久留米 竜之介 2018/5/14
n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))
point=0
for i in T:
	left=0
	right=n
	while left < right:
		mid=int((left+right)/2)
		if S[mid] == i:
			point += 1
			break
		elif i < S[mid]:
			right = mid
		else:
			left = mid + 1
	#print(i,point)

print(point)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [[]]
for i in range(N):
    As.append(list(map(int, input().split())))

Cs = [0] * (N + 1)
Ks = [False] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
tab = set()
while sw:
    c = 0
    wa = []
    for i in range(1, N + 1):
        if Ks[i]:
            continue
        if Cs[i] == N - 1:
            continue
        a = 0
        b = 0
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                print(d)
                break
            Cs[a] += 1
            Cs[b] += 1
            tab.remove((a, b))
            wa.append(a)
            wa.append(b)
        else:
            tab.add((a, b))
            Ks[i] = True
    for i in wa:
        Ks[i] = False
    d += 1
    if c == 0:
        print(-1)
        break

### FIXED CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [list(map(int, input().split())) + [-1] for _ in range(N)]

import collections

que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
    player = que.popleft()
    opponent = As[player][counters[player]] - 1
    if As[opponent][counters[opponent]] - 1 == player:
        days[player] = max(days[player], days[opponent]) + 1
        days[opponent] = days[player]
        counters[player] += 1
        counters[opponent] += 1
        que.append(player)
        que.append(opponent)
for c in counters:
    if c < N - 1:
        print(-1)
        break
else:
    print(max(days))