Problem:
 Score : 500 points    Problem Statement N players will participate in a tennis tournament. We will call them Player 1 , Player 2 , \ldots , Player N .  The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.   Each player plays at most one matches in a day.  Each player i  (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.       Constraints  3 \leq N \leq 1000  1 \leq A_{i, j} \leq N  A_{i, j} \neq i  A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.         Input Input is given from Standard Input in the following format:  N  A_{1, 1}  A_{1, 2}  \ldots  A_{1, N-1}  A_{2, 1}  A_{2, 2}  \ldots  A_{2, N-1}  :  A_{N, 1}  A_{N, 2}  \ldots  A_{N, N-1}       Output If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1 .        Sample Input 1 3
2 3
1 3
1 2      Sample Output 1 3  All the conditions can be satisfied if the matches are scheduled for three days as follows:   Day 1 : Player 1 vs Player 2  Day 2 : Player 1 vs Player 3  Day 3 : Player 2 vs Player 3   This is the minimum number of days required.       Sample Input 2 4
2 3 4
1 3 4
4 1 2
3 1 2      Sample Output 2 4  All the conditions can be satisfied if the matches are scheduled for four days as follows:   Day 1 : Player 1 vs Player 2 , Player 3 vs Player 4  Day 2 : Player 1 vs Player 3  Day 3 : Player 1 vs Player 4 , Player 2 vs Player 3  Day 4 : Player 2 vs Player 4   This is the minimum number of days required.       Sample Input 3 3
2 3
3 1
1 2      Sample Output 3 -1  Any scheduling of the matches violates some condition.

Solution (Python):
from collections import deque

n = int(input())
m = n * (n - 1) // 2
b = [[0, 0] for _ in range(m + 1)]
f = [0] * (m + 1)
q = deque()
for i in range(1, n + 1):
    a = list(map(int, input().split()))
    for j in range(n - 1):
        ma, mi = max(i, a[j]), min(i, a[j])
        x = (ma - 1) * (ma - 2) // 2 + mi
        if j == 0:
            f[x] += 1
            if f[x] == 2:
                q.append(x)
        else:
            if b[y][0] == 0:
                b[y][0] = x
            else:
                b[y][1] = x
        y = x
ans = 0
while q:
    ans += 1
    l = len(q)
    for _ in range(l):
        i = q.popleft()
        for j in range(2):
            k = b[i][j]
            f[k] += 1
            if f[k] == 2 and not k == 0:
                q.append(k)
print(ans if f[0] == n else -1)

Solution (Python):

import sys
from collections import deque
from typing import Deque, List

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    schedules: List[Deque[int]] = [deque()] + [
        deque(map(int, line.split())) for line in readlines()
    ]
    matched_games_cnt = 0
    next_opponents, last_games_days = [0] * (N + 1), [0] * (N + 1)
    queue = deque(range(1, N + 1))
    while queue:
        player = queue.popleft()
        if not schedules[player]:  
            continue
        opponent = schedules[player].popleft()

        
        if next_opponents[opponent] != player:
            next_opponents[player] = opponent
            continue

        
        matched_games_cnt += 1
        last_games_days[player] = last_games_days[opponent] = (
            max(last_games_days[player], last_games_days[opponent]) + 1
        )
        
        next_opponents[player] = next_opponents[opponent] = 0
        queue.append(player), queue.append(opponent)

    print(max(last_games_days) if matched_games_cnt == N * (N - 1) // 2 else -1)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
to = [[]for _ in range(MAXV)]
id = [[0]*MAXN for _ in range(MAXN)]


def toId(i, j):
    return id[min(i, j)][max(i, j)]


visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV


def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nv in to[v]:
        res = dfs(nv)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res + 1)
    calculated[v] = True
    return dp[v]


a = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    for j in range(N-1):
        a[i][j] -= 1
vid = 0
for i in range(N):
    for j in range(N):
        if i < j:
            id[i][j] = vid
            vid += 1


for i in range(N):
    for j in range(N-1):
        a[i][j] = toId(i, a[i][j])
    for j in range(N-2):
        to[a[i][j+1]].append(a[i][j])
ans = 0

for i in range(vid):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        return dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    mi.discard(t)
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    
  print(ans+1)

if __name__=='__main__':
  main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = [deque(list(map(int, input().split()))) for _ in range(n)]

    que = deque()
    for i in range(n):
        que.append(i)

    res = 0
    while True:
        tmp = deque()
        used = set()
        while que:
            idx = que.popleft()
            if A[idx]:
                a = A[idx][0] - 1
                if idx in used or a in used:
                    continue
                if A[a][0] - 1 == idx:
                    A[idx].popleft()
                    A[a].popleft()
                    used.add(idx)
                    used.add(a)
                    tmp.append(idx)
                    tmp.append(a)
        if tmp:
            res += 1
            que = tmp
        else:
            break

    for a in A:
        if a:
            print(-1)
            break
    else:
        print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):

import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    
    
    

    N = int(input())

    A_all = []
    for i in range(N):
        As = list(map(int, input().split()))
        A_all.append(As)
    A_index = [0] * N

    candidates = set(range(1, N+1))
    for i in range(N * (N - 1) // 2 + 1):
        matches = set()
        for j in candidates:
            A_idx = A_index[j - 1]
            if A_idx >= N - 1:
                continue
            k = A_all[j - 1][A_idx]
            B_idx = A_index[k - 1]
            if B_idx >= N - 1:
                continue
            if j == A_all[k - 1][B_idx]:
                pair = tuple(sorted([j, k]))
                matches.add(pair)

        if not matches:
            break

        candidates = set()
        for match in matches:
            for j in match:
                A_index[j - 1] += 1
                candidates.add(j)

    if all([A_idx == N - 1 for A_idx in A_index]):
        print(i)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [[]]
    for i in range(n):
        a.append([int(i) for i in ipt().split()])
    ta = [1]*(n+1)
    ht = [[0]*(n+1) for i in range(n+1)]
    ng = []
    for i in range(1,n+1):
        ai = min(i,a[i][0])
        bi = max(i,a[i][0])
        if ht[ai][bi]:
            ng.append((ai,bi))
        ht[ai][bi] += 1
    t = 0
    d = 0
    while ng:

        pg = []
        for ag,bg in ng:
            tag = ta[ag]
            if tag != n-1:
                aai = min(ag,a[ag][tag])
                abi = max(ag,a[ag][tag])
                if ht[aai][abi]:
                    pg.append((aai,abi))
                ht[aai][abi] += 1
                ta[ag] += 1
            tbg = ta[bg]
            if tbg != n-1:
                bai = min(bg,a[bg][tbg])
                bbi = max(bg,a[bg][tbg])
                if ht[bai][bbi]:
                    pg.append((bai,bbi))
                ht[bai][bbi] += 1
                ta[bg] += 1
            t += 1
        d += 1
        ng = pg*1

    if t == n*(n-1)//2:
        print(d)
    else:
        print(-1)



    return None

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = [list(int(x) - 1 for x in input().split()) for _ in range(n)]
B = [0] * n

ans = 1
stack = [i for i in range(n)]
while True:
    day_set = set()
    next_stack = []
    while stack:
        i = stack.pop()
        if i in day_set or B[i] >= n - 1:
            continue
        j = A[i][B[i]]
        if j in day_set or B[j] >= n - 1:
            continue
        if A[j][B[j]] == i:
            B[i] += 1
            B[j] += 1
            day_set.add(i)
            day_set.add(j)
            next_stack += [i, j]
            if all(b >= n - 1 for b in B):
                print(ans)
                exit()

    if not day_set:
        print(-1)
        exit()
    ans += 1
    stack = next_stack

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  
            return dp[v]
        visited[v] = True
        for u in V[v]:  
            res = dfs(u)
            if res == -1: return -1  
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  
            return
    print(ans)
    return

def examE2():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)
    


    
    def hasCycle(n,V):
        visited = [False]*n
        used = [False]*n

        def dfs(s, p=-1):
            if used[s]:
                return False

            now_use.add(s)

            for v in V[s]:
                if visited[v]:
                    return True
                if v in now_use:
                    continue
                visited[v] = True
                res = dfs(v, s)
                visited[v] = False
                if res:
                    return True
            return False

        has_cycle = False

        for i in range(node):
            now_use = set()
            if used[i]:
                continue
            visited[i] = True
            if dfs(i):
                has_cycle = True
                break
            for u in now_use:
                used[u] = True
            visited[i] = False

        return has_cycle

    if hasCycle(node,V):
        print(-1)
        return

    def getMaxLength(n,V):
        visited = [False]*n
        max_lens = [0] * n

        def dfs(s,p=-1):
            res = 0

            for v in V[s]:
                if max_lens[v]>0:
                    child = max_lens[v]
                else:
                    visited[v] = True
                    child = dfs(v, s)
                    visited[v] = False
                if res<child:
                    res = child
            max_lens[s] = res + 1

            return res+1

        for i in range(n):
            if max_lens[i]>0:
                continue
            dfs(i)

        return max(max_lens)

    ans = getMaxLength(node,V)
    print(ans)
    return

def examF():
    
    def calc_L(a,b):
        return (a**2 + b**2)**(1/2)
    N = I()
    X = [[]for _ in range(N)]
    for i in range(N):
        x,y = LI()
        d = math.degrees(math.atan2(y,x))
        if d<0:
            d += 360
        X[i] = [d,x,y]
    X.sort()
    
    ans = 0
    for i in range(N):
        cur_X = 0; cur_Y = 0
        for d2,x2,y2 in (X[i:] + X[:i]):
            if calc_L(cur_X+x2,cur_Y+y2)<calc_L(cur_X,cur_Y):
                continue
            cur_X += x2
            cur_Y += y2

        now = calc_L(cur_X,cur_Y)
        if now>ans:
            ans = now

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE2()

"""

"""

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  
            return dp[v]
        visited[v] = True
        for u in V[v]:  
            res = dfs(u)
            if res == -1: return -1  
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  
            return
    print(ans)
    return

def examE2():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)
    


    
    def hasCycle(n,V):
        visited = [False]*n
        used = [False]*n

        def dfs(s, p=-1):
            if used[s]:
                return False

            now_use.add(s)

            for v in V[s]:
                if visited[v]:
                    return True
                if v in now_use:
                    continue
                visited[v] = True
                res = dfs(v, s)
                visited[v] = False
                if res:
                    return True
            return False

        has_cycle = False

        for i in range(node):
            now_use = set()
            if used[i]:
                continue
            visited[i] = True
            if dfs(i):
                has_cycle = True
                break
            for u in now_use:
                used[u] = True
            visited[i] = False

        return has_cycle

    if hasCycle(node,V):
        print(-1)
        return

    def getMaxLength(n,V):
        visited = [False]*n
        max_lens = [0] * n

        def dfs(s,p=-1):
            res = 0

            for v in V[s]:
                if max_lens[v]>0:
                    child = max_lens[v]
                else:
                    visited[v] = True
                    child = dfs(v, s)
                    visited[v] = False
                if res<child:
                    res = child
            max_lens[s] = res + 1

            return res+1

        for i in range(n):
            if max_lens[i]==0:
                dfs(i)

        return max(max_lens)

    ans = getMaxLength(node,V)
    print(ans)
    return

def examF():
    
    def calc_L(a,b):
        return (a**2 + b**2)**(1/2)
    N = I()
    X = [[]for _ in range(N)]
    for i in range(N):
        x,y = LI()
        d = math.degrees(math.atan2(y,x))
        if d<0:
            d += 360
        X[i] = [d,x,y]
    X.sort()
    
    ans = 0
    for i in range(N):
        cur_X = 0; cur_Y = 0
        for d2,x2,y2 in (X[i:] + X[:i]):
            if calc_L(cur_X+x2,cur_Y+y2)<calc_L(cur_X,cur_Y):
                continue
            cur_X += x2
            cur_Y += y2

        now = calc_L(cur_X,cur_Y)
        if now>ans:
            ans = now

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE2()

"""

"""

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  
            return dp[v]
        visited[v] = True
        for u in V[v]:  
            res = dfs(u)
            if res == -1: return -1  
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  
            return
    print(ans)
    return

def examE2():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)
    


    
    def hasCycle(n,V):
        visited = [False]*n
        used = [False]*n

        def dfs(s, p=-1):
            if used[s]:
                return False

            now_use.add(s)

            for v in V[s]:
                if visited[v]:
                    return True
                if v in now_use:
                    continue
                visited[v] = True
                res = dfs(v, s)
                visited[v] = False
                if res:
                    return True
            return False

        has_cycle = False

        for i in range(node):
            now_use = set()
            if used[i]:
                continue
            visited[i] = True
            if dfs(i):
                has_cycle = True
                break
            for u in now_use:
                used[u] = True
            visited[i] = False

        return has_cycle

    if hasCycle(node,V):
        print(-1)
        return

    def getMaxLength(n,V):
        visited = [False]*n
        max_lens = [0] * n

        def dfs(s,p=-1):
            res = 0

            for v in V[s]:
                if max_lens[v]>0:
                    child = max_lens[v]
                else:
                    visited[v] = True
                    child = dfs(v, s)
                    visited[v] = False
                if res<child:
                    res = child
            max_lens[s] = res + 1

            return res+1

        for i in range(n):
            if max_lens[i]==0:
                dfs(i)

        return max(max_lens)

    ans = getMaxLength(node,V)
    print(ans)
    return

def examF():
    
    def calc_L(a,b):
        return (a**2 + b**2)**(1/2)
    N = I()
    X = [[]for _ in range(N)]
    for i in range(N):
        x,y = LI()
        d = math.degrees(math.atan2(y,x))
        if d<0:
            d += 360
        X[i] = [d,x,y]
    X.sort()
    
    ans = 0
    for i in range(N):
        cur_X = 0; cur_Y = 0
        for d2,x2,y2 in (X[i:] + X[:i]):
            if calc_L(cur_X+x2,cur_Y+y2)<calc_L(cur_X,cur_Y):
                continue
            cur_X += x2
            cur_Y += y2

        now = calc_L(cur_X,cur_Y)
        if now>ans:
            ans = now

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE2()

"""

"""

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  
            return dp[v]
        visited[v] = True
        for u in V[v]:  
            res = dfs(u)
            if res == -1: return -1  
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  
            return
    print(ans)
    return

def examE2():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)
    


    
    def hasCycle(n,V):
        visited = [False]*n
        used = [False]*n

        def dfs(s, p=-1):
            if used[s]:
                return False

            now_use.add(s)

            for v in V[s]:
                if visited[v]:
                    return True
                if v in now_use:
                    continue
                visited[v] = True
                res = dfs(v, s)
                visited[v] = False
                if res:
                    return True
            return False

        has_cycle = False

        for i in range(node):
            now_use = set()
            if used[i]:
                continue
            visited[i] = True
            if dfs(i):
                has_cycle = True
                break
            for u in now_use:
                used[u] = True
            visited[i] = False

        return has_cycle

    if hasCycle(node,V):
        print(-1)
        return

    def getMaxLength(n,V):
        visited = [False]*n
        max_lens = [0] * n

        def dfs(s,p=-1):
            res = 0

            for v in V[s]:
                if max_lens[v]>0:
                    child = max_lens[v]
                else:
                    visited[v] = True
                    child = dfs(v, s)
                    visited[v] = False
                if res<child:
                    res = child
            max_lens[s] = res + 1

            return res+1

        for i in range(n):
            if max_lens[i]>0:
                continue
            length = dfs(i)

        return max(max_lens)

    ans = getMaxLength(node,V)
    print(ans)
    return

def examF():
    
    def calc_L(a,b):
        return (a**2 + b**2)**(1/2)
    N = I()
    X = [[]for _ in range(N)]
    for i in range(N):
        x,y = LI()
        d = math.degrees(math.atan2(y,x))
        if d<0:
            d += 360
        X[i] = [d,x,y]
    X.sort()
    
    ans = 0
    for i in range(N):
        cur_X = 0; cur_Y = 0
        for d2,x2,y2 in (X[i:] + X[:i]):
            if calc_L(cur_X+x2,cur_Y+y2)<calc_L(cur_X,cur_Y):
                continue
            cur_X += x2
            cur_Y += y2

        now = calc_L(cur_X,cur_Y)
        if now>ans:
            ans = now

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE2()

"""

"""