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):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = []
    for i in range(N):
        A.append(deque(map(lambda x: int(x)-1, input().split())))
    
    dbg('hoge')
    ans = 0
    players = deque(range(N))
    calc = 0
    
    match = defaultdict(lambda : -1)
    first = True
    while True:
        mathced = False
        next_players = deque()
        next_match = defaultdict(lambda : -1)
        
        for i in players:
            
            calc += 1
            a = A[i]
            if len(a) == 0:
                continue
            j = a[0]
            b = A[j]

            
            
            if match[j] == i and match[i] == j:
                
                b.popleft()
                
                
                a.popleft()
                mathced = True
                match[i] = -1
                match[j] = -1
                if len(a) > 0:
                    next_match[i] = a[0]
                    next_players.append(i)

                if len(b) > 0:
                    next_match[j] = b[0]
                    next_players.append(j)


            else:
                next_match[i] = a[0]

        players = next_players
        match.update(next_match)
        if first:
            dbg('hogehoge')
            first = False
            players = range(N)
            continue
        ans += 1
        if not mathced or len(players) == 0:
            break

        
    print(ans if mathced and len(next_players)==0 else -1)
    dbg(calc,mathced,len(next_players),len(a),len(b))







    

    ans = 0

    

    
   
main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print(-1)

Solution (Python):
from collections import deque

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

graph = [[] for _ in range(N * N)]
parents = [0] * (N * N)
for i, nodes in enumerate(X):
    for j1, j2 in zip(nodes[:-1], nodes[1:]):
        n1 = max(i, j1 - 1) * N + min(i, j1 - 1)
        n2 = max(i, j2 - 1) * N + min(i, j2 - 1)
        graph[n1].append(n2)
        parents[n2] += 1

dist = [0] * (N * N)
visited = [False] * (N * N)

q = deque()
for i, v in enumerate(parents):
    if v == 0:
        q.append(i)
        visited[i] = True
        dist[i] = 1

while q:
    u = q.popleft()
    for v in graph[u]:
        if visited[v]:
            continue

        parents[v] -= 1
        if parents[v] == 0:
            visited[v] = True
            dist[v] = dist[u] + 1
            q.append(v)

print(max(dist) if all(visited) else -1)

Solution (Python):

from collections import deque

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

graph = [[] for _ in range(N * N)]
inserted = [0] * (N * N)
for i, nodes in enumerate(X):
    for j1, j2 in zip(nodes[:-1], nodes[1:]):
        n1 = max(i, j1 - 1) * N + min(i, j1 - 1)
        n2 = max(i, j2 - 1) * N + min(i, j2 - 1)
        graph[n1].append(n2)
        inserted[n2] += 1

dist = [0] * (N * N)
visited = [False] * (N * N)
for i in range(N):
    visited[i * N + i] = True

q = deque()
for i, v in enumerate(inserted):
    if v == 0:
        q.append(i)
        visited[i] = True
        dist[i] = 1

while q:
    u = q.popleft()
    for v in graph[u]:
        if visited[v]:
            continue

        inserted[v] -= 1
        if inserted[v] == 0:
            visited[v] = True
            dist[v] = dist[u] + 1
            q.append(v)

print(max(dist) if all(visited) else -1)

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

N = int(input().strip())
M = N*(N-1)//2

graph = [[] for i in range(M)]
in_cnt = [0 for i in range(M)]
for x in range(1,N+1):
  l = list(map(int,input().split()))
  y = l[0]
  b,s = max(x,y),min(x,y)
  prev = (b-1)*(b-2)//2+s-1
  for y in l[1:]:
    b,s = max(x,y),min(x,y)
    now = (b-1)*(b-2)//2+s-1
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = [1 for k in range(M)]
q = [i for i in range(M) if not in_cnt[i]]

if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in range(M) if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

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



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


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





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

    nxt = [-1] * n
    waiting = collections.deque(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))


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = [LIST() for _ in range(N)]

match = defaultdict(int)
cnt = 0
for i, j in combinations(range(N), 2):
	match[(i, j)] = cnt
	match[(j, i)] = cnt
	cnt += 1

V = N*(N-1)//2
graph = [[] for _ in range(V)]
dag = [0]*V
for i in range(N):
	for j in range(N-2):
		graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
		dag[match[(i, A[i][j+1]-1)]] += 1

q = deque([i for i in range(V) if dag[i]==0])
day = [1]*V
ans = 1

while q:
	p = q.popleft()
	for v in graph[p]:
		dag[v] -= 1
		if dag[v] == 0:
			day[v] = day[p]+1
			ans = day[v]
			q.append(v)


if any(dag):
	print(-1)
else:
	print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	match = defaultdict(int)
	cnt = 0
	for i, j in combinations(range(N), 2):
		match[(i, j)] = cnt
		match[(j, i)] = cnt
		cnt += 1

	V = N*(N-1)//2
	graph = [[] for _ in range(V)]
	dag = [0]*V

	for i in range(N):
		for j in range(N-2):
			graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
			dag[match[(i, A[i][j+1]-1)]] += 1

	q = deque([i for i in range(V) if dag[i] == 0])
	day = [1]*V
	while q:
		p = q.popleft()
		for v in graph[p]:
			dag[v] -= 1
			if dag[v] == 0:
				day[v] = day[p]+1
				q.append(v)
				ans = day[v]

	if any(dag):
		print(-1)
	else:
		print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	match = defaultdict(int)
	cnt = 0
	for i, j in combinations(range(N), 2):
		match[(i, j)] = cnt
		match[(j, i)] = cnt
		cnt += 1

	V = N*(N-1)//2
	graph = [[] for _ in range(V)]
	dag = [0]*V

	for i in range(N):
		for j in range(N-2):
			graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
			dag[match[(i, A[i][j+1]-1)]] += 1

	q = deque([i for i in range(V) if dag[i] == 0])
	day = [1]*V
	while q:
		p = q.popleft()
		for v in graph[p]:
			dag[v] -= 1
			if dag[v] == 0:
				day[v] = day[p]+1
				q.append(v)

	if any(dag):
		print(-1)
	else:
		print(max(day))

if __name__ == '__main__':
	main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = [LIST() for _ in range(N)]

match = defaultdict(int)
cnt = 0
for i, j in combinations(range(N), 2):
	match[(i, j)] = cnt
	match[(j, i)] = cnt
	cnt += 1

V = N*(N-1)//2
graph = [[] for _ in range(V)]
dag = [0]*V

for i in range(N):
	for j in range(N-2):
		graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
		dag[match[(i, A[i][j+1]-1)]] += 1

q = deque([i for i in range(V) if dag[i] == 0])
day = [1]*V
while q:
	p = q.popleft()
	for v in graph[p]:
		dag[v] -= 1
		if dag[v] == 0:
			day[v] = day[p]+1
			q.append(v)
			
if any(dag):
	print(-1)
else:
	print(max(day))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = [LIST() for _ in range(N)]

match_id = [[0]*N for _ in range(N)]

def toid(i, j):
	i, j = sorted([i, j])
	return match_id[i][j]

cnt = 0
for i in range(N):
	for j in range(N):
		if i < j:
			match_id[i][j] = cnt
			cnt += 1

V = N*(N-1)//2

gout = [[] for _ in range(V)]
deg = [0]*V
for i in range(N):
	for j in range(N-2):
		gout[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))
		deg[toid(i, A[i][j+1]-1)] += 1

topo = [v for v in range(V) if deg[v] == 0 ]
day = [0]*V
deq = deque(topo)
ans = 0
while deq:
	v = deq.popleft()
	for t in gout[v]:
		deg[t] -= 1
		if deg[t] == 0:
			deq.append(t)
			day[t] = day[v] + 1
			ans = day[t]
if any(deg):
	print(-1)
	exit()
print(ans+1)

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

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

Solution (Python):
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]

def c(x,y):
    if y < x:
        x,y = y,x
    return x*n+y

e = [[] for i in range(n**2)]
count = [0]*(n**2)
for i in range(n):
    for j in range(n-2):
        y = c(i,a[i][j]-1)
        z = c(i,a[i][j+1]-1)
        count[z] += 1
        e[y].append(z)

q = []

for i in range(n-1):
    for j in range(i+1,n):
        x = c(i,j)
        if count[x] == 0:
            q.append(x)
ans = 0

while q:
    
    ans += 1
    old = q
    q = []
    for nowq in old:
        for nex in e[nowq]:
            count[nex] -= 1
            
            if count[nex] == 0:
                q.append(nex)
if sum(count) > 0:
    print(-1)
else:    
    print(ans)

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

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    
    res = []
    
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            
            cnt_in[next_v] -= 1
            
            if cnt_in[next_v] == 0:
                q.append(next_v)
    
    if len(G) != len(res):
        print(-1)
        exit()
    return res

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


used = [0] * n**2











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

print(max(used))

Solution (Python):
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  
    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():
    
    N, *A = map(int, open(0).read().split())

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

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

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


def grl_4_a():
    
    V, _, *ST = 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)


if __name__ == "__main__":
    abc139_e()

Solution (Python):
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  
    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():
    
    N, *A = map(int, open(0).read().split())

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

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

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


def grl_4_a():
    
    V, _, *ST = 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)


if __name__ == "__main__":
    abc139_e()

Solution (Python):
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  
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

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


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

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

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

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


if __name__ == "__main__":
    abc139_e()

Solution (Python):
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  
    for i in range(first_index, V):
        if not in_degrees[i]:
            queue.append(i)
            depths[i] = 0

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

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


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

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

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

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


if __name__ == "__main__":
    abc139_e()

Solution (Python):
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  
    for i in range(first_index, V):
        if not in_degrees[i]:
            queue.append(i)
            depths[i] = 0

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

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


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

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

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

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


if __name__ == "__main__":
    abc139_e()

Solution (Python):
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  
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

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


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

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

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

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


if __name__ == "__main__":
    abc139_e()

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