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 _ 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

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


edge = [[] for _ in range(2*(10**6))]

used = [-1]*(2*(10**6))

for i in range(1,n+1):
    a = tuple(map(int,input().split()))
    fr = None
    for e in a:
        go = max(i,e) + min(i,e)*1000

        if fr != None:
            if used[fr] < 0:
                used[fr] = 0
            if used[go] < 0:
                used[go] = 0
            edge[fr].append(go)
            used[go] += 1
        fr = go


res = 0
ctr = 0
tank = []
new = []
for i,e in enumerate(used):
    if e == 0:
        new.append(i)
        ctr += 1

while len(new) > 0:
    tank = []
    for p in new:
        for e in edge[p]:
            used[e] -= 1
            if used[e] == 0:
                tank.append(e)
                ctr += 1
    new = tank
    res += 1

if ctr < n*(n-1)//2:
    print(-1)
else:
    print(res)

Solution (Python):
from copy import deepcopy
from heapq import heappop, heappush

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

d = [0] * n

ans = 0
temp = []
for x in range(n):
    heappush(temp, x)
while 1:
    next_temp = []
    while len(temp) > 0:
        x = heappop(temp)
        if d[x] >= n-1:
            continue
        y = a[x][d[x]]
        
        if y not in next_temp:
            if a[y][d[y]] == x:
                heappush(next_temp, x)
                heappush(next_temp, y)
    
    for t in next_temp:
        d[t] += 1
    if len(next_temp) == 0:
        break
    temp = [] + next_temp
    ans += 1



if d.count(n-1) == n:
    print(ans)
else:
    print(-1)

Solution (Python):
import collections


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
    ad = [0] * n
    q = collections.deque([[0, i] for i in range(n)])
    for i in range(10 ** 20):
        fq = collections.defaultdict(list)
        while True:
            if len(q) != 0:
                d, p = q.popleft()
                if d == i:
                    if p not in fq:
                        tp = a[p][ad[p]]
                        if tp not in fq:
                            if p == a[tp][ad[tp]]:
                                fq[tp]
                                fq[p]
                                ad[tp] += 1
                                ad[p] += 1
                                if ad[tp] < n - 1:
                                    q.append([d+1, tp])
                                if ad[p] < n - 1:
                                    q.append([d+1, p])
                else:
                    q.appendleft([d, p])
                    break
            else:
                if sum(ad) == n * (n - 1):
                    print(i + 1)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    slove()

Solution (Python):
from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


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

    node_id_db = [[0] * N for _ in range(N)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1] * (N * (N - 1) // 2)
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(1000000)
main()

Solution (Python):
from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


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

    node_id_db = [[0] * N for _ in range(N)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1 for _ in range(N * (N - 1) // 2)]
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(1000000)
main()

Solution (Python):
from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


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

    node_id_db = [[0] * (N+1) for _ in range(N + 1)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1 for _ in range(N * (N - 1) // 2)]
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(1000000)
main()

Solution (Python):
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

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

node_id_db = [[0] * (N+1) for _ in range(N + 1)]
v = 0
for i in range(N):
    for j in range(i + 1, N):
        node_id_db[i][j] = v
        v += 1


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
    Ai = A[i]
    from_id = get_node_id(i, Ai[0], node_id_db)
    if i < Ai[0]:
        start_nodes.append(from_id)
    for j in range(1, N - 1):
        to_id = get_node_id(i, Ai[j], node_id_db)
        edges[from_id].append(to_id)
        from_id = to_id

dp = [-1 for _ in range(N * (N - 1) // 2)]


def dfs(node_id, edges):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges)
        if t == 0:  
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


print(max(dfs(n, edges) for n in start_nodes))

Solution (Python):
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

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

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

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j]].append(a[i][j + 1])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()

Solution (Python):
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

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

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

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = [deque(LI()) for _ in range(n)]

match_set = set()
for i in range(n):
    opponent = L[i][0] - 1
    if i in match_set or opponent in match_set:
        continue
    elif L[opponent][0] - 1 == i:
        L[i].popleft()
        L[opponent].popleft()
        match_set.add(i)
        match_set.add(opponent)


pre_match_set = match_set


cnt = 1
while pre_match_set:
    match_set = set()
    flag = 0
    for j in pre_match_set:
        if not L[j]:
            continue
        opponent = L[j][0] - 1
        if not L[opponent]:
            continue
        if j in match_set or opponent in match_set:
            continue
        if L[opponent][0] - 1 == j:
            flag = 1
            L[j].popleft()
            L[opponent].popleft()
            match_set.add(j)
            match_set.add(opponent)
    if flag:
        cnt += 1
    pre_match_set = match_set



if any([i for i in L]):
    print(-1)
else:
    print(cnt)

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

edges = defaultdict(lambda: [])
used = [False for _ in range(1001000)]
d = [1 for _ in range(1001000)]


def dfs(i):
    if used[i]:
        return d[i]
    else:
        used[i] = True
        ret = 0
        for v in edges[i]:
            tmp = dfs(v)
            if ret < tmp+1:
                ret = tmp+1
        d[i] = ret
        return ret


def main():
    n = int(input())
    h = [0 for _ in range(1001000)]
    for i in range(n):
        a = list(map(int, input().split()))
        for j in range(1, n-1):
            pa = a[j-1]-1
            na = a[j]-1
            pi = i
            ni = i
            if na > ni:
                na, ni = ni, na
            if pa > pi:
                pa, pi = pi, pa
            edges[1000*pi + pa].append(1000*ni + na)
            h[1000*ni + na] += 1
    
    stack = []
    for k, _ in edges.items():
        if h[k] == 0:
            stack.append(k)
    
    ans = 0
    while len(stack):
        u = stack.pop()
        for v in edges[u]:
            h[v] -= 1
            if h[v] == 0:
                stack.append(v)
        ans += 1

    if ans != n*(n-1)//2:
        print(-1)
    else:
        ret = 0
        for k, _ in edges.items():
            tmp = dfs(k)
            if tmp > ret:
                ret = tmp
        print(ret+1)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

Solution (Python):
N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

Solution (Python):

import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	game.add((a,b))

day=0

while game:
	next_game=set()
	Visit=defaultdict(lambda: None) 

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp) and Visit[x] is None and Visit[y] is None:
			Visit[x]=1
			Visit[y]=1
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))

	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day

Solution (Python):
def solve():
    N = int(input())
    tournament = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]
    map_que_tournament = {i:[] for i in range(N)} 
    competition_num = -1
    que_player = list(range(N))
    
    while que_player:
        day_process_flag = False
        new_queue = []
        
        for player in que_player:
            if tournament[player]:
                match_player = tournament[player].pop(0)
                
                if map_que_tournament[match_player] and player == map_que_tournament[match_player][0]:
                    
                    day_process_flag = True
                    new_queue.append(match_player)
                    new_queue.append(player)
                    map_que_tournament[match_player].pop()
                else:
                    map_que_tournament[player].append(match_player)

        if day_process_flag:
            if competition_num < 0:
                competition_num = 1
            else: competition_num += 1

        que_player = new_queue
        
    
    for t in tournament:
        if t:
            competition_num = -1
            break

    print(competition_num)
    
solve()

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):

n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
  j = raw[i][cnt[i]]
  if i < j and i == raw[j][cnt[j]]:
    now.append(i)
    now.append(j)
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    cnt[x] += 1
    if cnt[x] < n-1:
      y = raw[x][cnt[x]]
      if x == raw[y][cnt[y]]:
        now.append(x)
        now.append(y)
  
if cnt == [n-1 for _ in range(n)]:
  print(ans)
else:
  print(-1)

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)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


if __name__ == '__main__':
    slove()

Solution (Python):
def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if n==1000 and x+1==n*(n-1)//2:
            print(x+1)
            exit()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Solution (Python):

n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
tmp = [0 for _ in range(n)]
now = [i for i in range(n)]
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    tmp[x] = 0
  for x in last:
    try:
      y = raw[x][cnt[x]]
      if tmp[x] == tmp[y] == 0 and x == raw[y][cnt[y]]:
        cnt[x] += 1
        cnt[y] += 1
        tmp[x] = 1
        tmp[y] = 1
        now.append(x)
        now.append(y)
    except:
      pass
  
if cnt == [n-1 for _ in range(n)]:
  print(ans-1)
else:
  print(-1)

Solution (Python):



n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
  j = raw[i][cnt[i]]
  if i < j and i == raw[j][cnt[j]]:
    now.append(i)
    now.append(j)
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    cnt[x] += 1
    if cnt[x] < n-1:
      y = raw[x][cnt[x]]
      if x == raw[y][cnt[y]]:
        now.append(x)
        now.append(y)
  
if cnt == [n-1 for _ in range(n)]:
  print(ans)
else:
  print(-1)

Solution (Python):

n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
  j = raw[i][cnt[i]]
  if i < j and i == raw[j][cnt[j]]:
    now.append(i)
    now.append(j)
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    cnt[x] += 1
    if cnt[x] < n-1:
      y = raw[x][cnt[x]]
      if x == raw[y][cnt[y]]:
        now.append(x)
        now.append(y)
  
if cnt == [n-1 for _ in range(n)]:
  print(ans)
else:
  print(-1)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
def combination_to_index(a,b,n):
    if(b<a):
        a,b = b,a
    return (2*n-a)*(a-1)//2+b-a

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    cnts = [0]*(M+1)
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            fr = combination_to_index(a,b,N)
            to = combination_to_index(a,A[ind+1],N)
            gp[fr].append(to)
            cnts[to] += 1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)
            cnts[ind]+=1

    ans = 0
    cnt = 0
    stk = deque()
    stk.append((0,0))
    while stk:
        n,ans = stk.popleft()
        for x in gp[n]:
            cnts[x]-=1
            if(cnts[x]==0):
                stk.append((x,ans+1))
                cnt += 1
    if(cnt!=M):
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [[x - 1 for x in list(map(int, input().split()))] for i in range(N)]

days = 0
cand = set(range(N))

while True:
    games = set() 
    
    for p in cand:
        if A[p] != []:
            if A[ A[p][0] ][0] == p:
                games.add(p)
                games.add(A[p][0])
    
    if not games: 
        if any(A): 
            print(-1) 
            break
        else: 
            print(days)
            break
    else: 
        for i in games:
            A[i].pop(0) 

    days += 1
    cand = games

Solution (Python):
N = int(input())
A = [[x - 1 for x in list(map(int, input().split()))] for i in range(N)]

days = 0
cand = set(range(N))

while True:
    games = set() 
    
    for p in cand:
        if A[p] != []:
            if A[ A[p][0] ][0] == p:
                games.add(p)
                games.add(A[p][0])
            
    
    
    if not games: 
        if any(A): 
            print(-1) 
            break
        else: 
            print(days)
            break
    else:
        for i in games:
            A[i].pop(0)

    days += 1
    cand = games

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def dfs(v, graph):
    if visited[v]:
        if not calculated[v]: 
            return -1 
        return depth[v]
    visited[v] = True
    for e in graph[v]: 
        res = dfs(e, graph) 
        if res == -1: 
            return -1 
        
        depth[v] = max(depth[v], res+1) 
    calculated[v] = True 
    return depth[v]


if __name__ == '__main__':
    N = int(input())
    Ng = N*(N-1)//2
    graph = [[] for _ in range(Ng)]
    G_id = [[-1]*N for _ in range(N)]
    
    game_id = 0
    first_game_id = []
    for i in range(N):
        row = list(map(int, input().split()))
        for d, r in enumerate(row):
            if G_id[i][r-1] == -1: 
                G_id[i][r-1] = game_id 
                G_id[r-1][i] = game_id
                
                if d != 0: 
                    graph[before].append(game_id)
                else:
                    first_game_id.append(game_id)
                    
                before = game_id 
                game_id += 1
            else: 
                if d != 0: 
                    graph[before].append(G_id[i][r-1])
                else:
                    first_game_id.append(G_id[i][r-1])
                before = G_id[i][r-1] 
    
    depth = [1]*Ng 
    visited = [False]*Ng
    calculated = [False]*Ng
    flag = True
    ans = 1
    for i in first_game_id:
        res = dfs(i, graph)
        if res == -1:
            flag = False
        else:
            ans = max(ans, res)
    if flag:
        print(ans)
    else:
        print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def dfs(v, graph):
    if visited[v]:
        if not calculated[v]: 
            return -1 
        return depth[v]
    visited[v] = True
    for e in graph[v]: 
        res = dfs(e, graph) 
        if res == -1: 
            return -1 
        
        depth[v] = max(depth[v], res+1) 
    calculated[v] = True 
    return depth[v]


if __name__ == '__main__':
    N = int(input())
    Ng = N*(N-1)//2
    graph = [[] for _ in range(Ng)]
    G_id = [[-1]*N for _ in range(N)]
    
    game_id = 0
    for i in range(N):
        row = list(map(int, input().split()))
        for d, r in enumerate(row):
            if G_id[i][r-1] == -1: 
                G_id[i][r-1] = game_id 
                G_id[r-1][i] = game_id
                
                if d != 0: 
                    graph[before].append(game_id)
                
                before = game_id 
                game_id += 1
            else: 
                if d != 0: 
                    graph[before].append(G_id[i][r-1])
                before = G_id[i][r-1] 
    
    depth = [1]*Ng 
    visited = [False]*Ng
    calculated = [False]*Ng
    flag = True
    ans = 1
    for i in range(Ng):
        res = dfs(i, graph)
        if res == -1:
            flag = False
        else:
            ans = max(ans, res)
    if flag:
        print(ans)
    else:
        print(-1)

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
import sys
from collections import*
from itertools import*
input=sys.stdin.readline
n=int(input())
d=defaultdict(count().__next__)
es=[]
for i in range(1,n+1):
    *a,=map(int,input().split())
    for j,k in zip(a,a[1:]):
        x,y=i,j
        if y<x:x,y=y,x
        v,w=i,k
        if w<v:v,w=w,v
        es+=(d[x*n+y],d[v*n+w]),
s=len(d)
outs=[[]for _ in range(s)]
ins=[0]*s
f=set(range(s))
for i,j in es:
    outs[i]+=j,
    f-={j}
    ins[j]+=1
q=deque(f)
l=0
data=[0]*s
m=0
while q:
    i=q.popleft()
    l+=1
    t=data[i]+1
    if t>m:m=t
    for j in outs[i]:
        if ins[j]>1:ins[j]-=1
        else:q+=j,
        if t>data[j]:data[j]=t
print(-(l<s)or m)
"""))

Solution (Python):
def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    l=0
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        l+=1
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(l<s)or m)
main()