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

import collections

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

n = int(input())
l = list(map(int, input().split()))
s = list(set(l))
all_sum = 0
count = {}
for i in range(len(s)):
    v = l.count(s[i])
    all_sum += v * (v - 1) // 2
count = count_defaultdict(l)
for i in range(len(l)):
    if count[l[i]] > 1:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)

### FIXED CODE ###

import collections

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

_ = int(input())
l = list(map(int, input().split()))
all_sum = 0
count = count_defaultdict(l)
for _, v in count.items():
    all_sum += v * (v - 1) // 2
for i in range(len(l)):
    if count[l[i]] > 1:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)
### BUGGY CODE ###

in_num = int(input())
check_num = 0
ans_counter = 0

while check_num <= in_num:
	i = 1
	div_counter = 0
	while i < check_num /2:
		if check_num % i == 0:
			div_counter += 1
		i += 2
	if div_counter == 8:
		ans_counter += 1

print(ans_counter)






### FIXED CODE ###

in_num = int(input())
check_num = 1
ans_counter = 0



while check_num <= in_num:
	i = 1
	div_counter = 0
	while i <= check_num :
		if check_num % i == 0:
			div_counter += 1
		i += 2
	if div_counter == 8:
		ans_counter += 1
	check_num += 2

print(ans_counter)
### BUGGY CODE ###

import numpy as np

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

s = list(S)
s.reverse()
s_bit = np.array([1 if i == 'E' else 0 for i in s])
bit_mask = np.array([pow(2,i) for i in range(N)])
bit = np.dot(s_bit, bit_mask)

min = N
for i in range(N):
    a = bit & (1 << i)
    b = (pow(2,N) - 1) - (pow(2,i+1) - 1)
    c = b | a
    cost = bit ^ c
    actual_cost = bin(cost).count("1")
    if actual_cost < min:
        min = actual_cost

print(min)


### FIXED CODE ###

import numpy as np

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


s = list(S)


s.reverse()
s = np.array([1 if i == 'E' else 0 for i in s])
#str = S.replace('E','1')
#bit_str = str.replace('W','0')
#bit = int(bit_str, base=2)

cost = [0]*N
cost[0] = (N-1) - sum(s[1:N])
for i in range(1,N):
    now = s[i]
    bef = s[i-1]
    cost[i] = cost[i-1] + bef - (1^now)

print(min(cost))
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a = sorted(a,reverse=True)
b = sorted(b,reverse=True)
c = sorted(c,reverse=True)

l = []
for i in range(min(200,x)):
    for j in range(min(200,y)):
        for t in range(min(200,z)):
            l.append(a[i] + b[j] + c[t])
l = sorted(l,reverse=True)
for i in range(k):
    print(l[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

l = []
for i in range(x):
    for j in range(y):
            l.append(a[i] + b[j])

l = sorted(l,reverse=True)
ll = []
for i in range(min(len(l),k)):
    for j in range(z):
        ll.append(l[i] + c[j])

ll = sorted(ll,reverse=True)
for i in range(k):
    print(ll[i])
### BUGGY CODE ###

import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict
import bisect
from fractions import Fraction
 
 
N = int(input())
A=list(map(int, input().split()))
 
num = A[0]
for i in range(1, N):
    num = num * A[i] // fractions.gcd(num%A[i], A[i])
 
ans = 0
 
for i in range(N):
    ans += (num // A[i])
    ans %= 10**9+7
 
print(ans)

### FIXED CODE ###

import fractions as math
from functools import reduce
 
 
N = int(input())
A=list(map(int, input().split()))
 
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
num = lcm_list(A)
 
ans = 0
 
for i in range(N):
    ans += (num // A[i])
 
print(ans%(10**9+7))
### BUGGY CODE ###

a,b,c = map(int, input().split())
arr = [[0 for _ in range(b)] for _ in range(a)]
for _ in range(c):
    x,y = map(int, input().split())
    arr[x-1][y-1] = '#'

counts = []
new_list = list(zip(*arr))
ans = 0
for k in range(b):
    counts.append(new_list[k].count('#'))
    
for i in range(a):
    temp = arr[i].count('#')
    for j in range(b):
        if arr[i][j] == '#':
            ans = max(ans, temp+counts[j]-1)
        else:
            ans = max(ans, temp+counts[j])
print(ans)

### FIXED CODE ###

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

HL, WL = [0]*H, [0]*W
B = []

for _ in range(M):
  h, w = map(lambda x:int(x)-1, input().split())
  B.append((h, w))
  HL[h] += 1
  WL[w] += 1

HM, WM = max(HL), max(WL)
K = HL.count(HM) * WL.count(WM)

cnt = 0
for h, w in B:
  if HL[h] == HM and WL[w] == WM:
    cnt += 1

if K > cnt:
  print(HM+WM)
else:
  print(HM+WM-1)
### BUGGY CODE ###

n = int(input())
s = input()

result = set()
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            key = ''.join(s[i] + s[j] + s[k])
            result.add(key)

#print(result)
print(len(result))


### FIXED CODE ###

n = int(input())
s = list(map(int, input()))

ans = 0
for i in range(10):
    if i in s[: n - 2]:
        x = s.index(i)
        for j in range(10):
            if j in s[x + 1: n - 1]:
                y = x + 1 + s[x + 1: n - 1].index(j)
                for k in range(10):
                    if k in s[y + 1:]:
                        ans += 1
print(ans)
### BUGGY CODE ###

def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13)
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = np.zeros(13)
        a = m13[i % 12]
        if s[i] == "?":
            list_ = np.arange(10)
        else:
            list_ = np.array([int(s[i])])
        list_ = a*list_ % 13
        for l in list_:
            memo2[l:] += memo[:13-l]
            memo2[:l] += memo[13-l:]
        memo = memo2 % mod
    print(int(memo[5]))


main()


### FIXED CODE ###

s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache

input = sys.stdin.readline

# N個整数
x, y, z, k = list(map(int, input().split()))

# 1整数
# n = int(input())

# 空白区切りリスト整数
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ll = [0] * 1000001
count = 0
for i in a:
    for j in b:
        ll[count] = i + j
        count += 1
ll.sort(reverse=True)

ll = ll[0:3000]
c.sort(reverse=True)

lll = [0] * 3000001
count = 0
for i in ll:
    for j in c:
        lll[count] = i + j
        count += 1
lll.sort(reverse=True)

for i in range(k):
    print(lll[i])

# 空白区切り文字列
# t, d = input().split()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache

input = sys.stdin.readline

# N個整数
x, y, z, kk = list(map(int, input().split()))

# 1整数
# n = int(input())

# 空白区切りリスト整数
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)


ll = []
count = 0
for i in range(len(a)):
    for j in range(len(b)):
        if i * j > kk:

            break
        for k in range(len(c)):
            if i * j * k > kk:
                break
            ll.append(a[i] + b[j] + c[k])
ll.sort(reverse=True)

for i in range(kk):
    print(ll[i])

# 空白区切り文字列
# t, d = input().split()
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
R = [0]*N
ans = []
for i in range(N-1):
  if S[i] == 'A' and S[i+1] == 'C':
    R[i+1] = 1
for k in range(Q):
  l,r = map(int,input().split())
  ans.append(sum(R[:r])-sum(R[:l]))
for j in range(len(ans)):
  print(ans[j])

### FIXED CODE ###

N,Q = map(int,input().split())
S = list(input())
R = [0]*N
ans = []
temp = 0
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    temp += 1
  R[i] = temp
for k in range(Q):
  l,r = map(int,input().split())
  ans.append(R[r-1]-R[l-1])
for j in range(len(ans)):
  print(ans[j])
### BUGGY CODE ###



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

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

# a = [0] * m
# b = [0] * m

ans = set([i for i in range(n)])

# table = [[1]*n for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    if h[a] <= h[b]:
        # table[h[a]][h[b]] = 0
        if a in ans:
            ans = ans - {a}
    if h[b] <= h[a]:
        if b in ans:
            ans = ans - {b}
        

# print(ans)
print(len(ans))


### FIXED CODE ###



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

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

# a = [0] * m
# b = [0] * m

ma = [0]*n


for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    ma[a] = max(ma[a],h[b])
    ma[b] = max(ma[b],h[a])

ans = 0    
for i in range(n):
    if h[i] > ma[i]:
        ans += 1
        

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

n = int(input())
A = list(map(int,input().split()))
cnt = 0
for i in range(1,n):
  if A[0] >= 0:
    if i%2!=0 and A[i]>=0:
      cnt += A[i]
      A[i] -= A[i]
      while sum(A[:i+1])>=0:
        A[i] -= 1
        cnt += 1
    elif i%2==0 and A[i]<0:
      cnt += abs(A[i])
      A[i] += abs(A[i])
      while sum(A[:i+1])<=0:
        A[i] += 1
        cnt += 1
    else:
      if A[i] >= 0:
        while sum(A[:i+1])<=0:
          A[i] += 1
          cnt += 1
      else:
        while sum(A[:i+1])>=0:
          A[i] -= 1
          cnt += 1
  else:
    if i%2!=0 and A[i]<0:
      cnt += abs(A[i])
      A[i] += abs(A[i])
      while sum(A[:i+1])<=0:
        A[i] += 1
        cnt += 1
    elif i%2==0 and A[i]>=0:
      cnt += A[i]
      A[i] -= A[i]
      while sum(A[:i+1])>=0:
        A[i] -= 1
        cnt += 1
    else:
      if A[i] >= 0:
        while sum(A[:i+1])<=0:
          A[i] += 1
          cnt += 1
      else:
        while sum(A[:i+1])>=0:
          A[i] -= 1
          cnt += 1  
print(cnt)

### FIXED CODE ###

n = input()
a = [int(i) for i in input().split()]
def chk(a, t):
  ans = 0
  x = 0
  for i in a:
    x += i
    if t == True and x < 1:
      ans+=1-x
      x=1
    elif t == False and x>-1:
      ans+=x+1
      x=-1
    t=not t
  return ans
print(min(chk(a,True),chk(a,False)))
### BUGGY CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for n in range(N)]
P = []

for n in range(1, N + 1):
    P.extend(itertools.combinations([n for n in range(N)], n))

add_len = {s: sum(L[i] for i in s) for s in P}


def cost(v, s):
    return 10 * (len(s) - 1) + abs(v - add_len[s])


res = 2 << 30
for a in P:
    cost_a = cost(A, a)
    if res < cost_a:
        continue

    for b in P:
        cost_b = cost(B, b)
        if res < cost_b:
            continue

        if len(set(a) & set(b)):
            continue

        for c in P:
            cost_c = cost(C, c)
            if res < cost_c:
                continue

            if len(set(a) & set(c)) or len(set(b) & set(c)):
                continue
            res = min(res, cost_a + cost_b + cost_c)

print(res)


### FIXED CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for n in range(N)]
P = []

for n in range(1, N + 1):
    P.extend(itertools.combinations([n for n in range(N)], n))

add_len = {s: sum(L[i] for i in s) for s in P}


def cost(v, s):
    return 10 * (len(s) - 1) + abs(v - add_len[s])


res = 2 << 30
for a in P:
    cost_a = cost(A, a)
    if res < cost_a:
        continue

    for b in P:
        cost_b = cost(B, b)
        if res < cost_b:
            continue

        set_a = set(a)
        set_b = set(b)
        if len(set_a & set_b):
            continue

        for c in P:
            cost_c = cost(C, c)
            if res < cost_c:
                continue

            set_c = set(c)
            if len(set_a & set_c) or len(set_b & set_c):
                continue
            res = min(res, cost_a + cost_b + cost_c)

print(res)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    s = list(input())
    k = int(input())
    subs = set()
    lens = len(s)
    for i1 in range(lens):
        for i2 in range(lens - i1):
            subs.add("".join(s[i2:i2+i1+1]))
    subs_l = list(subs)
    subs_l.sort()
    print(subs_l[k-1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = list(input())
    k = int(input())
    k -= 1

    d1 = defaultdict(list)
    for i, c in enumerate(s):
        d1[c].append(i)
    d2 = sorted(d1.items())

    lens = len(s)
    for d2e in d2:
        subs = set()
        subs.add(d2e[0])
        for d2ee in d2e[1]:
            end = min(lens + 1, d2ee + k + 2)
            for i1 in range(d2ee+1, end):
                subs.add("".join(s[d2ee:i1]))
        if len(subs) > k:
            subsl = list(subs)
            subsl.sort()
            print(subsl[k])
            sys.exit()
        else:
            k -= len(subs)

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

def main():
  from collections import deque
  H, W = map(int, input().split())
  graph = [['#'] * (W+2) for _ in range(H+2)]
  for i in range(H):
    S = input()
    for j in range(W):
      graph[i+1][j+1] = S[j]

  def dfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[sx][sy] = 0
    while q:
      x, y = q.popleft()
      dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
      for dx, dy in dxy:
        nextx = x+dx
        nexty = y+dy
        if(dist[nextx][nexty] >= 0):
          continue
        if(graph[nextx][nexty] == '#'):
          continue
        dist[nextx][nexty] = dist[x][y] + 1
        q.append((nextx, nexty))
    return dist[gx][gy]

  ans = 0  
  for sx in range(1, H+1):
    for sy in range(1, W+1):
      for gx in range(1, H+1):
        for gy in range(1, W+1):
          if(graph[sx][sy] == '.' and graph[gx][gy] == '.'):
            tmp = dfs(sx, sy, gx, gy)
            ans = max(ans, tmp)
          
  print(ans)
  
main()

### FIXED CODE ###

def main():
  from collections import deque
  H, W = map(int, input().split())
  graph = [['#'] * (W+2) for _ in range(H+2)]
  for i in range(H):
    S = input()
    for j in range(W):
      graph[i+1][j+1] = S[j]

  def dfs(sx, sy):
    q = deque([(sx, sy)])
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[sx][sy] = 0
    s = 0
    while q:
      x, y = q.popleft()
      dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
      for dx, dy in dxy:
        nextx = x+dx
        nexty = y+dy
        if(dist[nextx][nexty] >= 0):
          continue
        if(graph[nextx][nexty] == '#'):
          continue
        dist[nextx][nexty] = dist[x][y] + 1
        q.append((nextx, nexty))
    for i in range(H+2):
      for j in range(W+2):
        if(dist[i][j] >= 0):
          s = max(s, dist[i][j])
    return s

  ans = 0  
  for sx in range(1, H+1):
    for sy in range(1, W+1):
      if(graph[sx][sy] == '.'):
          tmp = dfs(sx, sy)
          ans = max(ans, tmp)
          
  print(ans)
  
main()
### BUGGY CODE ###

n, m = map(int, input().split())
s = input()
l = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
    print(s.count("AC", l[i][0]-1, l[i][1]))

### FIXED CODE ###

n, m = map(int, input().split())
s = input()
t = [0] * (n+1)
for i in range(n):
    if s[i:i + 2] == "AC":
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]
for i in range(m):
    a, b = map(int, input().split())
    print(t[b-1] - t[a-1])
### BUGGY CODE ###

N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

retval=0
while len(enemies)>0:
    e=enemies.pop(0)
    if e[1]<=0:
        continue
    bomb=0
    if e[1]%A==0:
        bomb=e[1]//A
    else:
        bomb=e[1]//A+1
    retval+=bomb
    for enemy in enemies:
        if enemy[0]-e[0]<=2*D:
            enemy[1]-=A*bomb
        else:
            break


print(retval)


### FIXED CODE ###

import sys
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

if enemies[-1][0]-enemies[0][0]<=2*D:
    hpmax=sorted(enemies,key=lambda  w:w[1])[-1][1]
    if hpmax%A==0:
        print(hpmax//A)
    else:
        print(hpmax//A+1)
    sys.exit()


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)
### BUGGY CODE ###

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

top = 0
for i in range(M):
  list.sort(A, reverse=True)
  A[0] = A[0] // 2

print(sum(A))

### FIXED CODE ###

import heapq
import math

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

hq = []
for a in A:
  heapq.heappush(hq, a * -1)

for i in range(M):
  n = math.ceil(heapq.heappop(hq) / 2)
  heapq.heappush(hq, n)

b = []
for hqi in hq:
  b.append(hqi * -1)
  
print(sum(b))
### BUGGY CODE ###

N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x

que=[(0,-1)]

while len(que)>0:
    now, pre=que.pop(0)
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

print(" ".join(map(str, X)))

### FIXED CODE ###

from collections import deque 
N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.pop()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

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

import sys
from collections import defaultdict
n=int(input())
a=[]
hd=[0]*n
for i in range(n):
    a.append(tuple(map(int,input().split())))
d=defaultdict(int)
for i in range(n):
    for j in range(n-1):
        d[(i,j)]=a[i][j]
loop=0
flag=0
while(flag<n):
    stk=[]
    for i in range(n):
        if hd[i]==n-1:
            continue
        idx=d[(i,hd[i])]-1
        if hd[idx]==n-1:
            print(-1)
            sys.exit()
        if d[(idx,hd[idx])]==i+1:
            stk.append(i)
    if not stk:
        loop=-2
        break
    for j in stk:
        hd[j]+=1
        if hd[j]==n-2:
            flag+=1
    loop+=1
print(loop+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
n=int(input())
a=[]
for i in range(n):
    a.append(tuple(map(int,input().split())))
#print(a)

root=[[] for i in range(n*(n-1)//2)]
buf=0
for i in range(n):
    buf=0
    for j in range(n-1):
        if j==0:
            x=min(i,a[i][j]-1)
            y=max(i,a[i][j]-1)
            buf=x*(2*n-2-x+1)//2+(y-x)-1
            #print(x,y,buf)
            continue
        x=min(i,a[i][j]-1)
        y=max(i,a[i][j]-1)
        node=x*(2*n-2-x+1)//2+(y-x)-1
        #print(x,y,node)
        root[buf].append(node)
        buf=node
flag=[True]

#閉路☑
def dfs(node,par): 
    dp[node]=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]==0:
            flag[0]=False
            return
        if dp[item]==-1: 
            dfs(item,node)
    dp[node]=1#finish
dp=[-1]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dfs(i,i)
        if flag[0]==False:
            break
if flag[0]==False:
    print(-1)
    sys.exit()
dp=[-1]*(n*(n-1)//2)
def dfs1(node,par): 
    buf=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]!=-1:
            buf=max(buf,dp[item])
            continue
        if dp[item]==-1: 
            buf=max([buf,dfs1(item,node)])
    dp[node]=buf+1#finish
    return buf+1

for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dp[i]=dfs1(i,i)
print(max(dp))
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict,deque
n = inn()
pr = {}
ch = {}
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        if (x1,y1) in ch:
            ch[(x1,y1)].append((x2,y2))
        else:
            ch[(x1,y1)] = [(x2,y2)]
        if (x2,y2) in pr:
            pr[(x2,y2)].append((x1,y1))
        else:
            pr[(x2,y2)] = [(x1,y1)]
g = {}
q = []
for i in range(1,n):
    for j in range(i+1,n+1):
        if (i,j) not in pr:
            q.append((i,j))
            g[(i,j)] = 1
        else:
            g[(i,j)] = 0
ddprint(ch)
ddprint("pr")
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.pop()
    if z in ch:
      for y in ch[z]:
        g[y] = max(g[y], g[z]+1)
        #ddprint("y {} z {}".format(y,z))
        pr[y].remove(z)
        if len(pr[y])==0:
            #del pr[y]
            q.append(y)
if min(g.values())==0:
    print(-1)
else:
    print(max(g.values()))


### FIXED CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict,deque
n = inn()
pr = [[ [] for i in range(n+1) ] for j in range(n+1)]
ch = [[ [] for i in range(n+1) ] for j in range(n+1)]
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        ch[x1][y1].append((x2,y2))
        pr[x2][y2].append((x1,y1))
g = [ [0]*(n+1) for i in range(n+1) ]
q = []
for i in range(1,n):
    for j in range(i+1,n+1):
        if len(pr[i][j])==0:
            q.append((i,j))
            g[i][j] = 1
        else:
            g[i][j] = 0
ddprint(ch)
ddprint("pr")
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.pop()
    i,j = z
    for u,v in ch[i][j]:
        g[u][v] = max(g[u][v], g[i][j]+1)
        #ddprint("y {} z {}".format(y,z))
        pr[u][v].remove(z)
        if len(pr[u][v])==0:
            #del pr[y]
            q.append((u,v))
ddprint("newg")
ddprint(g)
#gmn = [min(r[1:]) for r in g[1:]]
gmn = BIG
for i in range(1,n):
    for j in range(i+1,n+1):
        gmn = min(gmn,g[i][j])
if gmn==0:
    print(-1)
else:
    print(max([max(r) for r in g]))