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

Solution (Python):
n = int(input())

graph = {i+1000*j:[] for i in range(n) for j in range(i+1,n)}

st = {i+1000*j:0 for i in range(n) for j in range(i+1,n)}



szero = []


ans = []

for i in range(n):
    ls = list(map(int,input().split()))
    f = -1
    for p in ls:
        v = min(i,p-1) + 1000*(max(i,p-1))
        if f != -1:
            graph[f].append(v)
            st[v] += 1
        f = v

for v in st.keys():
    if st[v] == 0:szero.append(v)
count = 0
next_szero = []
while True:
    count += 1
    for i in szero:
        ans.append(i)
        for v in graph[i]:
            st[v] -= 1
            if st[v] == 0:
                next_szero.append(v)
    if len(next_szero) == 0:break
    szero = next_szero
    next_szero = []

if len(ans) != n*(n-1)//2:
    print(-1)
else:
    print(count)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1





S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        
        if IN[x] == 0:
            S.append(x)
    s += 1



if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))

Solution (Python):
def resolve():
    N = int(input())
    A = [list(map(lambda x:int(x)-1,input().split())) for _ in range(N)]
    cur = [0 for _ in range(N)]
    yesterday = set(range(N))
    rest = N * (N-1)
    day = 0
    while len(yesterday) > 0 and rest > 0:
        today = set()
        totoday = set()
        for y in yesterday:
            o = A[y][cur[y]]
            if A[o][cur[o]] == y:
                today.add(o)
                today.add(y)
        for t in today:
            cur[t] += 1
            if cur[t] < N-1:
                totoday.add(t)
        rest -= len(today)
        yesterday = totoday
        day += 1
    if rest == 0:
        print(day)
    else:
        print(-1)
resolve()

Solution (Python):
n = int(input())
xss = [[int(x)-1 for x in input().split()] for _ in range(n)]

def solve(n, xss):
    yss = [[-1] + list(reversed(xs)) for xs in xss]
    ans = 0
    candidates = range(n)
    while True:
        
        ms = list(matches(yss, candidates))
        if len(ms) == 0:
            if all(len(ys)==1 for ys in yss):
                return ans
            else:
                return -1
        ans += 1
        candidates = []
        
        for x, y in ms:
            yss[x].pop()
            yss[y].pop()
            candidates.append(x)
            candidates.append(y)

def matches(yss, candidates):
    firsts = [yss[i][-1] for i in candidates]
    ans = set()
    for x, y in zip(candidates, firsts):
        if y!=-1 and yss[y][-1] ==x:
            ans.add((min(x, y), max(x, y)))
    return ans

print(solve(n, xss))

Solution (Python):

import sys
input=sys.stdin.readline

n=int(input())
a=[list(reversed(list(map(lambda x:int(x)-1, input().split())))) for _ in range(n)]
b={i:r for i,r in enumerate(a)}

end=0
for k in range(8000):
    used=set()
    dels=[]
    for i,q in b.items():
        if not q:
            continue
        if i in used:
            continue
        j=q[-1]
        if j in used:
            continue
        if a[j][-1]==i:
            a[j].pop()
            a[i].pop()
            used.add(i)
            used.add(j)
            if not a[i]:
                end+=1
                dels.append(i)
            if not a[j]:
                end+=1
                dels.append(j)
    if not used:
        print(-1)
        exit()
    if end==n:
        print(k+1)
        exit()
    for i in dels:
        del b[i]

print(n*(n-1)//2)

Solution (Python):
import itertools

N = int(input())
A = [[int(_) - 1 for _ in input().split()][::-1] for _ in range(N)]
ans = 0
cand = 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)

Solution (Python):
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue








def main():
    n = map(int, raw_input().split())[0]
    da = [map(int, raw_input().split()) for i in range(n)]
    need = [0 for i in range(n+2)]
    t = [0 for i in range(n+2)]
    idx = [0 for i in range(n+2)]
    l = n*(n-1)/2
    ans = 0
    q = deque()
    for i in range(1, n+1):
        da[i-1].append(n+1)
        need[i] = da[i-1][idx[i]]
        if i == need[need[i]]:
            q.append(i);
    
    while q:
        
        fr = q.popleft()
        x, y = fr, need[fr]
        
        
        if not (x == need[y] and y == need[x]):
            continue
        ti = max(t[x], t[y]) + 1
        t[x] = t[y] = ti
        ans = max(ans, ti)
        l-=1
        idx[x] += 1
        idx[y] += 1
        need[x] = da[x-1][idx[x]]
        need[y] = da[y-1][idx[y]]
        if x == need[need[x]]:
            q.append(x)
        if y == need[need[y]]:
            q.append(y)
    
    if l==0:
        print ans
    else:
        print -1






main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline

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

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    
    A=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
    for i in range(n): A[i].reverse()
    stack=[]

    def check(i):
        if(not A[i]): return
        j=A[i][-1]
        if(A[j][-1]==i):
            stack.append((min(i,j),max(i,j)))

    
    for i in range(n): check(i)
    day=0
    while(stack):
        day+=1
        stack=list(set(stack)) 
        prev,stack=stack,[]
        for i,j in prev:
            A[i].pop(); A[j].pop()
        for i,j in prev:
            check(i); check(j)
    print(-1 if(any(A[i] for i in range(n))) else day)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    
    
    dp=[-1]*V
    def dfs(v):
        if(dp[v]>=0): return
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    
    for i in range(V): dfs(i)
    print(max(dp)+1)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    
    
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
import time
t=time.time()


def main():
    N = int(input().strip())
    A = [[0]] * (N+1)
    for idx in range(1, N+1):
        A[idx] = list(reversed([int(x) for x in input().strip().split()]))

    ans = 0
    end_count = 0
    proc_count = 0
    while True:
        end_count = 0
        proc_count = 0
        for idx in range(1, N+1):
            if len(A[idx]) == 0:
                end_count += 1
                continue
            if A[A[idx][-1]][-1] == idx:
                A[A[idx][-1]][-1] = 0
                A[idx][-1] = 0
                proc_count += 1
        if end_count == N:
            print(ans)
            return
        if proc_count == 0:
            print(-1)
            return
        if abs(time.time()-t)>1:
            print(N*(N-1)//2)
            return
        for idx in range(1, N+1):
            if len(A[idx]) != 0:
                if A[idx][-1] == 0:
                    A[idx].pop()
        ans += 1


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    graph = [[[] for _ in range(N)] for _ in range(N)]
    path = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        A = list(map(int, input().split()))
        for n in range(1, N-1):
            a, b = min(i, A[n]-1), max(i, A[n]-1)
            c, d = min(i, A[n-1]-1), max(i, A[n-1]-1)
            graph[c][d].append((a, b))
            path[a][b] += 1

    q = []
    for i in range(N-1):
        for j in range(i+1, N):
            if path[i][j] == 0:
                q.append((i, j))

    checked = [[False for _ in range(N)] for _ in range(N)]
    for i, j in q:
        checked[i][j] = True

    c = 0
    while q:
        c += 1
        qq = []
        for x, y in q:
            for nx, ny in graph[x][y]:
                path[nx][ny] -= 1
                if path[nx][ny] == 0:
                    checked[nx][ny] = True
                    qq.append((nx, ny))
        q = qq

    ok = True
    for i in range(N-1):
        for j in range(i+1, N):
            if not checked[i][j]:
                ok = False


    if not ok:
        print(-1)
    else:
        print(c)


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    

B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            
            
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print(-1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N = int(readline())
m = map(int,read().split())
A = [None] + list(map(deque,zip(*[m]*(N-1))))

day = 0
rest = N*(N-1)
cand = set(range(1,N+1))
while rest:
    day += 1
    match_player = set()
    for i in cand:
        if not A[i]:
            continue
        if A[A[i][0]][0] == i:
            match_player.add(i)
            match_player.add(A[i][0])
    if not match_player:
        break
    rest -= len(match_player)
    cand.clear()
    for i in match_player:
        cand.add(i)
        A[i].popleft()
        if A[i]:
            cand.add(A[i][0])

answer = day if rest == 0 else -1
print(answer)

Solution (Python):
N = int(input())
aaa = []
for i in range(N):
  aaa.append(list(reversed(list(map(int, input().split())))))

cs = set(range(N))
for i in range(0, N*N+1):
  empty = True
  played = False
  ncs = set()
  for j in cs:
    aa = aaa[j]
    if len(aa) > 0:
      empty = False
      l = aa[-1]-1
      if j not in ncs and l not in ncs and len(aaa[l]) > 0 and aaa[l][-1] == j+1:
          aa.pop()
          aaa[l].pop()
          played = True
          ncs.add(j)
          ncs.add(l)
  cs = ncs
  if empty:
    print(i)
    break
  elif not played:
    print(-1)
    break

Solution (Python):

import sys
from collections import defaultdict,deque

N=input()
M=[[None]]

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	M.append(A)

position=[0]*(N+1)

ans=0
goal_cnt=0
day=0
q=deque()

game=set()
for me in range(1,N+1):
	p=position[me]
	opp=M[me][p]	
	if me>opp: me,opp=opp,me
	game.add((me,opp))


while game:
	Visit=defaultdict(lambda: None) 
	next_game=set()
	for me,opp in game:
		opp_of_me=M[me][position[me]]
		opp_of_opp=M[opp][position[opp]]
		if me==opp_of_opp and opp==opp_of_me and Visit[me] is None and Visit[opp] is None:
			Visit[me]=1
			Visit[opp]=1
			position[me]+=1
			position[opp]+=1
			try:
				next_opp_of_me=M[me][position[me]]
				if me>next_opp_of_me: me,next_opp_of_me=next_opp_of_me,me
				next_game.add((me,next_opp_of_me))
			except:
				goal_cnt+=1
			try:
				next_opp_of_opp=M[opp][position[opp]]
				if opp>next_opp_of_opp: opp,next_opp_of_opp=next_opp_of_opp,opp
				next_game.add((opp,next_opp_of_opp))
			except:
				goal_cnt+=1
	day+=1
	game=next_game

if goal_cnt!=N:
	print -1
else:
	print day

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import defaultdict, deque

edges = defaultdict(lambda: [])
used = set()
d = defaultdict(lambda: 0)


def dfs(i):
    if i in used:
        return d[i]
    used.add(i)
    ret = -1
    for v in edges[i]:
        tmp = dfs(v)
        ret = max(ret, tmp)
    d[i] = ret + 1
    return ret+1

def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    h = {}
    for i, al in enumerate(a):
        for pa, ta in zip(al, al[1:]):
            pa, ta = pa-1, ta-1
            edges[1000*min(i, pa)+max(i, pa)].append(1000*min(i, ta)+max(i, ta))
            if 1000*min(i, pa)+max(i, pa) not in h:
                h[1000*min(i, pa)+max(i, pa)] = 0
            if 1000*min(i, ta)+max(i, ta) not in h:
                h[1000*min(i, ta)+max(i, ta)] = 1
            else:
                h[1000*min(i, ta)+max(i, ta)] += 1
    
    deq = deque([])
    for k, v in h.items():
        if v == 0:
            deq.append(k)
    
    ans = 0
    while deq:
        u = deq.popleft()
        for v in edges[u]:
            h[v] -= 1
            if h[v] == 0:
                deq.append(v)
        ans += 1
    
    if ans != n*(n-1) // 2:
        print(-1)
    else:
        length = 0
        for k, _ in edges.items():
            tmp = dfs(k)
            length = max(length, tmp)
        print(length + 1)


if __name__ == '__main__':
    main()

Solution (Python):
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    pt = [0] * n
    q = [[0, i] for i in range(n)]
    q = collections.deque(q)
    now = 0
    fq = collections.defaultdict(int)
    md = 0
    while True:
        if len(q) != 0:
            d, p = q.popleft()
            if d == now:
                o = a[p][pt[p]]
                r = a[o][pt[o]]
                if p == r and p not in fq and o not in fq:
                    fq[p]
                    fq[o]
                    md = max(md, d)
                    if len(a[p]) > pt[p] + 1:
                        pt[p] += 1
                        q.append([d + 1, p])
                    if len(a[o]) > pt[o] + 1:
                        pt[o] += 1
                        q.append([d + 1, o])
            else:
                q.append([d, p])
                fq = collections.defaultdict(int)
                now += 1
        else:
            break
    print(md + 1 if sum(pt) == (n - 2) * n else -1)


if __name__ == '__main__':
    slove()

Solution (Python):
from collections import* 
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(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)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A_array = [list(map(int, input().split())) for _ in range(N)]



s_index = [0] * N

ans_date = 1
finish_player = 0
match_count = 0
M = N * (N-1) // 2
first_flag = 1
while(1):
    flag = 0
    match_array = [0] * N
    if first_flag:
        match_candidate = [i for i in range(N)]
        first_flag = 0
    next_match = []
    for i in match_candidate:
        if match_array[i] == 1 or s_index[i] == N - 1:
            continue
        vs = A_array[i][s_index[i]] - 1
        
        if match_array[vs] != 1 and A_array[vs][s_index[vs]] - 1 == i:
            match_count += 1
            match_array[i] = 1
            s_index[i] += 1
            match_array[vs] = 1
            s_index[vs] += 1
            flag = 1
            next_match.append(i)
            next_match.append(vs)
    if flag == 0:
        print(-1)
        exit()
    if match_count == M:
        break
    ans_date += 1
    match_candidate = next_match
print(ans_date)

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

Solution (Python):
from collections import deque

n = int(input())
l = [[int(i)-1 for i in input().split()] for i in range(n)]


q = deque(range(n))
days = [0 for i in range(n)]
pairs = [-1 for i in range(n)]
while q:
    a = q.popleft() 
    if len(l[a]) == 0: 
        continue 
    b = l[a].pop(0)
    
    

    
    
    if pairs[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)

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


if pool:
    print(-1)
else:
    print(day)

Solution (Python):
N = int(input())


G = [[] for i in range(10 ** 6 + 1)]  
U = [None] * (10 ** 6 + 1)  
D = [0] * (10 ** 6 + 1)  



def x(i, j):
    return j + 1000 * i



for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].append(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0



for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1


U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)



if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()



for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)

Solution (Python):
N = int(input())


G = [None] * (10 ** 6 + 1)  
for i in range(10 ** 6 + 1):
    G[i] = set()
U = [None] * (10 ** 6 + 1)  
D = [0] * (10 ** 6 + 1)  



def x(i, j):
    return j + 1000 * i



for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].add(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0



for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

        

U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)



if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()



for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)

Solution (Python):

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(map(lambda x: int(x)-1, 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


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


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

    return


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


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


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


def F():
    return


if __name__ == '__main__':
    E()

Solution (Python):

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(map(lambda x: int(x)-1, 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


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


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

    return


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


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


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


def F():
    return


if __name__ == '__main__':
    E()