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):
from collections import deque

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

q = deque(range(N))
d = [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].popleft()

    if pairs[b] == a:  
        d[a] = d[b] = max(d[a], d[b]) + 1
        q.append(a)
        q.append(b)
    else:
        pairs[a] = b
print(max(d) if not any(L) else -1)

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

    
    N=0
    id=[[None]*n for _ in range(n)]
    from itertools import product
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        id[i][j]=N
        N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(n-2):
            u=toID(i,A[j])
            v=toID(i,A[j+1])
            E[u].append(v)

    
    dp=[-1]*N
    def dfs(v):
        if(dp[v]>=0): return dp[v]
        dp[v]=-2
        res=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            elif(dp[nv]==-1):
                res=max(res,dfs(nv)+1)
            else:
                res=max(res,dp[nv]+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

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

    
    N=0
    id=[[None]*n for _ in range(n)]
    from itertools import product
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        id[i][j]=N
        N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(n-2):
            u=toID(i,A[j])
            v=toID(i,A[j+1])
            E[u].append(v)

    
    dp=[-1]*N
    def dfs(v):
        if(dp[v]>=0): return dp[v]
        dp[v]=-2
        res=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

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

    
    N=0
    id=[[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            id[i][j]=N
            N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(n-2):
            u=toID(i,A[j])
            v=toID(i,A[j+1])
            E[u].append(v)

    
    dp=[-1]*N
    def dfs(v):
        if(dp[v]>=0): return dp[v]
        dp[v]=-2
        res=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

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())
    N=0
    id=[[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            id[i][j]=N
            N+=1
    to_id=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=tuple(map(int,input().split()))
        for j in range(n-2):
            u=to_id(i,A[j]-1)
            v=to_id(i,A[j+1]-1)
            E[u].append(v)

    
    dp=[None]*N

    def dfs(v):
        if(dp[v] is not None): return dp[v]
        dp[v]=-1
        res=0
        for nv in E[v]:
            if(dp[nv]==-1):
                print(-1)
                exit(0)
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Solution (Python):

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

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

    N = int(input())
    
    A = [deque() for _ in range(N+1)]
    
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    
    today = set()
    
    for i in range(1,N+1):
        
        if i in today:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in today):
            today.add(ME)
            today.add(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    
    if not today:
        print(-1)
        exit()

    
    yesterday = today
    
    answer = 1
    while is_not_empty(A):
        today = set()
        
        for i in yesterday:
            if not A[i]:
                continue
            if i in today:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in today):
                today.add(ME)
                today.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not today:
            print(-1)
            exit()
        answer += 1
        yesterday = today

    print(answer)

if __name__ == '__main__':
    main()

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):
N = int(input())
A = []
for i in range(N):
    temp = list(map(int, input().split()))
    for j in range(N-1):
        temp[j] -= 1
    A.append(temp)

cand = list(range(N))
cur = [0] * N
goal = 0
day = 0
while goal < N:
    day += 1
    game = []
    new_cur = cur[:]
    for i in cand:
        if i in game or cur[i] == N-1:
            continue
        opponent = A[i][cur[i]]
        if A[opponent][cur[opponent]] == i:
            new_cur[i] += 1
            new_cur[opponent] += 1
            game.append(i)
            game.append(opponent)
            if new_cur[i] == N-1:
                goal += 1
            if new_cur[opponent] == N-1:
                goal += 1
    cand = game
    cur = new_cur
    if not game:
        print(-1)
        exit()

print(day)

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

def topological_sort(E, D):
    D = D[:]
    n = len(E)
    Q = [i for i in range(n) if D[i] == 0]
    L = []
    while Q:
        p = Q.pop()
        L.append(p)
        for vf in E[p]:
            D[vf] -= 1
            if not D[vf]:
                Q.append(vf)
    
    if len(L) != n:
        return False
    return L

def check(E, D, N):
    D = D[:]
    Q = [i for i in range(N**2) if D[i] == 0 and i//N < i%N]
    
    cnt = 0
    res = 0
    match = N*(N-1)//2
    while match > res:
        cnt += 1
        res += len(Q)
        Q2 = []
        for q in Q:
            for vf in Edge[q]:
                D[vf] -= 1
                if not D[vf]:
                    Q2.append(vf)
        Q = Q2[:]
    return cnt
        
N = int(readline())
AA = [list(map(lambda x:int(x)-1, readline().split())) for _ in range(N)]

Edge = [[] for _ in range(N**2)]
Dim = [0]*(N**2)
for i in range(N):
    for j in range(N-2):
        noden = min(i, AA[i][j]) * N + max(i, AA[i][j])
        nodef = min(i, AA[i][j+1]) * N + max(i, AA[i][j+1])
        Dim[nodef] += 1
        Edge[noden].append(nodef)
L = topological_sort(Edge, Dim)
if L == False:
    ans = -1
else:
    ans = check(Edge, Dim, N)
print(ans)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
    ls = [0] * n
    ql = [[0, i] for i in range(n)]
    ql = collections.deque(ql)
    for i in range(10 ** 10):
        fq = collections.defaultdict(int)
        while ql:
            d, p = ql.popleft()
            if d == i:
                if ls[p] < n - 1:
                    rp = a[p][ls[p]]
                    if ls[rp] < n - 1:
                        rrp = a[rp][ls[rp]]
                        if p == rrp:
                            if p not in fq and rp not in fq:
                                fq[p]
                                fq[rp]
                                if ls[p] + 1 < n:
                                    ls[p] += 1
                                    ql.append([d+1, p])
                                if ls[rp] + 1 < n:
                                    ls[rp] += 1
                                    ql.append([d+1, rp])
            elif d > i:
                ql.appendleft([d, p])
                break
        if len(ql) == 0:
            print(i if sum(ls) == (n - 1) * n else -1)
            exit()


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]

n = int(input())
m = n * (n-1) // 2
graph = [list() for _ in range(m)]
deg = [0] * m

to_id = tdlist(n, n)
cnt = 0
for i in range(n):
    for j in range(i+1, n):
        to_id[i][j], to_id[j][i] = cnt, cnt
        cnt += 1

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n-2):
        v = to_id[i][a[j]-1]
        u = to_id[i][a[j+1]-1]
        graph[v].append(u)
        deg[u] += 1

q = deque(v for v in range(m) if deg[v] == 0)
cnt = 0
dp = [0] * m

while q:
    v = q.popleft()
    cnt += 1
    for u in graph[v]:
        deg[u] -= 1
        dp[u] = max(dp[u], dp[v] + 1)
        if deg[u] == 0:
            q.append(u)

print(-1 if cnt != m else max(dp)+1)

Solution (Python):
import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict, deque


def getlist():
	return list(map(int, input().split()))


def main():
	
	N = int(input())
	outE = defaultdict(list)
	inE = defaultdict(int)
	for i in range(N):
		A = getlist()
		for j in range(N - 2):
			a, b = sorted([A[j] - 1, i])
			c, d = sorted([A[j + 1] - 1, i])
			outE[a * N + b].append(c * N + d)
			inE[c * N + d] += 1

	
	Q = []
	for i in range(N):
		for j in range(i + 1, N):
			if inE[i * N + j] == 0:
				Q.append(i * N + j)
	
	
	judge = "Yes"
	cnt = 0
	ans = 1
	while True:
		q = []
		for i in Q:
			for j in outE[i]:
				inE[j] -= 1
				cnt += 1
				if inE[j] == 0:
					q.append(j)

		if q == []:
			break
		else:
			Q = q
		ans += 1
	
	

	if cnt != N * (N - 2):
		print(-1)
	else:
		print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = [list(map(lambda x: int(x) - 1, input().rstrip('\n').split())) for _ in range(n)]
    ps = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])
    for i in range(10 ** 10):
        fq = collections.defaultdict(int)
        while ql:
            d, p = ql.popleft()
            if d == i:
                if ps[p] < n - 1:
                    np = a[p][ps[p]]
                    if ps[np] < n - 1:
                        rp = a[np][ps[np]]
                        if p == rp:
                            if p not in fq and np not in fq:
                                fq[p]
                                fq[np]
                                ps[p] += 1
                                if ps[p] < n - 1:
                                    ql.append([d+1, p])
                                ps[np] += 1
                                if ps[np] < n - 1:
                                    ql.append([d+1, np])
            else:
                ql.appendleft([d, p])
                break
        else:
            print(i + 1 if sum(ps) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

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

Solution (Python):
def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    
    
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            j-=1
            if i>j:temp.append(d[(j,i)])
            else:temp.append(d[(i,j)])
        for j in range(len(temp)-1):
            g[temp[j]].append(temp[j+1])
            gr[temp[j+1]]+=1
    
    
    q=[]
    for i in range(m):
        if gr[i]==0:
            q.append(i)
    cnt=0
    
    while q:
        cnt+=1
        qq=[]
        temp=[]
        s=set()
        while q:
            i=q.pop()
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        
        while temp:
            i=temp.pop()
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)



main()

Solution (Python):
import time

t0 = time.clock()

N = int(input())
mat = []
for i in range(N):
    mat.append(list(map(lambda x:int(x)-1, input().split())))

ind = [0 for i in range(N)]
days = 0
while True:
    if time.clock() - t0 > 1:
        print(N * (N - 1) // 2)
        quit()
        
    madeMatch = False
    
    played = [False for i in range(N)]
    for i in range(N):
        if ind[i] == N-1 or played[i]: continue
        playAgainst = mat[i][ind[i]]
        if mat[playAgainst][ind[playAgainst]] == i and not played[playAgainst]:
            madeMatch = True
            played[i] = True
            played[playAgainst] = True

            ind[playAgainst] += 1
            ind[i] += 1
    if not madeMatch: break
    days += 1
    
if all(x == N-1 for x in ind):
    print(days)
else:
    print(-1)

Solution (Python):

from collections import deque

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

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

Solution (Python):
n=int(input())
lst_to=[[] for i in range(n**2)]
lst_from=[[] for i in range(n**2)]
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(n-2):
        i1=i
        i2=i
        b=a[j]-1
        c=a[j+1]-1
        if i1>b:
            i1,b=b,i1
        if i2>c:
            i2,c=c,i2
        lst_to[n*i1+b].append(n*i2+c)
        lst_from[n*i2+c].append(n*i1+b)

que=[]
for i in range(n):
    for j in range(i+1,n):
        if not lst_from[n*i+j]:
            que.append(n*i+j)

count=0
while que:
    count+=1
    h=[]
    for u in que:
        for v in lst_to[u]:
            lst_from[v].remove(u)
            if not lst_from[v]:
                h.append(v)
    que=h

for i in range(n):
    for j in range(i+1,n):
        if lst_from[n*i+j]:
            print(-1)
            break
    else:
        continue
    break
else:
    print(count)

Solution (Python):
N = int(input())
A = list(list(map(int,input().split()))for _ in range(N))

c = [0]*(N)
p = []
for i in range(N):
    j = A[i][c[i]]-1
    if i == A[j][c[j]]-1 and i < j:
        p.append((i,j))
ans = 0
while p:
    q = []
    for i,j in p:
        c[i] += 1
        c[j] += 1
        if c[i] < N-1:
            k = A[i][c[i]]-1
            if A[k][c[k]]-1 == i:
                q.append((i,k))
        if c[j] < N-1:
            k = A[j][c[j]]-1
            if A[k][c[k]]-1 == j:
                q.append((j,k))
    ans += 1
    p = q[:]

if min(c) != N-1:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = collections.defaultdict(list)
        while True:
            if len(ql) != 0:
                d, ps = ql.popleft()
                if d == i:
                    if ps not in fq:
                        nw = a[ps][ls[ps]]
                        if nw not in fq:
                            rw = a[nw][ls[nw]]
                            if ps == rw:
                                fq[ps]
                                fq[nw]
                                ls[ps] += 1
                                ls[nw] += 1
                                if ls[ps] < n - 1:
                                    ql.append([d+1, ps])
                                if ls[nw] < n - 1:
                                    ql.append([d+1, nw])
                else:
                    ql.appendleft([d, ps])
                    break
            else:
                if sum(ls) == n * (n - 1):
                    print(i + 1)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = collections.defaultdict(list)
        while True:
            if len(ql) != 0:
                d, ps = ql.popleft()
                if d == i:
                    if ps not in fq:
                        nw = a[ps][ls[ps]]
                        if nw not in fq:
                            rw = a[nw][ls[nw]]
                            if ps == rw:
                                fq[ps]
                                fq[nw]
                                ls[ps] += 1
                                ls[nw] += 1
                                if ls[ps] < n - 1:
                                    ql.append([d+1, ps])
                                if ls[nw] < n - 1:
                                    ql.append([d+1, nw])
                else:
                    ql.appendleft([d, ps])
                    break
            else:
                if sum(ls) == n * (n - 1):
                    print(i + 1)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    solve()

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 collections import deque

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

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

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

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

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

print(max(day))

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

solve()