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():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    
    ind = [i for i in range(N)]

    while len(ind) > 0:
        next_ = []
        while len(ind) > 0:
            i = ind.pop(-1)
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:
                    if a[want][now[want]] - 1 == i:
                        now[want] += 1
                        now[i] += 1
                        if now[want] < N-1:
                            next_.append(want)
                        if now[i] < N-1:
                            next_.append(i)
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        
        ind = next_
        day += 1
    ok = True
    for i in range(N):
        if now[i] < N-1:
            ok = False
            break
    if ok:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

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

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}




end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    elp=time.time()-ts
    if elp>1.8:
        ans=n*(n-1)//2
        break
    ans+=1
    IsMatch=False
    done=set()
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            if t[c1]:
                n_i=t[c1].pop()
            else:
                n_i=n
                n_yet.remove(c1)
            if t[c2]:
                n_n_i=t[c2].pop()
            else:
                n_n_i=n
                n_yet.remove(c2)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)

Solution (Python):
import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1

    v = 0  
    
    Id = [[-1 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:  
                Id[i][j] = v
                v += 1

    def toId(i, j):
        if i > j:
            i, j = j, i
        return Id[i][j]

    
    e = [[] for i in range(maxv)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n - 2):
            e[a[i][j + 1]].append(a[i][j])

    
    calculated = [False for i in range(maxv)]
    dp = [-1 for i in range(maxv)]

    def dfs(v):
        if dp[v] != -1:  
            if not calculated[v]:
                return -1
            return dp[v]
        dp[v] = 1
        for u in e[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from collections import defaultdict, deque
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)

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):
import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    v = 0
    Id = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                v += 1

    def toId(i, j):
        if i > j:
            i, j = j, i
        return Id[i][j]

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

    visited = [False for i in range(maxv)]
    calculated = [False for i in range(maxv)]
    dp = [-1 for i in range(maxv)]

    def dfs(v):
        if dp[v] != -1:
            if not calculated[v]:
                return -1
            return dp[v]
        visited[v] = True
        dp[v] = 1
        for u in to[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    v = 0
    Id = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                v += 1

    def toId(i, j):
        if i > j:
            i, j = j, i
        return Id[i][j]

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

    visited = [False for i in range(maxv)]
    calculated = [False for i in range(maxv)]
    dp = [0 for i in range(maxv)]

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

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] 
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] 
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 
            second_num = s[second] 
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.835:
        print(n*(n-1)//2)
        exit()
print(ans)

Solution (Python):
import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] 
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] 
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 
            second_num = s[second] 
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.83:
        print(n*(n-1)//2)
        exit()
print(ans)

Solution (Python):
import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] 
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] 
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 
            second_num = s[second] 
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.81:
        print(n*(n-1)//2)
        exit()
print(ans)

Solution (Python):
from collections import defaultdict

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

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

    day = 0
    
    M = defaultdict(int)
    
    for i in range(N):
        M[i] += 1

    
    W = [0] * N

    while M:
        day += 1
        
        for m in M:
            
            W[m] = A[m].pop(0) if A[m] else -1

        
        _M = defaultdict(int)
        for m in M:
            
            if W[m] >= 0 and W[W[m]] == m:
                
                _M[m] += 1
                _M[W[m]] += 1

        M = _M

    if sum(W) != -N:
        print(-1)
    else:
        print(day - 1)
            

main()

Solution (Python):

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    scheduled[x] = 1
    for i in range(cur[x], N - 1):
        z = A[x][i]  
        if z == y:
            cur[x] = i + 1
            scheduled[x] = 0
            days[x] += 1
            days[z] += 1
            days[x] = days[z] = max(days[x], days[z])
            return
        if scheduled[z]:  
            print(-1)
            exit()
        dfs(z, x)


def main():
    global N, A, cur, days, scheduled
    N = int(input())
    A = [0] + list(list(map(int, input().split())) for _ in range(N))
    cur, days, scheduled = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
    for i in range(1, N + 1):
        dfs(i, 0)
    ans = max(days)  
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    scheduled[x] = 1
    for i in range(cur[x], N - 1):
        z = A[x][i]  
        if z == y:
            cur[x] = i + 1
            scheduled[x] = 0
            days[x] += 1
            days[z] += 1
            days[x] = days[z] = max(days[x], days[z])
            return
        if scheduled[z]:  
            print(-1)
            exit()
        dfs(z, x)


def main():
    global N, A, cur, days, scheduled
    N = int(input())
    A = [0] + list(list(map(int, input().split())) for _ in range(N))
    cur, days, scheduled = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
    for i in range(1, N + 1):
        dfs(i, 0)
    ans = max(days)  
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


import sys
import time
from collections import deque

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

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

start = time.time()

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

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

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
A = [0] * N
l = [[int(x) for x in stdin.readline().rstrip().split()] for _ in A]
d = 1
k = N * (N - 1)

while sum(A) < k and d < 10 ** 4:
    L = [1] * N
    y = 0
    d += 1
    for i in range(N):
        if A[i] < N - 1:
            x = l[i][A[i]] - 1
            if l[x][A[x]] * L[x] * L[i] == i + 1:
                A[i] += 1
                A[x] += 1
                L[i] = L[x] = 0
                y = 1

print([k // 2, d * y - 1][d * y < 9999])

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
A=["dammy"]+[deque(list(map(int,input().split()))) for _ in range(n)]
Q,planned,day=deque([_ for _ in range(1,n+1)]),[0]*(n+1),[0]*(n+1)
cnt=0

while Q:
    x=Q.popleft()
    if not A[x]:
        pass
    else:
        y=A[x].popleft()
        if planned[y]==x:
            day[x],day[y]=max(day[x],day[y])+1,max(day[x],day[y])+1
            cnt+=1
            planned[x],planned[y]=0,0
            Q.append(x)
            Q.append(y)
        else:
            planned[x]=y

if cnt!=(n*(n-1))//2:
    print(-1)
else:
    print(max(day))

Solution (Python):
from collections import deque

N = int(input())
A = [['nul']] + [list(map(int, input().split())) for _ in range(N)]


c = [0 for _ in range(N + 1)]
predeq = deque([])

for i in range(1, N + 1):
    j = A[i][c[i]]
    if i == A[j][c[j]] and i < j:
        predeq.append((i, j))

ans = 0
while predeq:
    
    postdeq = deque([])
    for i, j in predeq:
        c[i] += 1
        c[j] += 1
        if c[i] < N - 1:
            k = A[i][c[i]] 
            if A[k][c[k]] == i:
                postdeq.append((i, k))
        if c[j] < N - 1:
            k = A[j][c[j]]
            if A[k][c[k]] == j:
                postdeq.append((j, k))
    ans += 1
    predeq = postdeq

if c == [0] + [N - 1] * N:
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import deque
from pprint import pprint
N = int(input())
nextGame = [deque()] + [deque(map(int , input().split())) for _ in range(N)]


canPlay = [[False] * (N + 1) for _ in range(N + 1)]

days = [0] * (N + 1)
que = ([i for i in range(N + 1)])

while que:
    now = que.pop()
    
    if not nextGame[now]:
        continue
    enemy = nextGame[now].popleft()
    canPlay[now][enemy] = True
    
    
    

    if canPlay[now][enemy] and canPlay[enemy][now]:
        days[now] = days[enemy] = max(days[now], days[enemy]) + 1
        que.append(now)
        que.append(enemy)
    

for test in nextGame:
    if test:
        print("-1")
        exit(0)
print(max(days))

Solution (Python):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

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

    ans = 0

    def find_next(idx, q, m):
        if agrid_pointer[idx] == n - 1 or i in m:  
            return

        target = agrid[idx][agrid_pointer[idx]]
        if agrid_pointer[target] == n - 1 or target in m:  
            return

        if agrid[target][agrid_pointer[target]] != idx:
            return

        q.append((idx, target))
        m.add(idx)
        m.add(target)

    que = deque()
    first_matching = set()
    for i in range(n):
        find_next(i, que, first_matching)

    while que:
        ans += 1

        changed = []
        while que:
            i, j = que.popleft()
            agrid_pointer[i] += 1
            agrid_pointer[j] += 1
            changed.append(i)
            changed.append(j)

        next_que = deque()
        match = set()
        for i in changed:
            find_next(i, next_que, match)

        
        que = next_que

    
    
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())

    nextGame = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    canPlay = [[False] * (N + 1) for _ in range(N + 1)]
    days = [0] * (N + 1)

    que = deque([i for i in range(1, N + 1)])

    while que:
        now = que.pop()
        if not nextGame[now]:
            continue
        enemy = nextGame[now].popleft()
        canPlay[now][enemy] = True

        if canPlay[now][enemy] and canPlay[enemy][now]:
            days[now] = days[enemy] = max(days[now], days[enemy]) + 1
            que.append(now)
            que.append(enemy)

    for a in nextGame:
        if a:
            print('-1')
            return

    ans = max(days)
    print(ans)


sol()

Solution (Python):
from collections import defaultdict
N = int(input())
A = [[0 for _ in range(N - 1)] for _ in range(N)]
for i in range(N):
  A[i] = [int(x) - 1 for x in input().split()]
day = 0
M = defaultdict(int)
for i in range(N):
  M[i] += 1
W = [0] * N
while M:
  day += 1
  for m in M:
    W[m] = A[m].pop(0) if A[m] else -1
  _M = defaultdict(int)
  for m in M:
    if W[m] >= 0 and W[W[m]] == m:
      _M[m] += 1
      _M[W[m]] += 1
  M = _M
for w in W:
  if w > 0:
    print(-1)
    break
else:
  print(day - 1)

Solution (Python):

from collections import deque

def main():
    N = int(input())
    M = [[]]
    for cm in range(N):
        A = list(map(int,input().split()))
        M.append(A)

    q = deque(range(1, N+1))
    day = [0] * (N+1)
    opponent = [-1] * (N+1)

    while q:
        a = q.popleft()
        if len(M[a]) > 0:
            b = M[a][0]
            if opponent[b] == a:
                day[a] = day[b] = max(day[a],day[b]) + 1
                opponent[a] = opponent[b] = -1
                M[a].pop(0)
                M[b].pop(0)
                q.append(a)
                q.append(b)
            else:
                opponent[a] = b

    remain = max([len(Mx) for Mx in M])
    if remain > 0:
        print(-1)
    else:
        answer = max(day)
        answer = answer if answer > 0 else -1
        print(answer)
    
if __name__ == "__main__":
    main()

Solution (Python):
n=int(input());a=[0]*n;l=[list(map(int,input().split()))for i in a];d=1;k=n*~-n
while sum(a)<k and d<1e4:
 L=[1]*n;y=0;d+=1
 for i in range(n):
  if-~a[i]-n:
   x=l[i][a[i]]-1
   if l[x][a[x]]*L[x]*L[i]==i+1:a[i]+=1;a[x]+=1;L[i]=L[x]=0;y=1
print([k//2,d*y-1][d*y<1e4])

Solution (Python):
n=int(input());a=[0]*n;l=[list(map(int,input().split()))for i in a];d=1;k=n*~-n
while sum(a)<k and d<1e4:
 L=[1]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]*L[x]*L[i]==i+1:a[i]+=1;a[x]+=1;L[i]=L[x]=0;y=1
print([k//2,d*y-1][d*y<1e4])

Solution (Python):
def e_league():
    import sys
    sys.setrecursionlimit(10**6)
    N = int(input())
    A = [[int(i) - 1 for i in input().split()] for j in range(N)]

    
    match_num = 0
    identification = [[None] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i < j:
                identification[i][j] = match_num
                match_num += 1

    vertex_max = N * (N - 1) // 2  
    
    match_allocation = [row for row in A]
    
    next_match = [[] for _ in range(vertex_max)]

    def to_id(i, j):
        if i > j:
            i, j = j, i
        return identification[i][j]

    
    for i in range(N):
        for j in range(N - 1):
            match_allocation[i][j] = to_id(i, match_allocation[i][j])
        for j in range(N - 2):
            next_match[match_allocation[i][j]].append(match_allocation[i][j + 1])

    
    
    is_visited = [False] * vertex_max
    is_calculated = [False] * vertex_max
    dp = [0] * vertex_max  

    def dfs(v):
        if is_visited[v]:
            
            if not is_calculated[v]:
                return -1
            return dp[v]

        is_visited[v] = True
        dp[v] = 1
        for u in next_match[v]:
            ret = dfs(u)
            if ret == -1:
                return -1  
            dp[v] = max(dp[v], ret + 1)  
        is_calculated[v] = True  
        return dp[v]

    ans = 0
    for v in range(match_num):
        res = dfs(v)
        if res == -1:
            return -1
        ans = max(ans, res)
    return ans

print(e_league())

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*~-n
while sum(a)<k and d<9999:
 L=[1]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]*L[x]*L[i]==i+1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=0;y=1
print([k//2,d*y-1][d*y<9999])

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*~-n
while sum(a)<k and d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
print([k//2,d*y-1][d*y<9999])

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*(n-1)
while sum(a)<k and d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
print([k//2,d*y-1][d*y<9999])

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*(n-1)
while sum(a)<k and d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
d*=y;print([k//2,d-1][d<9999])

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


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    N = int(input())
    X = [[] for i in range(N)]
    for i in range(N):
        for j in LI():
            X[i].append(j-1)
        X[i].reverse()

    Q = []
    def check(i):
        if len(X[i])==0:
            return
        j = X[i][-1]
        if len(X[j])==0:
            return
        if i==X[j][-1]:
            if i<j:
                Q.append((i,j))
            else:
                Q.append((j,i))

    for i in range(N):
        check(i)

    day = 0
    while len(Q)>0:
        day += 1
        Q.sort()
        Q = list(set(Q))
        prevQ = Q.copy()
        Q = []
        for i,j in prevQ:
            X[i].pop()
            X[j].pop()
        for i,j in prevQ:
            check(i)
            check(j)

    for i in range(N):
        if len(X[i])>0:
            print("-1")
            return

    print(day)
    return

main()

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
 d*=y
print([k//2,d-1][d<9999])

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[];y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if not(l[x][a[x]]-1!=i or x in L or i in L):
    a[i]+=1;a[x]+=1;L+=[i,x];y=1
 d*=y
print([k//2,d-1][d<9999])

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[];y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and not(x in L or i in L):
    a[i]+=1;a[x]+=1;L+=[i,x];y=1
 d*=y
print([k//2,d-1][d<9999])

Solution (Python):
from collections import deque

N, *A = map(int, open(0).read().split())
V = N * (N - 1) // 2

serial = [[0 for _ in range(N)] for _ in range(N)]
k = 0
for i in range(N):
    for j in range(i + 1, N):
        serial[i][j] = serial[j][i] = k
        k += 1

G = [[] for _ in range(V)]
deg = [0] * V
for s, a in zip(serial, zip(*[iter(A)] * (N - 1))):
    for j in range(N - 2):
        G[s[a[j] - 1]].append(s[a[j + 1] - 1])
        deg[s[a[j + 1] - 1]] += 1

Q = deque((k, 1) for k, v in enumerate(deg) if v == 0)

ans = 0
cnt = len(Q)
while Q:
    v, ans = Q.popleft()
    for t in G[v]:
        deg[t] -= 1
        if deg[t] == 0:
            Q.append((t, ans + 1))
            cnt += 1

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

Solution (Python):
import sys
from collections import deque

n = int(input())
matches = [None] + [list(map(int, line.split())) for line in sys.stdin]
q = deque(range(1, n + 1))
depth = [0] * (n + 1)
waiting = [-1] * (n + 1)

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

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

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

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

Solution (Python):
import sys
from collections import deque

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

while q:
    a = q.popleft()
    ma = matches[a]
    if not ma:
        continue
    b = ma.pop()
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        q.append(a)
        q.append(b)
    else:
        waiting[a] = b

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

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[0 for i in[0]*n];y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
 d*=y
print([k//2,d-1][d<9999])