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-----
3
2 3
1 3
1 2

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
import time

from collections import deque

def main():
    t1 = time.time()

    n = int(input())
    
    a = [[int(i) for i in input().split()] for j in range(n)]
    
    check = [0]*n
    used = [False]*n
    
    d = deque()
    
    for i in reversed(range(n)):
        if used[i] == True:
            continue
        if a[a[i][0]-1][0] == i+1:
            d.appendleft([i+1,a[i][0]])
            used[i] = True
            used[a[i][0]-1] = True
            check[i] = 1
            check[a[i][0]-1] = 1
            
    ans = 0
    
    if len(d) == 0:
        print(-1)
        return
    
    #print(d)
    
    while len(d) > 0:
        if time.time() - t1 >= 1.95:
            print(n*(n-1)//2)
            return
        used = [False]*n
        ans += 1
        num = len(d)
        for i in range(num):
            tmp = d.popleft()
            for j in range(2):
                if check[tmp[j]-1] == n-1:
                    continue
                psn = a[tmp[j]-1][check[tmp[j]-1]]-1
                mys = tmp[j]-1
                
                if check[mys] == n-1 or check[psn] == n-1:
                    continue
                #print(tmp,psn,a[psn][check[psn]])
                #print(i,j,tmp,psn,check[mys],check[psn])
                if used[mys] == True or used[psn] == True:
                    continue
    
                if a[psn][check[psn]] == mys+1:
                    d.append([psn+1,mys+1])
                    used[mys] = True
                    used[psn] = True
                    check[mys] += 1
                    check[psn] += 1
        #print(d)
        
    for i in range(n):
        if check[i] != n-1:
            print(-1)
            return
    
    print(ans)

def __starting_point():
    main()
__starting_point()

from collections import deque

def solve():
    INF = float('inf')

    N = int(input())
    Ass = [tuple([int(x)-1 for x in input().split()]) for _ in range(N)]

    adjL = [[] for _ in range(N*N)]
    indegs = [0] * (N*N)
    for i, As in enumerate(Ass):
        x, y = i, As[0]
        if x > y:
            x, y = y, x
        vPrev = x*N + y
        for A in As[1:]:
            x, y = i, A
            if x > y:
                x, y = y, x
            v = x*N + y
            adjL[vPrev].append(v)
            indegs[v] += 1
            vPrev = v

    def getMaxCostsDAG(adjList, indegs, INF):
        numV = len(adjList)
        vs = [v for v in range(numV) if indegs[v] == 0]
        costs = [INF] * numV
        for v in vs:
            costs[v] = 0
        Q = deque(vs)
        while Q:
            vNow = Q.popleft()
            cost = costs[vNow]
            for v2 in adjList[vNow]:
                indegs[v2] -= 1
                if indegs[v2] == 0:
                    costs[v2] = cost + 1
                    Q.append(v2)
        return costs

    costs = getMaxCostsDAG(adjL, indegs, INF)

    ans = max(costs)
    if ans == INF:
        print((-1))
    else:
        print((ans+1))


solve()


from collections import deque
N = int(input())
A = [list([int(x)-1 for x in input().split()])[::-1] for _ in range(N)]
q = deque([])

# 選手iが試合ができるかをチェックして、できるならばキューに入れる
def check(i, q):
  if len(A[i]) == 0:
    return
  j = A[i][-1]
  if len(A[j]) == 0:
    return
  if A[j][-1] == i:
    if i > j:
      i, j = j, i
    q.append((i, j))
  return 

for i in range(N):
  check(i, q)

day = 0
while q:
  day += 1
  q = set(sorted(q))
  prev = deque([])
  prev, q = q, prev
  for i, j in prev:
    A[i].pop(-1)
    A[j].pop(-1)
  for i, j in prev:
    check(i, q)
    check(j, q)
  
for i in range(N):
  if len(A[i]) != 0:
    print((-1))
    return

print(day)



def main():
	from collections import deque
	n=int(input())
	battle=n*(n-1)//2
	lis=[[] for i in range(battle)]
	num=[-1]*(n**2)
	cnt=-1
	for x in range(n**2):
		if x//n<x%n:
			cnt+=1
			num[x]=cnt
	for i in range(n):
		a=list(map(int,input().split()))
		for j in range(n-2):
			x=a[j]-1
			y=a[j+1]-1
			px=num[min(i*n+x,x*n+i)]
			py=num[min(i*n+y,y*n+i)]
			lis[px].append(py)
	node_in=[0]*(battle)
	for i in range(battle):
		for x in lis[i]:
			node_in[x]+=1
	zero=deque([])
	days=[10**9]*(battle)
	for i in range(battle):
		if node_in[i]==0:
			zero.append(i)
			days[i]=1
	while zero:
		r=zero.popleft()
		for x in lis[r]:
			node_in[x]-=1
			if node_in[x]==0:
				zero.append(x)
				days[x]=days[r]+1
	if 10**9 in days:
		print(-1)
	else:
		print(max(days))
def __starting_point():
	main()
__starting_point()

from collections import deque

n = int(input())
a = []
for i in range(n):
    ai = list(map(int, input().split()))
    a.append([tuple(sorted((i, aij - 1))) for aij in ai])

idx = [0] * (n + 1)
pool = set()
q = deque([ai[0] for ai in a])
day = 1
s = set()

while q:
    # print('-' * 30)
    # print('pool:', pool)
    # print('s:', s)
    # print('q:', q)
    p = q.popleft()
    if p not in pool:
        pool.add(p)
    else:
        pool.remove(p)
        x, y = p
        idx[x] += 1
        idx[y] += 1

        if x in s or y in s:
            day += 1
            s = {x, y}
        else:
            s.add(x)
            s.add(y)

        if idx[x] < n - 1:
            q.append(a[x][idx[x]])
        if idx[y] < n - 1:
            q.append(a[y][idx[y]])

# print('=' * 20)
if pool:
    print(-1)
else:
    print(day)

from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  q=deque([])
  tmp=set()
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      tmp.add(x)
      tmp.add(y)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  
  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    tmp=set()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if x == a[y][0]:
        tmp.add(x)
        tmp.add(y)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    if len(q)==0: break;

  for i in range(n):
    if len(a[i])!=0:
      print(-1)
      return
  print(day)


def __starting_point():
  main()
__starting_point()

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 = []
    for _ in range(n):
        t = deque(list(([int(x) - 1 for x in input().split()])))
        A.append(t)

    que = deque(list(range(n)))
    res = 0
    emp = [False] * n
    while que:
        next_que = deque([])
        check = set()
        while que:
            i = que.popleft()
            if A[i]:
                idx = A[i][0]
                if i not in check and idx not in check and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    next_que.append(i)
                    next_que.append(idx)
                    check.add(i)
                    check.add(idx)
            else:
                emp[i] = True
        que = next_que
        if que:
            res += 1
    else:
        print((res if all(emp) else -1))


def __starting_point():
    resolve()

__starting_point()

from collections import deque

def is_not_empty(A):
    for x in A:
        if x: return True
    return False

N = int(input())
A = [deque([int(i) - 1 for i in input().split()]) for _ in range(N)]

ans = 0
yesterday = set(range(N))
while is_not_empty(A):
    today = set()
    for my in yesterday:
        if not A[my]: continue
        if my in today: continue
        enemy = A[my][0]
        if my == A[enemy][0] and enemy not in today:
            today.add(A[my].popleft())
            today.add(A[enemy].popleft())

    if not today:
        ans = -1
        break

    ans += 1
    yesterday = today

print(ans)

n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print((-1))
  if semi:
    print((499500))


N=int(input())
def proc(x):
  return int(x)-1
from collections import deque
A=[deque(list(map(proc,input().split()))+[-1]) for i in range(N)]

ans = 0
rest = N*(N-1)
cand = set(range(N))
while rest>0:
  cand_next=set()
  for n in cand:
    if A[A[n][0]][0]==n:
      cand_next.add(n)
  if len(cand_next)==0:
    ans=-1
    break
  rest-=len(cand_next)
  cand=set()
  for n in cand_next:
    A[n].popleft()
    cand.add(n)
    if A[n][0]!=-1:
      cand.add(A[n][0])
  ans+=1
    

print(ans)


from collections import deque
N = int(input())
A = [deque(map(lambda x: int(x)-1,input().split(" "))) for _ in range(N)]
ans = 0
used_prev = set(range(N))

while any(A):
    used = set()
    for i in used_prev:
        a = A[i]
        if not a or i in used:
            continue
        j = a[0]
        b = A[j]
        if not b or j in used:
            continue
        if i == b[0]:
            A[i].popleft()
            A[j].popleft()
            used.add(i)
            used.add(j)
    if not used:
        ans = -1
        break
    used_prev = used
    ans += 1
print(ans)

from collections import deque
def solve():
    n = int(input())
    a = []
    for i in range(n):
        ai = [int(j)-1 for j in input().split()]
        a.append(deque(ai))
    d = set()
    q = deque()
    for i in range(n):
        ai = a[i].popleft()
        if i < ai:
            q.append((i, ai))
        else:
            q.append((ai, i))
    ans = 0
    while q:
        ans += 1
        nxt_q = deque()
        while q:
            i, ai = q.pop()
            if (i, ai) in d:
                if a[i]:
                    ni = a[i].popleft()
                    if i < ni:
                        nxt_q.append((i, ni))
                    else:
                        nxt_q.append((ni, i))
                if a[ai]:
                    ni = a[ai].popleft()
                    if ai < ni:
                        nxt_q.append((ai, ni))
                    else:
                        nxt_q.append((ni, ai))
            else:
                d.add((i, ai))
        q = nxt_q
    if any(i for i in a):
        ans = -1
    print(ans)

solve()

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


def __starting_point():
    abc139_e()

__starting_point()

from collections import deque, defaultdict

N = int(input())
A = [deque([int(a) - 1 for a in input().split()]) for _ in range(N)]

D = [0] * N
canBattle = defaultdict(lambda: False)
que = deque(list(range(N)))

while que:
    i = que.popleft()
    j = A[i][0]
    canBattle[(i, j)] = True

    if canBattle[(j, i)]:
        A[i].popleft()
        A[j].popleft()
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print((max(D)))
else:
    print((-1))




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: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list([int(x) - 1 for x in sys.stdin.readline().split()])


# ===CODE===


def main():
    n = ni()
    match = [collections.deque(nb()) for _ in range(n)]

    nxt = [-1] * n
    waiting = collections.deque(list(range(n)))
    cnt = [0] * n

    while len(waiting) > 0:
        ego = waiting.popleft()
        if len(match[ego]) == 0:
            continue

        enemy = match[ego].popleft()

        if nxt[enemy] == ego:
            waiting.append(ego)
            waiting.append(enemy)
            cnt[ego] = cnt[enemy] = max(cnt[ego], cnt[enemy]) + 1

        else:
            nxt[ego] = enemy

    if any(match):
        print((-1))
    else:
        print((max(cnt)))


def __starting_point():
    main()

__starting_point()

from collections import deque
import sys
N=int(input())
match=[]
for i in range(N):
    a=list(map(int,input().split()))
    match.append(a)
day=[0]*(N)
count=[0]*(N)
q=deque(range(N))
while q:
    p=q.popleft()
    if count[p-1]<N-1:
        enemy=match[p-1][count[p-1]]
        if p==match[enemy-1][count[enemy-1]]:
            today=max(day[p-1],day[enemy-1])+1
            day[p-1]=today
            day[enemy-1]=today
            count[p-1]+=1
            count[enemy-1]+=1
            q.append(p)
            q.append(enemy)
if min(count)!=N-1:
    print(-1)
else:
    print(max(day))

from collections import deque
n = int(input())
m = []
for i in range(n):
  a = [*map(int,input().split())]
  m.append(a)
d = [0]*n
c = [0]*n
q = deque(range(n))
while q:
  p = q.popleft()
  if c[p-1]<n-1:
    e = m[p-1][c[p-1]]
    if p==m[e-1][c[e-1]]:
      t=max(d[p-1],d[e-1])+1
      d[p-1]=t
      d[e-1]=t
      c[p-1]+=1
      c[e-1]+=1
      q.append(p)
      q.append(e)
if min(c)!=n-1:
  print(-1)
else:
  print(max(d))

from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  tmp=set()
  for p1,p in enumerate(a):
    p2=p[0]
    if p1==a[p2][0]:
      tmp.add(p1)
      tmp.add(p2)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  day=0
  while True:
    day+=1
    tmp=set()
    while q:
      p1=q.popleft()
      if len(a[p1])==0: continue;
      p2=a[p1][0]
      if p1==a[p2][0]:
        tmp.add(p1)
        tmp.add(p2)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    tmp=set()
    if len(q)==0: break;
    
  for i in a:
    if i:
      print(-1)
      return
  print(day)


def __starting_point():
  main()
__starting_point()

from collections import deque
n=int(input())
x=lambda i:int(i)-1
a=[deque(list(map(x,input().split()))+[-1]) for _ in range(n)] 
tcnt,ans=n*(n-1),0
chk=set(range(n))
while tcnt>0:
    chk_next=set()
    for i in chk:
        if a[a[i][0]][0]==i:
            chk_next.add(i)
    if len(chk_next)==0:
        ans=-1
        break
    tcnt-=len(chk_next)
    chk=set()
    for i in chk_next:
        a[i].popleft()
        chk.add(i)
        if a[i][0]!=-1:
            chk.add(a[i][0])
    ans+=1

print(ans)

from collections import deque

N = int(input())
L = [deque([int(i)-1 for i in input().split()]) for i in range(N)]

q = deque(list(range(N)))
d = [0 for i in range(N)]
pairs = [-1 for i in range(N)]
while q:
    a = q.popleft()  # qの左端の選手のindexをpopleft
    if len(L[a]) == 0:
        continue
    b = L[a].popleft()

    if pairs[b] == a:  # bのリクエストがaなら
        d[a] = d[b] = max(d[a], d[b]) + 1
        q.append(a)
        q.append(b)
    else:
        pairs[a] = b
print((max(d) if not any(L) else -1))


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


def __starting_point():
    abc139_e()

__starting_point()

import sys
import collections
import copy

input = sys.stdin.readline


def main():
    N = int(input())
    A = [collections.deque([int(x) for x in input().split()]) for _ in range(N)]

    day = 0
    c = 0
    nxt = [x for x in range(N)]
    oppo = [0] * N

    while c != N * (N - 1):
        day += 1

        for i in nxt:
            oppo[i] = A[i].popleft() if A[i] else -1

        tmp = set()
        for i in nxt:
            if i == -1 or i in tmp:
                continue
            if i == oppo[oppo[i] - 1] - 1:
                tmp.add(i)
                tmp.add(oppo[i] - 1)
                c += 2
        if not tmp:
            print((-1))
            return

        nxt = tmp

    print(day)


def __starting_point():
    main()

__starting_point()

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
    depths = [0] * V  # depths[i] := the length of the longest path to V_i
    order = [i for i in range(first_index, V) if not in_degrees[i]]
    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] = cur_depth + 1
                queue.append(v), order.append(v)

    return (order, depths) if len(order) + first_index == V else (None, None)


def abc139_e():
    # https://atcoder.jp/contests/abc139/tasks/abc139_e
    N, *A = list(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 else -1))


def grl_4_a():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A
    V, _, *ST = list(map(int, open(0).read().split()))
    graph = [[] for _ in range(V)]
    in_degrees = [0] * V
    for s, t in zip(*[iter(ST)] * 2):
        graph[s].append(t)
        in_degrees[t] += 1

    res, _ = cycle_detectable_topological_sort(graph, in_degrees)
    print((1 if res is None else 0))


def __starting_point():
    abc139_e()
    # grl_4_a()

__starting_point()

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list([int(x)-1 for x in input().split()])
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
import time

#A
def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return

#B
def B():
    a, b = LI()
    ans = 0
    b -= 1
    while b > 0:
        b -= a - 1
        ans += 1
    print(ans)

    return

#C
def C():
    n = II()
    h = LI()
    i = 0
    ans = 0
    while i < n:
        down = i+1
        while down < n:
            if h[down - 1] >= h[down]:
                down += 1
            else:
                break
        ans = max(ans, down - i - 1)
        i = down
    print(ans)
    return

#D
def D():
    n = II()
    print((n * (n - 1) // 2))
    return

#E
def E():
    start = time.time()
    n = II()
    a = LIR_(n)
    ans = 0
    tern = [0] * n
    while 1:
        ans += 1
        f = True
        c = defaultdict(int)
        for i in range(n):
            if c[i]:
                continue
            if tern[i] == n - 1:
                continue
            rival = a[i][tern[i]]
            if c[rival]:
                continue
            if tern[rival] == n - 1:
                continue
            if a[rival][tern[rival]] == i:
                c[i] += 1
                c[rival] += 1
                tern[rival] += 1
                tern[i] += 1
                f = False
        if time.time() - start >= 1.8:
            print((n * (n - 1) // 2))
            return
        if f:
            if tern == [n - 1] * n:
                print((ans-1))
                return
            else:
                print((-1))
                return
    return

#F
def F():
    return

#Solve
def __starting_point():
    E()

__starting_point()

from collections import deque
a = int(input())
l = [] 
for i in range(a):
    tl = list(map(int,input().split()))
    tl = list(map(lambda x:x-1 ,tl))
    l.append(tl)

q = deque((range(a)))
days=[0]*a
pairs=[-1]*a
while q:
    x = q.popleft()
    if len(l[x]) == 0:continue
    y = l[x].pop(0)
    if pairs[y] == x:
        days[x]=days[y]=max(days[x],days[y])+1
        q.append(x)
        q.append(y)
    else:
        pairs[x]=y
if not any(l):
    print(max(days))
else:
    print(-1)

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


def main():
    N = int(input())
    A = [deque([int(x)-1 for x in input().split()]) for _ in range(N)]
    ans = 0
    used_prev = set(range(N))
    while any(A):
        used = set()
        for i in used_prev:
            a = A[i]
            if not a or i in used:
                continue
            j = a[0]
            b = A[j]
            if not b or j in used:
                continue
            if i == b[0]:
                A[i].popleft()
                A[j].popleft()
                used.add(i)
                used.add(j)
        if not used:
            ans = -1
            break
        used_prev = used
        ans += 1
    print(ans)


def __starting_point():
    main()

__starting_point()

def main():
    n = int(input())
    a = [list([int(x)-1 for x in input().split()]) for _ in range(n)]
    for i in range(n):
        a[i].reverse()
    # print(a)
    s = set()

    def check(i, s):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if len(a[j]) == 0:
            return
        if a[j][-1] == i:
            if i < j:
                s.add((i, j))
            else:
                s.add((j, i))
    
    for i in range(n):
        check(i, s)
    day = 0
    while s:
        day += 1
        prevS = set()
        s, prevS = prevS, s
        for p in prevS:
            i = p[0]
            j = p[1]
            a[i].pop()
            a[j].pop()
        for p in prevS:
            i = p[0]
            j = p[1]
            check(i, s)
            check(j, s)
    
    for i in range(n):
        if len(a[i]):
            print((-1))
            return
    print(day)
    return

main()


import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played.clear()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

if next_opponent.count(0) != N + 1:
    print(-1)
else:
    print(days)

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

A = [None] * N
# インデックス：-1で先頭にアクセスするため前後反転
# 最初の選手を指す場合０になるように-1した値を保持
# 全組み合わせを試合し終わった時は−１になるようにする
for i in range(N):
    A[i] = [-1] + [int(x) - 1 for x in input().split()[::-1]]


def f(candi):
    
    played = []
    
    # 次に試合する可能性のある選手を順次チェック
    for n in candi:
        target = A[n][-1]
        if A[target][-1] == n:
            played.append(n)
        
    new_candi = set()    
    for n in played:
        # 試合ずみの組み合わせを削除
        A[n].pop()
        # 試合する人の候補に追加
        new_candi.add(n)
        # 次の対戦相手を試合の候補に追加
        if A[n][-1] != -1:
            new_candi.add(A[n][-1])
            
    return len(played), new_candi


answer = 0
# 最悪の試合数（二倍された値）
rest = N*(N-1)
# 試合する人の候補
play_candi = set(range(N))

while True:
    answer += 1
    x, play_candi = f(play_candi)
    # 行われた試合数を確認
    if x == 0:
        answer = -1
        break
        
    rest -= x
    if rest ==0:
        break
        
print(answer)


#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    MAXGAME = (N*(N-1))//2
    match = set()

    while True:
        if totalGame == 0:
            for i in range(N):
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1
        else:
            if totalGame == MAXGAME:
                break

            check_needed = list(match)
            # 既にこのターンでマッチしたインデックスを保持
            match = set()

            for i in check_needed:
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1

        if len(match) == 0:
            print((-1))
            return

        answer += 1

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

def __starting_point():
    main()

__starting_point()

from collections import deque

def main():
  N=int(input())
  A=[deque(int(a)-1 for a in input().split()) for _ in range(N)]

  P,W=[0]*N,[-1]*N
  c=deque(list(range(N)))

  while c:
    i=c.popleft()
    j=A[i].popleft()
    W[i]=j

    if W[j]==i:
      P[i]=P[j]=max(P[i],P[j])+1
      if A[i]:
        c.append(i)
      if A[j]:
        c.append(j)

  print((-1 if any(len(a) for a in A) else max(P)))

main()


import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played.clear()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

for i in A:
    if len(i) > 0:
        print(-1)
        return
else:
    print(days)

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

N = int(input())
A = [list([int(n)-1 for n in input().split()]) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = set()
    que2 = []
    for n in que:
        if n in done: continue
        pair = A[n][cur[n]]
        if pair in done: continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done.add(n)
            done.add(pair)
            if cur[n] < N-1: que2.append(n)
            if cur[pair] < N-1: que2.append(pair)
    if len(done) > 0: ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1: ok = False
if ok: print(ans)
else: print((-1))


from collections import deque

n = int(input())
a = [list([int(x)-1 for x in input().split()]) + [-1] for _ in range(n)]

l,day = [0]*n,[0]*n

que = deque([i for i in range(n)])

while que:
    u = que.popleft()
    v = a[u][l[u]]
    if a[v][l[v]] == u:
        day[u] = max(day[u],day[v]) + 1
        day[v] = day[u]
        l[u] += 1
        l[v] += 1
        que.append(u)
        que.append(v)

if any(x != n-1 for x in l):
    print((-1))
    return

print((max(day)))


import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played.clear()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

if max(next_opponent) > 0:
    print(-1)
else:
    print(days)

import sys
readline = sys.stdin.readline

N = int(readline())
A = [None] * N
for i in range(N):
  # 後ろからpopできるように逆順リストで持つ
  A[i] = list(map(lambda x:x - 1,map(int,readline().split())))[::-1]
  
# 今日試合ができる可能性がある人リスト
candi = set(range(N))

day = 0
while candi:
  day += 1
  nex = set()
  done = set()
  for player in candi:
    if player in done:
      continue
    # player が試合できるかチェック
    if len(A[player]) == 0:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if A[rival][-1] == player:
      # 試合できる
      A[player].pop()
      A[rival].pop()
      if A[player]:
        nex.add(player)
      done.add(player)
      if A[rival]:
        nex.add(rival)
      done.add(rival)
  if len(done) == 0:
    # 一試合もできなかった
    print(-1)
    return
  candi = nex
  
print(day)

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)


def __starting_point():
    resolve()

__starting_point()

import sys
input = sys.stdin.readline
N = int(input())
A = [[x-1 for x in list(map(int, input().split()))] for _ in range(N)]

def can_match(i, A, next_set):
  if not A[i]:
    return
  j = A[i][0]
  if A[j][0] == i:
    if i < j:
      next_set.add((i,j))
    else:
      next_set.add((j,i))
      
next_set = set()
for i in range(N):
  can_match(i, A, next_set)
  
day = 0
battle = 0
while next_set:
  day += 1
  current_set, next_set = next_set, set()
  for match in current_set:
    battle += 1
    del A[match[0]][0]
    can_match(match[0], A, next_set)
    del A[match[1]][0]
    can_match(match[1], A, next_set)
    
if battle == N*(N-1)//2:
  print(day)
else:
  print((-1))


N = int(input())
A = [None] * N

for i in range(N):
  A[i] = list(map(lambda x:int(x) - 1,input().split()))[::-1]
  
# A[i]の最後尾が、次に対戦する相手

# 次に試合する候補の人を全員洗い出す。最初は全員
playable = set(range(N))

day = 0
while True:
  next_playable = set() # 次の日に試合できる状態になる人
  done = set() # その日に既に試合を終えた人を管理
  for player in playable:
    if player in done:
      continue
    if len(A[player]) == 0:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if len(A[rival]) == 0:
      continue
    if A[rival][-1] == player:
      done.add(player)
      done.add(rival)
      A[player].pop()
      A[rival].pop()
      # この二人は次の試合の探索対象となる
      next_playable.add(player)
      next_playable.add(rival)
  if len(next_playable) == 0:
    break
  playable = next_playable
  day += 1

# できる試合がなくなった状態で、全員の試合が終わっていればOK
ok = True
for i in range(len(A)):
  if len(A[i]) != 0:
    ok = False
    break
    
print((-1,day)[ok])

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
stack=[]

def addmatch(i):
  if len(a[i])==0:
    return
  j=a[i][-1]
  if a[j][-1]==i:
    stack.append([i,j])

for i in range(N):
  addmatch(i)

day=0
while stack:
  day+=1
  member=set()
  for i in range(len(stack)):
    g=stack.pop()
    y=g[0]
    x=g[1]
    if len(a[y])>0 and a[y][-1]==x:
      a[y].pop()
      a[x].pop()
      member.add(y)
      member.add(x)
  for m in member:
    addmatch(m)

for i in range(len(a)):
  if len(a[i])>0:
    print(-1)
    break
else:
  print(day)

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
cleared_num=0
new_search_index=set(range(1,N+1))
for answer in range(1,N**3):
  matched_set=set()
  unchanged=True

  search_index=new_search_index;
  new_search_index=set()
  for i in search_index:
    if i in matched_set:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not ai_next in matched_set:
      #print(i,ai_next,answer)
      matched_set.add(amat[i].pop())
      matched_set.add(amat[ai_next].pop())
      if len(amat[i])==0:
        cleared_num+=1
      else:
        new_search_index.add(i)  
      if len(amat[ai_next])==0:
        cleared_num+=1
      else:
        new_search_index.add(ai_next)
      unchanged=False
      
  if unchanged:
    print(-1)
    return
  elif cleared_num==N:
    print(answer)
    return

from collections import deque

n = int(input())
l = [[int(i)-1 for i in input().split()] for i in range(n)]
# 選手の番号をindexと一致させる

q = deque(list(range(n)))
days = [0 for i in range(n)]
pairs = [-1 for i in range(n)]
while q:
    a = q.popleft() #qの左端の選手のindexをpopleft
    if len(l[a]) == 0: #a番の選手のリクエストがない
        continue #skip
    b = l[a].pop(0)
    #l[a]:a番の選手のリクエストリスト
    #l[a]の最初のリクエストをpop

    #a:ある選手のindex
    #b:a番の選手が最初にリクエストした選手のindex
    if pairs[b] == a: # bのリクエストがaなら
        days[a] = days[b] = max(days[a],days[b]) +1
        q.append(a)
        q.append(b)
    else:
        pairs[a] = b #
print((max(days) if not any(l) else -1))



from collections import deque

n = int(input())
matches = []
for _ in range(n):
    matches.append(list([int(x)-1 for x in input().split()]))

q = deque(list(range(n)))

days = [0]*n  # 各選手の現在の日付

while q:
    x = q.popleft()  # 試合する人
    if len(matches[x]) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x][0]  # xの次の対戦相手
    if matches[y][0] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
        _ = matches[x].pop(0)
        _ = matches[y].pop(0)

if not any(matches):  # 全ての試合をしょうか
    print((max(days)))
else:
    print((-1))


import itertools
#0-indexed
N = int(input())
A = [[int(_) - 1 for _ in input().split()][::-1] for _ in range(N)]
ans = 0
cand = list(range(N))
left = 1
while True:
    cand_ = set()
    for i in cand:
        v = A[i]
        if not len(v):
            continue
        if A[v[-1]][-1] == i:
            f = 0
            cand_.add(i)
            cand_.add(v[-1])
    if not cand_:
        break
    cand = cand_
    left = 0
    for i in cand:
        A[i].pop()
        left |= len(A[i]) > 0
    ans += 1
if left:
    print((-1))
else:
    print(ans)


import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played = set()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

for i in A:
    if len(i) > 0:
        print(-1)
        return
else:
    print(days)

from collections import deque

def main():
    n = int(input())
    a = []
    for i in range(n):
        a.append(list(map(int, input().split())))

    que = deque()
    lastdone = []
    next = []
    for i in range(n):
        que.append((i, 1))
        lastdone.append(-1)
        next.append(0)
    while len(que) > 0:
        now, day = que.popleft()
        if lastdone[now] == day:
            continue
        if next[now] == n-1:
            continue
        candidate = a[now][next[now]]-1
        if lastdone[candidate] == day:
            continue
        if next[candidate] == n-1:
            continue
        if a[candidate][next[candidate]]-1 == now:
            next[now] += 1
            next[candidate] += 1
            lastdone[now] = day
            lastdone[candidate] = day
            que.append((now, day+1))
            que.append((candidate, day+1))

    for i in range(n):
        if next[i] != n-1:
            print((-1))
            return

    print((max(lastdone)))

def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
league = [0]*(n+1)
cnt = 0

while True:
  topop = []
  if cnt == 0:
    for i,player in enumerate(a):
      x = player[-1]
      if league[x] == i+1:
        topop.append(x)
        topop.append(i+1)
      else:
        league[i+1] = x
  else:
    for player in popped:
      if a[player-1] == []:
        continue
      x = a[player-1][-1]
      if league[x] == player:
        topop.append(x)
        topop.append(player)
      else:
        league[player] = x
  popped = []
  if topop == []:
    print((-1))
    return
  for t in topop:
    if a[t-1] == []:
      print((-1))
      return
    a[t-1].pop()
    popped.append(t)
  cnt += 1
  if not any(a[i] for i in range(n)):
    break
print(cnt)


from collections import deque, defaultdict

N = int(input())
A = [deque([int(a) - 1 for a in input().split()]) for _ in range(N)]

D = [0] * N
canBattle = defaultdict(lambda: False)
que = deque(list(range(N)))

while que:
    i = que.popleft()
    j = A[i].popleft()
    canBattle[(i, j)] = True

    if canBattle[(j, i)]:
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print((max(D)))
else:
    print((-1))


from collections import deque, defaultdict

N = int(input())
A = [deque([int(a) - 1 for a in input().split()]) for _ in range(N)]

D = [0] * N
Nx = [-1] * N
que = deque(list(range(N)))

while que:
    i = que.popleft()
    j = A[i].popleft()
    Nx[i] = j

    if Nx[j] == i:
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print((max(D)))
else:
    print((-1))


import sys, collections
input = sys.stdin.readline

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
    i2 = a[i - 1][0]
    if a[i2 - 1][0] == i:
        if i not in temp:
            queue.append([i, i2])
            temp.add(i)
            temp.add(i2)
if not queue:
    flag = False
while queue:
    temp = []
    while queue:
        test = queue.popleft()
        match += 1
        num1, num2 = test[0], test[1]
        nums[num1 - 1] += 1
        nums[num2 - 1] += 1
        temp.append(num1)
        temp.append(num2)
    flag2 = False
    temp2 = set()
    for i in temp:
        if nums[i - 1] <= n - 2:
            new_num = a[i - 1][nums[i - 1]]
            if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
                if i not in temp2:
                    queue.append([i, new_num])
                    flag2 = True
                    temp2.add(i)
                    temp2.add(new_num)
    if flag2 == False and match < n * (n - 1) // 2:
        flag = False
        break
    day += 1

if flag == True:
    print(day)
else:
    print(-1)

# 頂点数がN(N-1)/2, 辺がN(N-2)本できる
from collections import deque

N = int(input())
matches = [[a-1 for a in map(int, input().split())] for line in range(N)]
q = deque(range(N))
depth = [0]*N
waiting = [-1]*N

while q:
  a = q.popleft()
  b = matches[a].pop()
  if waiting[b] == a:
    depth[a] = depth[b] = max(depth[a], depth[b]) + 1
    if matches[a]:
      q.append(a)
    if matches[b]:
      q.append(b)
  else:
    waiting[a] = b
    
if any(matches):
  print(-1)
else:
  print(max(depth))

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list([int(x)-1 for x in input().split()])
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
import time

#A
def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return

#B
def B():
    a, b = LI()
    ans = 0
    b -= 1
    while b > 0:
        b -= a - 1
        ans += 1
    print(ans)

    return

#C
def C():
    n = II()
    h = LI()
    i = 0
    ans = 0
    while i < n:
        down = i+1
        while down < n:
            if h[down - 1] >= h[down]:
                down += 1
            else:
                break
        ans = max(ans, down - i - 1)
        i = down
    print(ans)
    return

#D
def D():
    n = II()
    print((n * (n - 1) // 2))
    return

#E
def E():
    start = time.time()
    n = II()
    a = LIR_(n)
    ans = 0
    tern = [0] * n
    while 1:
        ans += 1
        f = True
        c = defaultdict(int)
        for i in range(n):
            if c[i]:
                continue
            if tern[i] == n - 1:
                continue
            rival = a[i][tern[i]]
            if c[rival]:
                continue
            if tern[rival] == n - 1:
                continue
            if a[rival][tern[rival]] == i:
                c[i] += 1
                c[rival] += 1
                tern[rival] += 1
                tern[i] += 1
                f = False
        if time.time() - start >= 1:
            print((n * (n - 1) // 2))
            return
        if f:
            if tern == [n - 1] * n:
                print((ans-1))
                return
            else:
                print((-1))
                return
    return

#F
def F():
    return

#Solve
def __starting_point():
    E()

__starting_point()

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


def __starting_point():
    abc139_e()

__starting_point()

def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            cnt+=1
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            if i>=j:temp.append(d[(j-1,i)])
            else:temp.append(d[(i,j-1)])
        for j,k in enumerate(temp[1:]):
            g[temp[j]].append(k)
            gr[k]+=1
    q=[i for i,j in enumerate(gr) if j==0]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        for i in q:
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)
main()

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


def __starting_point():
    abc139_e()

__starting_point()

# 次に試合したい相手をdequeで管理
# お互いの試合したい相手(dequeの先頭)が一致すれば試合できる
# 次の日のチェック対象は「前日に試合した人」だけ。これをキュー管理

import sys
readline = sys.stdin.readline

N = int(readline())
ALL = (N * (N - 1)) // 2 # 試合数

from collections import deque
player = [None] * N
for i in range(N):
  player[i] = deque(list(map(lambda x:int(x) - 1,readline().split())))
  
# 明日試合する候補の人
q = set(range(N))

day = 0
while q:
  day += 1
  nextday = set()
  checked = set()
  for p in q:
    if p in checked:
      continue
    if len(player[p]) == 0:
      continue
    op = player[p][0] # 次の対戦相手
    if op in checked:
      continue
    if player[op][0] == p:
      # 試合成立
      player[p].popleft()
      player[op].popleft()
      checked.add(op)
      checked.add(p)
      if player[p]:
        nextday.add(p)
      if player[op]:
        nextday.add(op)
  q = nextday 

for p in player:
  if len(p) > 0:
    print(-1)
    break
else:
  print(day)

N = int(input())
A = [list([int(n)-1 for n in input().split()]) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print((-1))


def solve():
    N = int(input())
    Ass = [tuple([int(x)-1 for x in input().split()]) for _ in range(N)]

    day = 0
    numMatch = 0
    ps = set(range(N))
    isReadys = [0] * N
    iAs = [-1] * N
    while True:
        day += 1
        p2s = set()
        for p in ps:
            iAs[p] += 1
            if iAs[p] == N-1: continue
            q = Ass[p][iAs[p]]
            if isReadys[q] and Ass[q][iAs[q]] == p:
                isReadys[q] = 0
                p2s.add(p)
                p2s.add(q)
                numMatch += 1
            else:
                isReadys[p] = 1
        if numMatch >= N*(N-1)//2:
            print(day)
            break
        if not p2s:
            print((-1))
            break
        ps = p2s

solve()


import sys
import copy
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

match = 0
candidate = []
used = set()
for i in range(N):    
    bool = False
    if len(A[i]) == 0:
        continue
    op = A[i][0] - 1
    if op in used or i in used:
        continue
    if A[op][0]-1 == i:
        used.add(i)
        used.add(op)
        candidate.extend([i, op])
        match += 1
        bool = True
        A[i].popleft()
        A[op].popleft()
answer = 1

while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print((-1))
        return

print(answer)


from collections import deque
n = int(input())
a = [list(map(int, input().split())) + [0] for i in range(n)]
for i in range(n):
    for j in range(n):
        a[i][j] -= 1
l = [0] * n
d = [0] * n
Q = deque(range(n))
while Q:
    p = Q.popleft()
    q = a[p][l[p]]
    if a[q][l[q]] == p:
        m = max(d[p], d[q]) + 1
        d[p] = m
        d[q] = m
        l[p] += 1
        l[q] += 1
        Q.append(p)
        Q.append(q)
for i in l:
    if i != n - 1:
        print(-1);return()
print(max(d))

import sys
input = sys.stdin.readline

N = int(input())
A = [list([int(n)-1 for n in input().split()]) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print((-1))


import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = [deque for _ in range(N)]
    for i in range(N):
        A[i] = deque(list([int(x) - 1 for x in input().split()]))

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].popleft()
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print((-1))


def __starting_point():
    solve()

__starting_point()

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)

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    Id = {}
    
    cur = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            Id[(i,j)] = cur
            cur += 1
            
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: k = Id[(i, j)]
            else: k = Id[(j, i)]
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print(-1)
            return
    print(ans)
            
def __starting_point():
    main()
__starting_point()

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

N = int(input())
A = []
for _ in range(N):
    # 選手番号を0-indexにする
    line = list([int(x) - 1 for x in input().split()])
    A.append(line)

# cnt[i] = 選手iが現在までに何試合したか
cnt = [0] * N
# recent[i] = 選手iが最後に試合をした日
recent = [0] * N

# Qの初期値 = [0, 1, ..., N-1]
Q = deque(list(range(N)))

while Q:
    # ある選手(p1)について
    p1 = Q.popleft()
    # p1がまだ全試合(N-1試合)を終えていない場合
    # p2 = p1が次に当たるべき選手
    if cnt[p1] < N - 1:
        p2 = A[p1][cnt[p1]]
        # p2もまだ全試合を終えていない場合
        if cnt[p2] < N - 1:
            # p2が次に当たるべき選手がp1の場合 -> (p1,p2)の試合を行うことが可能
            if A[p2][cnt[p2]] == p1:
                # day = (p1,p2)の試合を行う日
                day = max(recent[p1], recent[p2]) + 1
                recent[p1] = day
                recent[p2] = day
                cnt[p1] += 1
                cnt[p2] += 1
                Q.append(p1)
                Q.append(p2)

if min(cnt) != N - 1:
    print((-1))
else:
    print((max(recent)))


from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [[int(s) - 1 for s in reversed(readline().split())] for _ in range(N)]

    M = N * (N - 1) // 2
    games = 0
    players = set(range(N))

    for d in range(1, M + 1):
        players, players_prev = set(), players
        for i in players_prev:
            if not A[i] or i in players:
                continue
            j = A[i][-1]
            if j not in players and i == A[j][-1]:
                players.add(i)
                players.add(j)
                A[i].pop()
                A[j].pop()
                games += 1

        if games == M:
            print(d)
            break

        if not players:
            print((-1))
            break

    return


def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print((-1))
        break
    else:
        r = ne


from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(list(map(int,input().split())))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print((-1))
            return
        if abs(time.time()-t)>1:
            print((n*(n-1)//2))
            return

    print(c)

def __starting_point():
    main()

__starting_point()

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]
candidate = list(range(N))
match = 0
day = 0

while True:
    day += 1
    used = set()
    next = set()
    bool = False
    for c in candidate:
        if len(A[c]) == 0:
            continue
        op = A[c][0] - 1
        if c in used or op in used:
            continue
        if A[op][0] - 1 == c:
            bool = True
            A[c].popleft()
            A[op].popleft()
            match += 1
            next |= {c, op}
            used |= {c, op}
    if match == N * (N-1) // 2:
        break
    if not bool:
        print((-1))
        return
    candidate = next

print(day)


def opp(i):  #対戦希望相手
    return a[i][nex[i]]

from sys import stdin
#入力
readline=stdin.readline
n=int(readline())
m=n*(n-1)//2
a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

nex=[0]*n
before=set(range(n))
day=0
for day in range(1,m+1):
    now=set()
    while len(before)>0:
        p=before.pop()
        q=opp(p)
        if opp(q)==p and p not in now and q not in now:
            nex[p]+=1
            nex[q]+=1
            if nex[p]<n-1:
                now.add(p)
            if nex[q]<n-1:
                now.add(q)
            if q in before:
                before.remove(q)
    before=now
    if len(before)==0:
        break

if min(nex)==n-1:
    print(day)
else:
    print(-1)

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = list([int(x) - 1 for x in input().split()])

    # print(A)

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].pop(0)
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print((-1))


def __starting_point():
    solve()

__starting_point()

import sys
import collections
from collections import defaultdict

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [[int(x) for x in input().split()] for _ in range(N)]

    q = [collections.deque() for j in range(N)]

    for i, a in enumerate(A):
        for aa in a:
            q[i].append(aa)

    ans = 0

    current = defaultdict(int)
    for i, v in enumerate(q):
        current[i + 1] = v[0]

    while True:
        v = set()
        for k in list(current.keys()):
            if k == q[current[k] - 1][0]:
                v.add(k)
                v.add(current[k])

        current = defaultdict(int)

        if len(v) == 0:
            break

        for vv in v:
            q[vv - 1].popleft()
            if len(q[vv - 1]):
                current[vv] = q[vv - 1][0]

        ans += 1

    # 全て空なら
    size = 0
    for i in range(N):
        size += len(q[i])

    if size == 0:
        print(ans)
    else:
        print((-1))


def __starting_point():
    main()

__starting_point()

import collections

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=[0]+[collections.deque(arr[i]) for i in range(n)]
ans=0
cand=set(range(1,n+1))
while 1:
  check=set()
  for i in cand:
    if not arr[i]:
      continue
    pair=arr[i][0]
    if arr[pair][0]==i:
      check.add(i)
      check.add(pair)
  if not check:
    break
  cand=set()
  for i in check:
    cand.add(i)
    arr[i].popleft()
    if arr[i]:
      cand.add(arr[i][0])
  ans+=1
for i in range(1,n+1):
  if arr[i]:
    print(-1)
    break
else:
  print(ans)

from collections import deque

N = int(input())
A = [deque([ a-1 for a in map(int, input().split())]) for _ in range (N)]
cnt = 0
cur = [-1 for _ in range(N+1)]
day = [0 for _ in range(N+1)]
que = deque( range(N) )

while que:
    x = que.popleft()
    if not A[x]:
        continue
    y = A[x].popleft()
    if cur[y] == x:
        cnt += 1
        day[x] = day[y] = max(day[x], day[y]) + 1
        cur[x] = cur[y] = -1
        que.append(x), que.append(y)
    else:
        cur[x] = y

flag = ( cnt == N*(N-1)/2 )
print( max(day) if flag else -1 )

from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions,time
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

st = time.time()
n = inp()
a = []
for i in range(n):
    b = inpl()
    a.append(deque(b))
zan = n*(n-1)//2
res = 0
while True:
    res += 1
    now = zan
    s = set()
    for i in range(n):
        if i in s or a[i] == deque([]): continue
        end = True
        chk = a[i][0] - 1
        if not chk in s and a[chk][0] == i+1:
            zan -= 1
            if not zan: 
                print(res); return
            a[i].popleft(); a[chk].popleft()
            s.add(i); s.add(chk)
        # print(res,i,chk,a)
        nnn = time.time()
    if now == zan:
        print((-1))
        return
    if nnn - st > 1.7:
        print((n*(n-1)//2))
        return

            


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] = cur_depth + 1
                queue.append(v), order.append(v)
    return (order, depths) if len(order) + first_index == V else (None, None)


def abc139_e():
    # https://atcoder.jp/contests/abc139/tasks/abc139_e
    N, *A = list(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 else -1))


def grl_4_a():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A
    V, _, *ST = list(map(int, open(0).read().split()))
    graph = [[] for _ in range(V)]
    in_degrees = [0] * V
    for s, t in zip(*[iter(ST)] * 2):
        graph[s].append(t)
        in_degrees[t] += 1

    res, _ = cycle_detectable_topological_sort(graph, in_degrees)
    print((1 if res is None else 0))


def __starting_point():
    abc139_e()
    # grl_4_a()

__starting_point()

# O(N)
def is_not_empty(A):
    for x in A:
        if x:
            return True
    return False

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # 当日の参加者
    today = set()
    # 初日
    for i in range(1,N+1):
        # 既に参加した人はダメ
        if i in today:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in today):
            today.add(ME)
            today.add(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    # 初日に誰も試合できなかったとき
    if not today:
        print(-1)
        return

    # 前日の参加者
    yesterday = today
    # 日数
    answer = 1
    while is_not_empty(A):
        today = set()
        # 前日に試合した人は必ず次の日に試合する
        for i in yesterday:
            if not A[i]:
                continue
            if i in today:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in today):
                today.add(ME)
                today.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not today:
            print(-1)
            return
        answer += 1
        yesterday = today

    print(answer)

def __starting_point():
    main()
__starting_point()

import sys

input = sys.stdin.readline

def main(): 
    N = int(input())
    
    Id = {}
    
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    cur = 0
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: a, b = i, j
            else: a, b = j, i
        
            if (a, b) not in Id:
                Id[(a, b)] = cur
                cur += 1
            k = Id[(a, b)]
        
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print((-1))
            return
    print(ans)           

def __starting_point():
    main()


__starting_point()

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print((-1))
    break
else:
  print(day)