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 bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    s1 = set()
    s2 = set()

    def update(i):
        if not A[i-1]:
            return

        d = A[i-1][-1]
        n = (min(i, d), max(i, d))
        if n not in s1:
            s1.add(n)
        else:
            s2.add(n)
            s1.remove(n)

    for i in range(1, N+1):
        update(i)

    while s2:
        ans += 1
        s2_, s2 = s2, set()
        for k in s2_:
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            update(a)
            update(b)


    for a in A:
        if a:
            return -1
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    s1 = set()
    s2 = set()

    def update(i):
        if not A[i-1]:
            return

        d = A[i-1][-1]
        n = (min(i, d), max(i, d))
        if n not in s1:
            s1.add(n)
        else:
            s2.add(n)
            s1.remove(n)

    for i in range(1, N+1):
        update(i)

    while s2:
        ans += 1
        for k in tuple(s2):
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            update(a)
            update(b)
            s2.remove(k)


    for a in A:
        if a:
            return -1
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    s1 = set()
    s2 = set()

    def update(i):
        if not A[i-1]:
            return

        d = A[i-1][-1]
        n = (min(i, d), max(i, d))
        if n not in s1:
            s1.add(n)
        else:
            s2.add(n)
            s1.remove(n)

    for i in range(1, N+1):
        update(i)

    while s2:
        ans += 1
        for k in list(s2):
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            update(a)
            update(b)
            s2.remove(k)


    for a in A:
        if a:
            return -1
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))

    
    

    
    
    
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=0;k=n*(n-1)
while sum(a)<k and -1<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
 if y<1:d=-1
print([k//2,d][d<9999])

Solution (Python):
n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def conv(a, b, b_max):
    return a*(b_max+1)+b

def main(): 
    N = II()
    
    
    

    
    

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    for i in range(N):
        
        a = LI()
        for j in range(1,N-1):
            
            
            
            
            prev_v = (min(i+1, a[j-1]), max(i+1, a[j-1]))
            next_v = (min(i+1, a[j]), max(i+1, a[j]))
            prev_v = conv(prev_v[0]-1, prev_v[1]-1, N)
            next_v = conv( next_v[0]-1, next_v[1]-1, N)
            outs[prev_v].append(next_v)
            ins[next_v] += 1

    
    

    from collections import deque
    q = deque()
    for i in range(1, N+1):
        for j in range(1, N+1):
        
            if i < j and ins[conv(i-1, j-1, N)] == 0:
                q.append([conv( i-1, j-1, N), 0])

    if not q:
        print(-1)
        return

    
    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth+1])
                depth_max = max(depth_max, depth+1)
    if len(res)!=N*(N-1)//2:
        print(-1)
        return
    else:
        print(depth_max+1)
        return

main()

Solution (Python):
from collections import deque

n = int(input())
a = [0]*n

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

t = [a[i][0] for i in range(n)]

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

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

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

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

print(max(day))

Solution (Python):
from collections import deque
import time     
start = time.time()
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
    aida = time.time()
    if aida-start > 1.7:
        print(N*(N-1)//2)       
        exit()
print(ans-1)

Solution (Python):
import sys
from collections import deque


def topological_check(roots, out_links, in_count):
    depth = [0] * match_count
    for r in roots:
        depth[r] = 1
    q = deque(roots)
    while q:
        v = q.popleft()
        d = depth[v] + 1
        for u in out_links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                depth[u] = d
                q.append(u)
    if any(in_count):
        return -1
    return max(depth)


n = int(input())
match_count = n * (n - 1) // 2

offsets = [0]
tmp = -2
for i in range(1, n + 1):
    offsets.append(tmp)
    tmp += n - i - 1

roots = set()
in_links = [set() for _ in range(match_count)]
out_links = [set() for _ in range(match_count)]

for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    prev = offsets[i] + j if i < j else offsets[j] + i
    roots.add(prev)

    for j in aaa[1:]:
        key = offsets[i] + j if i < j else offsets[j] + i
        out_links[prev].add(key)
        in_links[key].add(prev)
        prev = key

in_count = list(map(len, in_links))
roots = {r for r in roots if in_count[r] == 0}

if not roots:
    print(-1)
    exit()

print(topological_check(roots, out_links, in_count))

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

Solution (Python):
def solve_e(n, a_list):
    days = 0
    ind_list = [0] * n
    match_count = 0
    queue = list(range(n))
    stack = dict()
    while len(queue) > 0:
        days += 1
        new_queue = []
        for p in queue:
            if ind_list[p] < n - 1:
                q = a_list[p][ind_list[p]] - 1
                k = str(min(p, q)) + "_" + str(max(p, q))
                if k in stack.keys():
                    ind_list[p] += 1
                    ind_list[q] += 1
                    
                    new_queue.append(p)
                    new_queue.append(q)
                    match_count += 1
                else:
                    stack[k] = 1
        queue = new_queue
    if match_count == n * (n - 1) // 2:
        return days - 1
    else:
        return -1


def test():
    n = 1000
    a_list = []
    for i in range(n):
        a_list.append(list(range(1, i + 1)) + list(range(i + 2, n + 1)))
    print(solve_e(n, a_list))


def main():
    n = int(input())
    a_list = []
    for _ in range(n):
        a_list.append(list(map(int, input().split())))
    print(solve_e(n, a_list))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def conv(n,a,b):
    return a*(2*n-a-1)//2+b-a-1

def main(): 
    N = II()
    
    
    

    
    

    from collections import defaultdict
    outs = defaultdict(list)
    ins = defaultdict(int)
    for i in range(N):
        
        a = LI()
        for j in range(1,N-1):
            
            
            
            
            prev_v = (min(i+1, a[j-1]), max(i+1, a[j-1]))
            next_v = (min(i+1, a[j]), max(i+1, a[j]))
            prev_v = conv(N, prev_v[0]-1, prev_v[1]-1)
            next_v = conv(N, next_v[0]-1, next_v[1]-1)
            outs[prev_v].append(next_v)
            ins[next_v] += 1

    
    

    from collections import deque
    q = deque()
    for i in range(1, N+1):
        for j in range(1, N+1):
        
            if i < j and ins[conv(N, i-1, j-1)] == 0:
                q.append([conv(N, i-1, j-1), 0])

    if not q:
        print(-1)
        return

    
    res = []
    depth_max = 0
    while q:
        v1, depth = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append([v2, depth+1])
                depth_max = max(depth_max, depth+1)
    if len(res)!=N*(N-1)//2:
        print(-1)
        return
    else:
        print(depth_max+1)
        return


main()

Solution (Python):
from sys import stdin

from collections import deque



def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

move_in = [[[] for i in range(N)] for j in range(N)]
move_out = [[[] for i in range(N)] for j in range(N)]
cost = [[0] * N for _ in range(N)]
start_pair = []
for i in range(N):
    a_list = _li_()
    start_pair.append(a_list[0])
    for j in range(N-2):
        start = [min(i, a_list[j]), max(i, a_list[j])]
        end = [min(i, a_list[j+1]), max(i, a_list[j+1])]
        move_in[end[0]][end[1]].append((start[0], start[1]))
        move_out[start[0]][start[1]].append((end[0], end[1]))

count = 0
stack = deque([])
for i in range(N):
    pair = start_pair[i]
    if i < pair and i == start_pair[pair]:
        stack.append((i, start_pair[i]))
        cost[i][start_pair[i]] = 1
        count += 1


ans = 0
while stack:
    cand = stack.pop()
    for dest in move_out[cand[0]][cand[1]]:
        cost[dest[0]][dest[1]] = max(cost[dest[0]][dest[1]],
                                     cost[cand[0]][cand[1]] + 1)
        in_list = move_in[dest[0]][dest[1]]
        if in_list[0] == cand:
            del in_list[0]
        else:
            del in_list[1]
        if len(in_list) == 0:
            count += 1
            if len(move_out[dest[0]][dest[1]]) == 0:
                ans = max(ans, cost[dest[0]][dest[1]])
            else:
                stack.append(dest)

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

Solution (Python):
import time

start = time.time()

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0

for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
    if time.time() - start > 1.9:
        print(N*(N-1)//2)
        exit(0)
print(days)

Solution (Python):

from collections import deque


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


if __name__ == "__main__":
    main()

Solution (Python):
import collections as cl
def l(): 
    return list(map(int,input().split()))
def onem(): 
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Solution (Python):

from collections import deque


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


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n=int(input())
A=[]
for i in range(n):
  A.append([int(i) for i in input().split()])
nn=n*(n-1)//2
F=[[0]*(n+1) for _ in range(n+1)]
cur=0
for i in range(1,n):
  for j in range(i+1,n+1):
    F[i][j]=cur
    F[j][i]=cur
    cur+=1
Edge=[[] for _ in range(nn)]
Deg=[0]*nn
for i in range(n):
  s=F[i+1][A[i][0]]
  for j in range(1,n-1):
    t=F[i+1][A[i][j]]
    Edge[s].append(t)
    Deg[t]+=1
    s=t
ans=0
S=[i for i in range(nn) if Deg[i]==0]
D=deque()
DD=deque(S)
while DD:
  D=DD
  DD=deque()
  while D:
    d=D.popleft()
    for g in Edge[d]:
      Deg[g]-=1
      if Deg[g]==0:
        DD.append(g)
        S.append(g)
  ans+=1
print(-1 if len(S)<nn else ans)

Solution (Python):

from collections import deque


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


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


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


if __name__ == "__main__":
    main()

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())
N =n*(n-1)//2

a = [[int(j)-1 for j in readline().split()] for _ in range(n)]
g = [[] for i in range(N)]
indegree = [0]*N

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

for i in range(n):
    for j in range(n-2):
        p,q = encode(i,a[i][j]), encode(i,a[i][j+1])
        g[p].append(q)
        indegree[q] += 1

"""
トポロジカルソート
q をheapq にしたりすると、辞書順にとりだしたりとかができる。
返り値：DAG ならトポソのひとつを返す。ループがあれば-1を返す
"""
"""
g: グラフの隣接行列
indegree: 流入辺の数を数えた配列
"""
def topological_sort_queue(g,indegree):
    q = [i for i,c in enumerate(indegree) if c == 0] 
    L = [] 
    ans =[0]*len(g)
    a = 0
    while q:
        v = q.pop()
        L.append(v)
        for c in g[v]: 
            ans[c] = max(ans[c],ans[v]+1)
            a = max(a,ans[c])
            indegree[c] -= 1 
            if indegree[c] == 0:
                q.append(c)
    if len(L) != N: 
        return -1
    else: 
        return(a+1)        

print(topological_sort_queue(g,indegree))

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.8:
        print(n*(n-1)//2)
        exit()
print(ans)

Solution (Python):

import sys
import time

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

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

    start = time.time()

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  
                continue
            

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  
                break

        
        if len(match) == 0:  
            break
        elapsed_time = time.time() - start
        if elapsed_time > 1.5:
            print(n * (n-1)//2)
            return

        ans += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)

Solution (Python):
import sys
import time


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1):
            print(n * (n-1) // 2)
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()

Solution (Python):
import sys
sys.setrecursionlimit(2000000)


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

visited = [[-1] *(len(a[0])) for i in range(n)]
memo = [[-1] * (n) for i in range(n)]

for i in range(n):
    for j in range(len(a[0])):
        memo[i][a[i][j]] = j

def solve(i_me, j_me, rec_times):
    if rec_times >= 10000:
        print(-1)
        exit()
    i_you = a[i_me][j_me]
    j_you = memo[i_you][i_me]
    
    if visited[i_me][j_me] > 0 and visited[i_you][j_you] > 0:
        return max(visited[i_me][j_me], visited[i_you][j_you])

    if j_me == 0 and j_you == 0:
        visited[i_me][j_me] = 1
        visited[i_you][j_you] = 1
        return 1
    
    if j_you == 0:
        day = solve(i_me, j_me - 1, rec_times + 1) + 1
    elif j_me == 0:
        day = solve(i_you, j_you - 1, rec_times + 1) + 1    
    else:
        day = max(solve(i_me, j_me - 1, rec_times + 1), solve(i_you, j_you - 1, rec_times + 1)) + 1
    visited[i_me][j_me] = day
    visited[i_you][j_you] = day
    return day
    
for i in range(n):
    solve(i, len(a[0]) - 1, 0)
ans = 0
for i in range(n):
    ans = max(ans,visited[i][-1])
print(ans)

Solution (Python):
N = int(input())
A = []
rem = N * (N-1) // 2
for _ in range(N):
    *temp, = map(int, input().split())
    A.append(temp[::-1])
day = 0
next_opponent = [-1]*N
played_yesterday = list(range(N))
while rem:
    day += 1
    impossible = True
    for p in played_yesterday:
        if A[p]: next_opponent[p] = A[p].pop() - 1
    played_today = []
    for p in played_yesterday:
        candidate = next_opponent[p]
        if candidate == -1: continue 
        elif next_opponent[candidate] == p: 
            impossible = False
            rem -= 1
            played_today += [p, candidate]
            next_opponent[p], next_opponent[candidate] = -1, -1
    if impossible: print(-1); break
    played_yesterday = played_today
else:
    print(day)