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):
import sys
input = sys.stdin.readline

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

EDGEIN=[0]*(N*N)

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])
        EDGEIN[A[i][j]]+=1

from collections import deque
Q=deque()

for i in range((N-1)**2):
    if EDGEIN[i]==0 and len(E[i])>0:
        Q.append(i)

TOP=[]
while Q:
    x=Q.pop()
    TOP.append(x)
    for to in E[x]:
        EDGEIN[to]-=1
        if EDGEIN[to]==0:
            Q.append(to)


H=[1]*(N**2)
for x in TOP[::-1]:

    for fr in EREV[x]:
            
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1

if min(EDGEIN)<0 or max(EDGEIN)>0:
    print(-1)
else:
    print(max(H))

Solution (Python):
from collections import deque
N=int(input())
M=(N*(N-1))//2
D=dict()
tmp=0
X=[(0,0) for i in range(M)]
G=[[] for i in range(M)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i<j:
            D[(i,j)]=tmp
            X[tmp]=(i,j)
            tmp+=1
A=[[int(j) for j in input().split()] for i in range(N)]
for i in range(N):
    for j in range(N-2):
        p1=D[(i+1,A[i][j])] if i+1<A[i][j] else D[(A[i][j],i+1)]
        p2=D[(i+1,A[i][j+1])] if i+1<A[i][j+1] else D[(A[i][j+1],i+1)]
        G[p1].append(p2)
K=[0 for i in range(M)]
for i in range(M):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(M) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)


if len(res)<M:
    print(-1)
    exit()
ans=[0 for i in range(M)]
ans[res[-1]]=1
for i in res[:-1][::-1]:
    if len(G[i])==0:
        ans[i]=1
    else:
        for j in G[i]:
            ans[i]=max(ans[i],ans[j]+1)
print(max(ans))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def topological_sort(N: int, edges: list) -> list:
    """ トポロジカルソート(頂点数、辺集合(DAG, 0-indexed)) """

    
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(edges)):
        
        incnts[edges[i][1]] += 1
        
        outnodes[edges[i][0]].append(edges[i][1])
    
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)
            
            dist[i] = 1

    
    L = []
    
    while S:
        
        L.append(S.pop())
        
        for node in outnodes[L[-1]]:
            
            incnts[node] -= 1
            
            if incnts[node] == 0:
                S.add(node)
    
    if len(L) != N:
        return []
    
    return L

N = INT()


mapping = list2d(N, N, -1)
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        mapping[i][j] = cnt
        cnt += 1

A = []
for i in range(N):
    tmp = []
    for a in LIST():
        a -= 1
        a, b = min(a, i), max(a, i)
        
        tmp.append(mapping[a][b])
    A.append(tmp)


MAXV = N*(N-1)//2
edges = []
nodes = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(1, N-1):
        edges.append((A[i][j-1], A[i][j]))
        nodes[A[i][j-1]].append(A[i][j])


dist = [-1] * MAXV
res = topological_sort(MAXV, edges)
if not len(res):
    print(-1)
    exit()


for u in res:
    for v in nodes[u]:
        dist[v] = max(dist[v], dist[u]+1)

print(max(dist))

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

f = 0
def ts(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    def visit(j):
        global f
        checking[j] = 1
        if done[j] == 0:
            done[j] = 1
            for k in E[j]:
                if f: return 1
                if checking[k]:
                    f = 1
                    return 1
                visit(k)
                D[j] = max(D[j], D[k] + 1)
            L.append(j)
        checking[j] = 0
        return f
    for i in range(n):
        if visit(i):
            return []
    return L[::-1]

def ca(i, j):
    return max(i, j) * (max(i, j)-1) // 2 + min(i, j)

N = int(input())
M = N * (N-1) // 2
X = [[] for i in range(M)]
for i in range(N):
    A = [int(a)-1 for a in input().split()]
    for j in range(N-2):
        X[ca(i, A[j])].append(ca(i, A[j+1]))
D = [0] * M
L = ts(X)
print(max(D) + 1 if L else -1)

Solution (Python):
from collections import deque


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = deque()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.appendleft(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        for _ in range(len(today_states)):
            s = today_states.pop()
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    today_states.appendleft(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Solution (Python):
def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = set()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.add(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        nextday_states = set()
        for s in today_states:
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    nextday_states.add(ns)
        today_states = nextday_states
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

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

def main():
    n = int(input())

    def calc_idx(x, y):
        if x > y:
            x, y = y, x
        return x + y*(y-1)//2

    
    n_game = n * (n-1) // 2
    edge = [[] for i in range(n_game)]
    indegree = [0] * n_game
    for i in range(n):
        ai = list(map(int, input().split()))

        for j in range(1, n-1):
            g1 = calc_idx(i, ai[j-1]-1)
            g2 = calc_idx(i, ai[j]-1)
            edge[g1].append(g2)
            indegree[g2] += 1


    ans = 0
    cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
    n_ts = 0
    while len(cand) > 0:
        u, day = cand.popleft()
        ans = max(ans, day)
        n_ts += 1
        for v in edge[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand.append((v, day+1))

    if n_ts != n_game:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
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.appendleft(a)
        if matches[b]:
            q.appendleft(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))

Solution (Python):
from collections import deque

N = int(input())
A = [[a - 1 for a in map(int, input().split())] for _ in range(N)]
matchAvailablePlayers = deque(range(N))  
daysPassedWhenPlayedMostRecentMatch = [0] * N
opponentCandidateIdx = [-1] * N  


while matchAvailablePlayers:
    playerIdx = matchAvailablePlayers.popleft()
    matchesOrderForThisPlayer = A[playerIdx]  

    if not matchesOrderForThisPlayer:  
        continue

    finalOpponentIdx = matchesOrderForThisPlayer.pop()  

    if opponentCandidateIdx[finalOpponentIdx] == playerIdx:  
        daysPassedWhenPlayedMostRecentMatch[playerIdx] = daysPassedWhenPlayedMostRecentMatch[finalOpponentIdx] = max(daysPassedWhenPlayedMostRecentMatch[playerIdx], daysPassedWhenPlayedMostRecentMatch[finalOpponentIdx]) + 1  
        matchAvailablePlayers.append(playerIdx)  
        matchAvailablePlayers.append(finalOpponentIdx)
    else:  
        opponentCandidateIdx[playerIdx] = finalOpponentIdx

if any(A):  
    print(-1)
else:
    print(max(daysPassedWhenPlayedMostRecentMatch))

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] 
    opp = [0]*N 
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() 
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:

                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

if __name__ == '__main__':
    main()

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

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]
to = [0]*nedge
for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])
		to[a[i][j]]+=1

from collections import deque

dp=[1]*nedge
q=deque([])
cnt = 0
for i in range(nedge):
	if to[i]==0:
		q.append(i)
		cnt+=1

ans = 1
while(q):
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne],dp[e]+1)
		to[ne]-=1
		if to[ne]==0:
			q.append(ne)
			cnt+=1
	ans = max(ans,dp[e])

if cnt != nedge:
	print(-1)
else:
	print(ans)

Solution (Python):
from collections import deque
import time

zuru = time.time()
N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
match = 0
que = [0 for _ in range(N+1)]

for day in range(1, (N-1) * N // 2 + 1):
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    ans = -1
    break
  if match==(N-1) * N / 2:
    ans = day
    break
  if time.time()-zuru > 1.5:
    ans = N*(N-1)//2
    break
print(ans)

Solution (Python):
import sys

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

import collections

que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
    player = que.popleft()
    opponent = As[player][counters[player]] - 1
    if As[opponent][counters[opponent]] - 1 == player:
        days[player] = max(days[player], days[opponent]) + 1
        days[opponent] = days[player]
        counters[player] += 1
        counters[opponent] += 1
        que.append(player)
        que.append(opponent)
for c in counters:
    if c < N - 1:
        print(-1)
        break
else:
    print(max(days))

Solution (Python):


from collections import deque,defaultdict
from sys import stdin



def solve():
  
  N = int(input())
  An = [deque([i-1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]

  
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn.add(i)
          Qn.add(An[i][0])
        An[j].popleft()
        if len(An[j]) > 0:
          Qn.add(j)
          Qn.add(An[j][0])
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



print(solve())

Solution (Python):

from collections import deque


def main():
    N = int(input())
    A = [0] + list(deque(map(int, input().split())) for _ in range(N))
    cnt, cur, days = 0, [0] * (N + 1), [0] * (N + 1)
    q = deque(list(range(1, N + 1))) 
    while q:
        x = q.popleft()
        
        if not A[x]:  
            continue
        y = A[x].popleft()  
        if cur[y] == x:  
            cnt += 1 
            days[x] = days[y] = max(days[x], days[y]) + 1  
            cur[x], cur[y] = 0, 0  
            q.append(x), q.append(y) 
        else:  
            cur[x] = y
    flg = cnt == N * (N - 1) // 2  
    print(max(days) if flg else -1)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



N = I()
A = []
for _ in range(N):
    A.append(III())

S = []
for i in range(N):
    j = A[i][0]-1
    if i==A[j][0]-1:
        if i<j:
            S.append((i,j))

c = [0]*N
ans = 0
while S:
    q = []
    for i,j in S:
        c[i] += 1
        c[j] += 1
        if c[i] <= N-2:
            x = A[i][c[i]]-1
            if A[x][c[x]]-1==i:
                q.append((min(i,x), max(i,x)))
        if c[j] <= N-2:
            y = A[j][c[j]]-1
            if A[y][c[y]]-1==j:
                q.append((min(j,y), max(j,y)))
    S = q
    ans += 1

for i in range(N):
    if c[i] != N-1:
        print(-1)
        exit()

print(ans)

Solution (Python):
def check(player):
    if not a[player]:
        return
    opponent = a[player][-1]
    if not a[opponent]:
        return
    if a[opponent][-1] == player:
        tpl = (player, opponent)
        q.add((min(tpl), max(tpl)))


n = int(input())

a = []
for _ in range(n):
    t = list(map(lambda x: int(x) - 1, input().split()))
    t.reverse()
    a.append(t)

q = set()
for i in range(n):
    check(i)

day = 0
while q:
    day += 1
    prev_q = set()
    q, prev_q = prev_q, q
    for player, opponent in prev_q:
        a[player].pop()
        a[opponent].pop()
    for player, opponent in prev_q:
        check(player)
        check(opponent)

if any(a[player] for player in range(n)):
    print(-1)
    exit()

print(day)

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

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

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        schedule = set()
        for i in q :
            j = A[i][0]
            if i in schedule or j in schedule :
                continue
                
            if i == A[j][0] :
                schedule.add(i)
                schedule.add(j)
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print(solve())

Solution (Python):
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
from collections import defaultdict
d=defaultdict(int)
l=defaultdict(list)
for i in range(N):
    x,y=(i,A[i][0]-1) if i<A[i][0]-1 else (A[i][0]-1,i)
    d[(x,y)]+=1
    l[(x,y)].append(i)
p=[0]*N
r=0
cand=list(d.keys())
while len(d)>0:
    r+=1
    f=0
    diff=defaultdict(int)
    for k in cand:
        if d[k]==2:
            del d[k]
            for i in l[k]:
                p[i]+=1
                if p[i]>N-2:
                    continue
                x,y=(i,A[i][p[i]]-1) if i<A[i][p[i]]-1 else (A[i][p[i]]-1,i)
                diff[(x,y)]+=1
                l[(x,y)].append(i)
            f=1
    for x,y in diff.keys():
        d[(x,y)]+=diff[(x,y)]
    cand=diff.keys()
    if f==0:
        break
print(r if f>0 else -1)

Solution (Python):
MAXN = 1005
MAXV = (MAXN * (MAXN - 1)) // 2
to = [[] for _ in range(MAXV)]
ID = [[-1] * MAXN for _ in range(MAXN)]

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

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

def main():
    N = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

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

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()

Solution (Python):


import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

start = time.time()

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)

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

    games = []
    for i in range(N):
        for j in range(i+1, N):
            games.append(i*N+j)
    adjL = [[] for _ in range(N*N)]

    indegs = [0] * (N*N)
    for i, As in enumerate(Ass):
        for j in range(len(As)-1):
            p1, p2, p3, p4 = i, As[j], i, As[j+1]
            if p1 > p2:
                p1, p2 = p2, p1
            if p3 > p4:
                p3, p4 = p4, p3
            adjL[p1*N+p2].append(p3*N+p4)
            indegs[p3*N+p4] += 1

    gameTodays = set()
    for game in games:
        if indegs[game] == 0:
            gameTodays.add(game)

    ans = 0
    numDone = 0
    while gameTodays:
        gameTomorrows = set()
        for game in gameTodays:
            numDone += 1
            for game2 in adjL[game]:
                indegs[game2] -= 1
                if indegs[game2] == 0:
                    gameTomorrows.add(game2)
        ans += 1
        gameTodays = gameTomorrows

    if numDone == N*(N-1)//2:
        print(ans)
    else:
        print(-1)

solve()

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

    games = []
    for i in range(N):
        for j in range(i+1, N):
            games.append(i*N+j)
    adjL = [[] for _ in range(N*N)]

    indegs = [0] * (N*N)
    for i, As in enumerate(Ass):
        for j in range(len(As)-1):
            p1, p2, p3, p4 = i, As[j], i, As[j+1]
            if p1 > p2:
                p1, p2 = p2, p1
            if p3 > p4:
                p3, p4 = p4, p3
            adjL[p1*N+p2].append(p3*N+p4)
            indegs[p3*N+p4] += 1

    gameTodays = set()
    for game in games:
        if indegs[game] == 0:
            gameTodays.add(game)

    ans = 0
    numDone = 0
    while gameTodays:
        gameTomorrows = set()
        for game in gameTodays:
            numDone += 1
            for game2 in adjL[game]:
                indegs[game2] -= 1
                if indegs[game2] == 0:
                    gameTomorrows.add(game2)
        ans += 1
        gameTodays = gameTomorrows

    if numDone == N*(N-1)//2:
        print(ans)
    else:
        print(-1)

solve()