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

import queue

def setNode(n):
    global G
    global H
    G = [{} for i in range(n)]
    H = [{} for i in range(n)]

def addEdge(s, t, p, q):
    global G
    global H
    G[s][t]=p
    G[t][s]=p
    H[s][t]=q
    H[t][s]=q

def shortest_path(G, s, t):
    fixed = {}
    q = queue.PriorityQueue()
    q.put((0,s))

    while q.empty() == False:
        w,x = q.get()
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                q.put((w + G[x][y], y))
    return None

if __name__ == '__main__':
    G = [{}] # JPY
    H = [{}] # SNK
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    setNode(n)

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        U = u-1
        V = v-1
        addEdge(U, V, p, q)

    for year in range(n):
        cost = None
        for exg in range(year, n):
            min_jpy = shortest_path(G, S, exg)
            min_snk = shortest_path(H, T, exg) # = shortest_path(exg, T)
            total = min_jpy + min_snk
            if cost is None:
                cost = total
            else:
                if cost > total:
                    cost = total
            #print("year:{}\t{}->{}->{}: JPY:{}, SNK:{}: total:{}".format(year, S,exg,T,min_jpy,min_snk, total))
        #print("year:{}\tminimum cost:{}, money:{}".format(year, cost, money-cost))
        print(money-cost)

### FIXED CODE ###

import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
p = [np.sum(np.arange(1, int(i) + 1)) / float(i) for i in input().split()]
p = np.array(p)
s = np.cumsum(p)
m = s[k - 1]
for i in range(n - k):
    m = max(m, s[i + k] - s[i])
print(m)

### FIXED CODE ###

import sys
n, k = map(int, input().split())
p = [int(i) for i in input().split()]
total = [0] * n
total[0] = sum(range(1, p[0] + 1)) / p[0]
max_value = 0
if k == 1:
    print(sum(range(1, max(p) + 1)) / max(p))
    sys.exit()
elif k == n:
    print(sum([sum(range(1, i + 1)) / i for i in p]))
    sys.exit()
for i in range(1, n):
    total[i] = total[i - 1] + sum(range(1, p[i] + 1)) / p[i]
    
    if i == k - 1:
        max_value = total[i]
    elif i >= k:
        max_value = max(max_value, total[i] - total[i - k])
print(max_value)
### BUGGY CODE ###

from collections import Counter

n = int(input())
ball = [int(i) for i in input().split()]
counter = Counter(ball)
for i in range(n):
  counter[ball[i]] -= 1
  result = 0
  print(sum([i * (i - 1) // 2 for i in counter.values()]))
  counter[ball[i]] += 1
  


### FIXED CODE ###

from collections import Counter

n = int(input())
ball = [int(i) for i in input().split()]
counter = Counter(ball)
result = sum([i * (i - 1) // 2 for i in counter.values()])

for i in range(n):
  c = counter[ball[i]]
  print(result - (c - 1))
### BUGGY CODE ###

N, M, Q = map(int, input().split())
LR =[[] for i in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    LR[L-1].append(R)

ans = []
for i in range(Q):
    p, q = map(int, input().split())
    count = 0
    for j in range(p-1, q):
        for k in LR[j]:
            if k <= q:
                count += 1
    ans.append(count)

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

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

LR =[[0 for j in range(N+2)] for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    LR[L][R] += 1
    LR[0][R] -= 1
    LR[L][N+1] -= 1
    LR[0][N+1] += 1

for i in range(1, N+1): #R方向への累積和
    for j in range(1, N+2):
        LR[i][j] += LR[i][j-1]
for i in range(N-1, -1, -1): #L方向への累積和
    for j in range(1, N+2):
        LR[i][j] += LR[i+1][j]

ans = []
for i in range(Q):
    p, q = map(int, input().split())
    ans.append(LR[p][q])

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
s_list = []
count_list = []

for _ in range(n):
  s = input()
  if not s in s_list:
    s_list.append(s)
    count_list.append(1)
  else:
    count_list[s_list.index(s)] += 1
    
#print(s_list)
#print(count_list)

max_s = max(count_list)
#print(max_s)

max_list = []
for i in range(len(s_list)):
  if count_list[i] == max_s:
    max_list.append(s_list[i])
    
max_list.sort()

for j in range(len(max_list)):
  print(max_list[j])


### FIXED CODE ###

n = int(input())
s_dict = {}

for _ in range(n):
  s = input()
  if s_dict.get(s, -1) == -1:
    s_dict[s] = 1
  else:
    s_dict[s] += 1

if len(s_dict) == 1:
  print(list(s_dict.keys())[0])
  exit()
  
s_dict2 = sorted(s_dict.items(), key=lambda x:x[1], reverse=True)
s_list = []
i = 0

while s_dict2[i][1] == s_dict2[0][1]:
  s_list.append(s_dict2[i][0])
  i += 1
  if i == len(s_dict2):
    break

s_list.sort()
for i in range(len(s_list)):
  print(s_list[i])
### BUGGY CODE ###

import sys
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    num[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])
def unite(x,y):
  if (y<x):
    par[x]=y
  else:
    par[y]=x
def same(x,y):
  return find(x)==find(y)
def cnt(x,tmp):
  res = tmp + num[x]
  if par[x]==x:
    return res
  else:
    return cnt(par[x],res)


N,Q = IL()
ab = [IL() for i in range(N-1)]
px = [IL() for i in range(Q)]

par=[0 for i in range(N+1)]
num=[0 for i in range(N+1)]

init(N)

for a,b in ab:
  unite(a,b)

for p,x in px:
  num[p] += x

ans = []
for i in range(1,N+1):
  ans.append(cnt(i,0))

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

### FIXED CODE ###

import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    num[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])
def unite(x,y):
  if (y<x):
    par[x]=y
  else:
    par[y]=x
def same(x,y):
  return find(x)==find(y)
def cnt(x):
  if par[x]==x:
    res = num[x]
    return res
  else:
    if used[par[x]] == True:
      res = num[x] + ans[par[x]]
      return res
    else:
      return

N,Q = IL()
ab = [IL() for i in range(N-1)]
px = [IL() for i in range(Q)]

par=[0 for i in range(N+1)]
num=[0 for i in range(N+1)]

init(N)

for a,b in ab:
  unite(a,b)

for p,x in px:
  num[p] += x

ans = [0 for i in range(N+1)]
used = [False for i in range(N+1)]
for i in range(1,N+1):
  ans[i] = cnt(i)
  used[i] = True

print(" ".join(map(str,ans[1:])))
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
for i in range(len(c)):
  for j in range(len(d)-1,-1,-1):
    if c[i]+d[j]<=k and i+j>e:
      e=i+j
      break
print(e)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
f=len(d)-1
for i in range(len(c)):
  for j in range(f,-1,-1):
    if c[i]+d[j]<=k:
      if i+j>e:
        e=i+j
      f=j
      break
print(e)
### BUGGY CODE ###

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

num_list = [0]* (len(a)+1)

for i in range(len(a)+1):
    num_list[i] = a.count(i)

total = 0

for j in range(len(num_list)):
    total += (num_list[j]* (num_list[j]-1))/2

#print(total)

for k in range(len(a)):
#    print(num_list[a[k]]) 
    print(int(total-(num_list[a[k]])+1))
"""
import math

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

cnt = flaot(0.0)

for i in range(1, len(a)+1):
    b = a[0:i-1]+a[i:len(a)]
    
    cnt = 0.0
    for j in range (1, len(a)):
        cnt += b.count(j)*(b.count(j)-1)/2
    print(int(cnt))
"""

### FIXED CODE ###

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

num_list = [0]* (len(a)+1)

for i in range(len(a)):
#    num_list[i] = a.count(i)
    num_list[a[i]] += 1

total = 0

for j in range(len(num_list)):
    total += (num_list[j]* (num_list[j]-1))/2

#print(total)

for k in range(len(a)):
#    print(num_list[a[k]]) 
    print(int(total-(num_list[a[k]])+1))
"""
import math

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

cnt = flaot(0.0)

for i in range(1, len(a)+1):
    b = a[0:i-1]+a[i:len(a)]
    
    cnt = 0.0
    for j in range (1, len(a)):
        cnt += b.count(j)*(b.count(j)-1)/2
    print(int(cnt))
"""
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]


def bfs():
    q = deque()
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nx = i + dx
                    ny = j + dy
                    if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                        q.append((nx, ny))
    res = len(q)
    while (len(q)):
        np = q.popleft()
        grid[np[0]][np[1]] = '#'

    return res


res = 0
while (bfs()):
    res += 1
print(res)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

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

import math
n,k = map(int,input().split())
alist = list(map(int,input().split()))

for i in range(k):
    new = [0] * n
    for j in range(n):
        distance = j - alist[j]
        if distance < 0:
            distance = 0
        last =  j + alist[j]
        if last > n-1:
            last = n-1
        new[distance]+=1
        if last+1 < n:
            new[last+1]-=1
    for j in range(1,n):
        new[j] += new[j-1]
    alist = new.copy()
    if new.count("n") == n:
        break
print(*alist)

### FIXED CODE ###


import numpy as np
from numba import njit

import math

n,k = map(int,input().split())
a = np.array(input().split(),np.int64)

@njit
def solve(n,k,a):
    for i in range(k):
        new = np.zeros_like(a)
        for j in range(n):
            distance = j - a[j]
            if distance < 0:
                distance = 0
            last =  j + a[j]
            if last > n-1:
                last = n-1
            new[distance]+=1
            if last+1 < n:
                new[last+1]-=1
        a = np.cumsum(new)
        if np.all(a==n):
            break
    return a

a = solve(n,k,a)
print(" ".join(a.astype(str)))
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=[x for x in set(a) if a.count(x)%2!=0]
print(len(b))

"""
set型は重複した要素をもたないデータ型
set(a)の各要素につき，リストaに奇数個含まれていたらリストbに入れる
"""

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
a.sort()
h=a[0]
ans=1
for i in a[1:]:
    if i!=h:
        ans+=1
        h=i
    else:
        ans-=1
        h=pow(10,10)    
print(ans)
### 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())
  a, b = a-1, b-1
  g[a].append(b)
#print(g)

from collections import deque

c = [0]*n
for j in range(q):
  x, p = map(int, input().split())
  x = x-1
  queue = deque()
  queue.append(x)
  c[x] += p
  while queue:
    y = queue.popleft()
    for y_ in g[y]:
      c[y_] += p
      queue.append(y_)

print(' '.join(map(str, c)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  #g[b].append(a)

ans = [0]*n  
for j in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
from collections import deque
s = deque()
s.append(0)

while s:
  v = s.pop()
  for v_ in g[v]:
    ans[v_] += ans[v]
    s.append(v_)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

s=input()
l=len(s)

mod=10**9+7

dp=[[0 for j in range(13)] for i in range(l)]

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

for i in range(1, l):
 if s[i]=='?':
   for j in range(10):
     for k in range(13):
       dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
 else:
   for k in range(13):
     dp[i][(k*10+int(s[i]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)


### FIXED CODE ###

s=input()
l=len(s)

mod=10**9+7

dp=[[0 for j in range(13)] for i in range(l)]

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

for i in range(1, l):
 if s[i]=='?':
   for j in range(10):
     for k in range(13):
       dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
 else:
   for k in range(13):
     dp[i][(k*10+int(s[i]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)

def rec(pp,xx=-1):
    for i in gragh[pp]:
        if i==xx:
            continue
        ans[i]+=ans[pp]
        rec(i,pp)

n,q=map(int,stdin.readline().rstrip().split())
ans=[0]*n
gragh=[[]*n for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,stdin.readline().rstrip().split())
    a-=1
    b-=1

    gragh[a].append(b)
    gragh[b].append(a)
for _ in range(q):
    p,x=map(int,stdin.readline().rstrip().split())
    ans[p-1]+=x
rec(0)
print(*ans)


### FIXED CODE ###

#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)

def rec(pp,xx=-1):
    for i in gragh[pp]:
        if i==xx:
            continue
        ans[i]+=ans[pp]
        rec(i,pp)

n,q=map(int,stdin.readline().rstrip().split())
ans=[0]*n
gragh=[[]*n for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,stdin.readline().rstrip().split())
    a-=1
    b-=1

    gragh[a].append(b)
    gragh[b].append(a)
for _ in range(q):
    p,x=map(int,stdin.readline().rstrip().split())
    ans[p-1]+=x
rec(0)
print(*ans)
### BUGGY CODE ###

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

lr = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l, r = map(lambda x: int(x) - 1, input().split())
    lr[l][r] += 1

dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        added = 0
        for k in range(i, j+1):
            added += lr[k][j]
        dp[i][j] = dp[i][j-1] + added

for _ in range(q):
    p, q = map(lambda x: int(x) - 1, input().split())
    print(dp[p][q])


### FIXED CODE ###

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

lr = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l, r = map(lambda x: int(x) - 1, input().split())
    lr[l][r] += 1

for i in range(n):
    for j in range(1, n):
        lr[i][j] += lr[i][j-1]

for i in range(1, n):
    for j in range(n):
        lr[i][j] += lr[i-1][j]

for _ in range(q):
    p, q = map(lambda x: int(x) - 1, input().split())
    if p == 0:
        print(lr[q][q])
    else:
        print(lr[q][q]-lr[p-1][q]-lr[q][p-1]+lr[p-1][p-1])
### BUGGY CODE ###

import sys
 
stdin=sys.stdin
sys.setrecursionlimit(10 ** 7)
ni=lambda:int(ns())
na=lambda:list(map(int,stdin.readline().split()))
ns=lambda:stdin.readline().rstrip()  # ignore trailing spaces


n,q=na()
AB=[[int(x) for x in na()] for _ in range(n-1)]
PX=[[int(x) for x in na()] for _ in range(q)]

graph=[[] for _ in range(n+1)]
values=[0]*(n+1)

for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

for p,x in PX:
    values[p]+=x

#print(graph)

def dfs(x,parent,add):
    values[x]+=add
    for i in graph[x]:
        if i==parent:
            continue
        dfs(i,x,values[x])

dfs(1,0,0)

print(' '.join(map(str,values[1:])))


### FIXED CODE ###

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

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
ai_sum=0
for i in range(n):
    ai_sum+=a[i]
    clear=True
    scale=ai_sum
    for j in range(i+1,n):
        if(2*scale>=a[j]):
            scale+=a[j]
        else:
#            print(i,j,scale)
            i=j
            clear=False
            break

    if(clear):
        ans=n-i
        break

print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
sum_former=sum(a)
for i in range(n-1,-1,-1):
    sum_former-=a[i]
    if(2*sum_former < a[i]):
        ans=n-i
        break

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

from math import ceil
import numpy as np
def main():
    N, K = map(int,input().split())
    A = np.array(list(map(int,input().split())), dtype="i8")
    C = np.array(list(map(int,input().split())), dtype="i8")
    A.sort()
    A = A[::-1]
    C.sort()
    def chk(x):
        cnt = 0
        for i in range(N):
            cnt += max(ceil(A[i]-x/C[i]), 0)
            if cnt > K:
                return False
        return True
    ng, ok = -1, 10**12
    while ok - ng > 1:
        m = (ok+ng)//2
        if chk(m):
            ok = m
        else:
            ng = m
    print(ok)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import ceil
def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    C = list(map(int,input().split()))
    A.sort(reverse=True)
    C.sort()
    def chk(x):
        cnt = 0
        for i in range(N):
            cnt += max(ceil(A[i]-x/C[i]), 0)
            if cnt > K:
                return False
        return True
    ng, ok = -1, 10**12
    while ok - ng > 1:
        m = (ok+ng)//2
        if chk(m):
            ok = m
        else:
            ng = m
    print(ok)
if __name__ == "__main__":
    main()
### BUGGY CODE ###


def main():
    
    N = int(input())

    A = [list(map(int, input().split())) for _ in range(N)]

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
        if check[i] >= N - 1:
            i += 1
            tmp += 1
            continue
        if flag[i] == False: #試合済みのとき
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]]
        # print (b)
        if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1] == True: #試合できる時
            check[i] += 1
            check[b - 1] += 1
            flag[i] = False
            flag[b - 1] = False
            tmp = 0
            count += 1
        i += 1
        tmp += 1
        if count == (N * (N - 1))//2:
            print (ans)
            exit()
        # print (check)

    # print (check)
    # for i in check:
    #     if i != N - 1:
    #         print (-1)
    #         exit()

    print (-1)
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)