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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def topological_sort(graph):
  d = {i:1 for i in nodes}
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      #d[y] = max(d[x]+1,d[y])
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None,d
  return ret,d

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans,d = topological_sort(graph)
if not ans:
  print(-1)
else:
  print(max(d[i] for i in nodes))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def topological_sort(graph):
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None
  return ret

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now
exit()
ans = topological_sort(graph)
if not ans:
  print(-1)
else:
  d = {i:1 for i in nodes}
  for x in ans:
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
  print(max(d[i] for i in nodes))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def topological_sort(graph):
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None
  return ret

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now
exit()

ans = topological_sort(graph)
if not ans:
  print(-1)
else:
  d = {i:1 for i in nodes}
  for x in ans:
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
  print(max(d[i] for i in nodes))

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

    n = ni()
    d = [nb() for _ in range(n)]
    table = [[[2, []] for _ in range(n)] for _ in range(n)]

    que = queue.Queue()

    for i in range(n):
        s = min(i, d[i][0])
        l = max(i, d[i][0])
        table[s][l][0] -= 1

        if i == d[d[i][0]][0]:
            if i < d[i][0]:
                que.put([s, l])

        for j in range(n - 2):
            s1 = min(i, d[i][j])
            l1 = max(i, d[i][j])
            s2 = min(i, d[i][j + 1])
            l2 = max(i, d[i][j + 1])
            table[s1][l1][1].append([s2, l2])
            # table[s2][l2][0] += 1

    cnt = 0
    while que.qsize() > 0:
        cnt += 1
        flg = True

        for i in range(que.qsize()):
            x, y = que.get()
            for xi, yi in table[x][y][1]:
                table[xi][yi][0] -= 1
                if table[xi][yi][0] == 0:
                    flg = False
                    que.put([xi, yi])

        if flg and que.qsize() > 0:
            print(-1)
            exit(0)

    print(cnt if cnt > 0 else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
wait=[[-1]*N for _ in range(N)]
for i in range(N):
  wait[A[i][0]-1][i]=0
L=[list(range(N)),[]]
finish=[0]*N

day=0
ind=0
while L[ind]:
  day+=1
  for player in L[ind]:
    if finish[player]>=N-1:
      continue
    enemy=A[player][finish[player]]-1
    if wait[player][enemy]<day:
      finish[player]+=1
      finish[enemy]+=1
      if finish[player]<N-1:
        wait[A[player][finish[player]]-1][player]=day
      if finish[enemy]<N-1:
        wait[A[enemy][finish[enemy]]-1][enemy]=day
      L[(ind+1)%2].append(player)
      L[(ind+1)%2].append(enemy)
  L[ind]=[]   
  ind=(ind+1)%2
if min(finish)<N-1:
  print(-1)
else:
  print(day)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
# print(max(used))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
# print(edges)
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            if used[u] == 0:
                q.append(u)
                used[u] = max(used[u], used[v] + 1)
            
print(max(used)+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    prev = 0
    for e in r:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            if used[u] == 0:
                q.append(u)
                used[u] = used[v] + 1
            
print(max(used))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
count = [0 for i in range(N)]
total=0

day = 1
while 1:
  ed=[]
  ok=0
  for i in range(N):
    if count[i]>=N-1:continue
    j = A[i][count[i]]-1
    if j in ed:continue
    if A[j][count[j]]-1==i:
      count[i]+=1
      count[j]+=1
      total+=1
      ok=1
      ed.append(i)
      ed.append(j)
  if ok==1:day+=1
  else:
    print(-1)
    break
  if total==N*(N-1)//2:break
if ok==1: print(day)

Submission status: Wrong Answer

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
            depths[v] = max(depths[v], cur_depth + 1)
            if not in_degrees[v]:
                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]
            print(i, j, cur_id)
            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: Wrong Answer

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: Wrong Answer

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):
            res = False
            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:
                    break
            return res

        has_cycle = False

        for i in range(node):
            now_use = set()
            visited[i] = True
            if used[i]:
                continue
            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(V):
        visited = [False]*node
        def dfs(s,p=-1):
            res = 0

            if not s in V:
                return res+1

            for v in V[s]:
                if v==p:
                    continue
                n = node_v[v]
                visited[n] = True
                child = dfs(v, s)
                if res<child:
                    res = child

                visited[n] = False

            return res+1

        max_length = 0

        for i in V.keys():
            length = dfs(i)
            if max_length<length:
                max_length = length

        return max_length

    #ans = getMaxLength(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: Wrong Answer

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(V):
        visited = [False]*node
        used = set()

        def dfs(s, p=-1):
            res = False
            now_use.add(s)
            if s in used:
                return False

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

        has_cycle = False
        for i in range(node):
            now_use = set()
            if i in used:
                continue
            if dfs(i):
                has_cycle = True
                break
            used |= now_use
        #print(has_cycle)
        return has_cycle

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

    def getMaxLength(V):
        visited = [False]*node
        def dfs(s,p=-1):
            res = 0

            if not s in V:
                return res+1

            for v in V[s]:
                if v==p:
                    continue
                n = node_v[v]
                visited[n] = True
                child = dfs(v, s)
                if res<child:
                    res = child

                visited[n] = False

            return res+1

        max_length = 0

        for i in V.keys():
            length = dfs(i)
            if max_length<length:
                max_length = length

        return max_length

    #ans = getMaxLength(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()

"""

"""