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.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Accepted

Solution code:
from collections import deque
from typing import List, Optional, Tuple


def cycle_detectable_topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Tuple[Optional[List[int]], Optional[List[int]]]:
    """Topological sort that uses Kahn's algorithm and detects a loop (DAG or not).
    Returns:
        if the given graph is DAG, a list of sorted vertices and a list of depths of
        each vertex is returned.
        Otherwise, (None, None) is returned.
    """
    V = len(graph) + first_index
    order = []
    depths = [-1] * V  # depths[i] := the length of the longest path to V_i
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

    queue = deque(order)
    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = max(depths[v], cur_depth + 1)
                queue.append(v), order.append(v)
    return (order, depths) if len(order) + first_index == V else (None, None)


def abc139_e():
    N, *A = map(int, open(0).read().split())

    ids = [[-1] * (N + 1) for _ in range(N + 1)]
    cur_id = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            ids[i][j] = ids[j][i] = cur_id
            cur_id += 1

    graph = [[] for _ in range(N * (N - 1) // 2)]
    in_degrees = [0] * (N * (N - 1) // 2)
    for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
        source = -1
        for j in a:
            target = ids[i][j]
            if source != -1:
                graph[source].append(target)
                in_degrees[target] += 1
            source = target

    _, depths = cycle_detectable_topological_sort(graph, in_degrees)
    print(max(depths) + 1 if depths is not None else -1)


if __name__ == "__main__":
    abc139_e()

Submission status: Accepted

Solution code:
from collections import deque
from typing import List


def get_longest_path_depth(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> int:
    """Return the depth of the longest path of DAG.
    if the given graph is not DAG, -1 is returned.
    """
    V = len(graph) + first_index
    queue = deque()
    depths = [-1] * V  # depths[i] := the length of the longest path to V_i
    for i in range(first_index, V):
        if not in_degrees[i]:
            queue.append(i)
            depths[i] = 0

    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = max(depths[v], cur_depth + 1)
                queue.append(v)

    return max(depths[first_index:]) if min(depths[1:]) != -1 else -1


def abc139_e():
    N, *A = map(int, open(0).read().split())

    ids = [[-1] * (N + 1) for _ in range(N + 1)]
    cur_id = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            ids[i][j] = ids[j][i] = cur_id
            cur_id += 1

    graph = [[] for _ in range(N * (N - 1) // 2)]
    in_degrees = [0] * (N * (N - 1) // 2)
    for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
        source = -1
        for j in a:
            target = ids[i][j]
            if source != -1:
                graph[source].append(target)
                in_degrees[target] += 1
            source = target

    depth = get_longest_path_depth(graph, in_degrees)
    print(depth + 1 if depth != -1 else -1)


if __name__ == "__main__":
    abc139_e()

Submission status: Accepted

Solution code:
from collections import deque
from typing import List


def get_longest_path_depth(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> int:
    """Return the depth of the longest path of DAG.
    if the given graph is not DAG, -1 is returned.
    """
    V = len(graph) + first_index
    queue = deque()
    depths = [-1] * V  # depths[i] := the length of the longest path to V_i
    for i in range(first_index, V):
        if not in_degrees[i]:
            queue.append(i)
            depths[i] = 0

    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = max(depths[v], cur_depth + 1)
                queue.append(v)

    return max(depths) if -1 not in depths else -1


def abc139_e():
    N, *A = map(int, open(0).read().split())

    ids = [[-1] * (N + 1) for _ in range(N + 1)]
    cur_id = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            ids[i][j] = ids[j][i] = cur_id
            cur_id += 1

    graph = [[] for _ in range(N * (N - 1) // 2)]
    in_degrees = [0] * (N * (N - 1) // 2)
    for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
        source = -1
        for j in a:
            target = ids[i][j]
            if source != -1:
                graph[source].append(target)
                in_degrees[target] += 1
            source = target

    depth = get_longest_path_depth(graph, in_degrees)
    print(depth + 1 if depth != -1 else -1)


if __name__ == "__main__":
    abc139_e()

Submission status: Accepted

Solution code:
from collections import deque
from typing import List, Optional, Tuple


def cycle_detectable_topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Tuple[Optional[List[int]], Optional[List[int]]]:
    """Topological sort that uses Kahn's algorithm and detects a loop (DAG or not).
    Returns:
        if the given graph is DAG, a list of sorted vertices and a list of depths of
        each vertex is returned.
        Otherwise, (None, None) is returned.
    """
    V = len(graph) + first_index
    order = []
    depths = [-1] * V  # depths[i] := the length of the longest path to V_i
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

    queue = deque(order)
    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = max(depths[v], cur_depth + 1)
                queue.append(v), order.append(v)
    return (order, depths) if len(order) + first_index == V else (None, None)


def abc139_e():
    N, *A = map(int, open(0).read().split())

    ids = [[-1] * (N + 1) for _ in range(N + 1)]
    cur_id = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            ids[i][j] = ids[j][i] = cur_id
            cur_id += 1

    graph = [[] for _ in range(N * (N - 1) // 2)]
    in_degrees = [0] * (N * (N - 1) // 2)
    for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
        prev_id = -1
        for j in a:
            cur_id = ids[i][j]
            if prev_id != -1:
                graph[prev_id].append(cur_id)
                in_degrees[cur_id] += 1
            prev_id = cur_id

    _, depths = cycle_detectable_topological_sort(graph, in_degrees)
    print(max(depths) + 1 if depths is not None else -1)


if __name__ == "__main__":
    abc139_e()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# E - League
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]:  # The player has finished all games.
            continue
        opponent = schedules[player].popleft()

        # The opponent will have another game before playing against x.
        if next_opponents[opponent] != player:
            next_opponents[player] = opponent
            continue

        # The opponent's next game is against the player and vice versa.
        matched_games_cnt += 1
        last_games_days[player] = last_games_days[opponent] = (
            max(last_games_days[player], last_games_days[opponent]) + 1
        )
        # No next game is currently planned.
        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()

Submission status: Accepted

Solution code:
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

# プレイヤーiの試合の依存関係の情報をグラフ化
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)

Submission status: Accepted

Solution code:
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
  #print(g)
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    #print(dp)
  print(ans+1)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env 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, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    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()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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:
#        print(ng,ht)
        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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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
    #A = [LI() for _ in range(N)]
    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]
            #print(fr,to)
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    # https://mhiro216.hatenablog.com/entry/2019/09/08/142414
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  # 計算が終わっていない頂点を2度訪れるのはループがあるということ
            return dp[v]
        visited[v] = True
        for u in V[v]:  # 全ての辺をなめる
            res = dfs(u)
            if res == -1: return -1  # ループがあれば-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')  # ループがあれば-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
    #A = [LI() for _ in range(N)]
    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]
            #print(fr,to)
            V[fr].append(to)
    #print(V)


    # 閉路検出
    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()
    #print(X)
    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()

"""

"""

Submission status: Accepted

Solution code:
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
    #A = [LI() for _ in range(N)]
    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]
            #print(fr,to)
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    # https://mhiro216.hatenablog.com/entry/2019/09/08/142414
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  # 計算が終わっていない頂点を2度訪れるのはループがあるということ
            return dp[v]
        visited[v] = True
        for u in V[v]:  # 全ての辺をなめる
            res = dfs(u)
            if res == -1: return -1  # ループがあれば-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')  # ループがあれば-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
    #A = [LI() for _ in range(N)]
    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]
            #print(fr,to)
            V[fr].append(to)
    #print(V)


    # 閉路検出
    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()
    #print(X)
    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()

"""

"""