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())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [[[] for i in range(n)] for i in range(n)]
c = 0
day = 0
for i in range(n):
    ap = [i,a[i][0]-1]
    ap.sort()
    for j in range(1,n-1):
        p = [i,a[i][j]-1]
        p.sort()
        l[ap[0]][ap[1]].append(p)
        ap = p
rl = [[0 for i in range(n)] for i in range(n)]
dl = [[0 for i in range(n)] for i in range(n)]
d = deque()
for i in range(n):
    for j in range(n):
        if i < j:
            if len(l[i][j]) > 0:
                for k in l[i][j]:
                    rl[k[0]][k[1]] += 1

for i in range(n):
    for j in range(n):
        if i < j:
            if rl[i][j] == 0:
                d.append([[i,j],0])
al = []
key = 0

if len(d) == 0:
    key = 1
while len(d):
    
    now,day = d.pop()
    day += 1
    if len(l[now[0]][now[1]]) == 0:
        al.append(day)
    else:
        for i in l[now[0]][now[1]]:
            if rl[i[0]][i[1]] == 1:
                rl[i[0]][i[1]] -= 1
                d.append([i,max(day,dl[i[0]][i[1]])])
            else:
                rl[i[0]][i[1]] -= 1
                dl[i[0]][i[1]] = max(day,dl[i[0]][i[1]])
    if day > n*(n-1)//2:
        key = 1
        break
md = 0
for i in range(n):
    md += sum(rl[i])
if key == 1 or md > 0:
    print(-1)
else:
    print(max(al))

Solution (Python):
n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print(-1)
  if semi:
    print(499500)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


n = inn()
pr = [[ [] for i in range(n+1) ] for j in range(n+1)]
ch = [[ [] for i in range(n+1) ] for j in range(n+1)]
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        ch[x1][y1].append((x2,y2))
        pr[x2][y2].append((x1,y1))
g = [ [0]*(n+1) for i in range(n+1) ]
q = []
for i in range(1,n):
    for j in range(i+1,n+1):
        if len(pr[i][j])==0:
            q.append((i,j))
            g[i][j] = 1
        else:
            g[i][j] = 0
ddprint(ch)
ddprint("pr")
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.pop()
    i,j = z
    for u,v in ch[i][j]:
        g[u][v] = max(g[u][v], g[i][j]+1)
        
        pr[u][v].remove(z)
        if len(pr[u][v])==0:
            
            q.append((u,v))
ddprint("newg")
ddprint(g)

gmn = BIG
for i in range(1,n):
    for j in range(i+1,n+1):
        gmn = min(gmn,g[i][j])
if gmn==0:
    print(-1)
else:
    print(max([max(r) for r in g]))

Solution (Python):
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

q = [[]]
l = [0] * 1005
d = [0] * 1005
hv = [0] * 1005

def dfs(x,y):
    hv[x] = 1
    for i in range(l[x],n-1):

        if q[x][i] == y:
            l[x] = i+1
            hv[x] = 0

            d[q[x][i]] += 1
            d[x] += 1
            d[x] = max(d[x],d[q[x][i]])
            d[q[x][i]] = max(d[x], d[q[x][i]])

            return
        if hv[q[x][i]]:
            print(-1)
            exit(0)
        dfs(q[x][i],x)
        d[x] = max(d[q[x][i]],d[x])


    hv[x] = 0
    l[x] = n

n = int(input())
for i in range(n):
    a = list(rrd())
    q.append(a)

for i in range(1,n+1):
    dfs(i,0)

print(max(d))

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  
            return dp[v]
        visited[v] = True
        for u in V[v]:  
            res = dfs(u)
            if res == -1: return -1  
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  
            return
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

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

ans = 0
matched = 0
marker = [0] * N
que = list(range(N))

while matched < N * (N - 1) // 2:
    already_matched = set()
    next_que = []

    while que:
        player = que.pop()
        partner = A[player][marker[player]]

        if A[partner][marker[partner]] == player:
            if not ((player not in already_matched) and (partner not in already_matched)):
                continue

            matched += 1

            marker[player] += 1
            marker[partner] += 1

            already_matched.add(player)
            already_matched.add(partner)

            next_que.append(player)
            next_que.append(partner)

    if not next_que:
        print(-1)
        break

    ans += 1
    que = next_que[:]

else:
    print(ans)

Solution (Python):
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
toNum = {}
L = N*(N-1)//2
s = [0]
for i in range(N-1,0,-1):
  s += [s[-1]+i]
dist = [0]*L
for i in range(N):
  inf = [int(c)-1 for c in input().split()]
  pa = min(i,inf[0])
  pb = max(i,inf[0])
  pnum = s[pa]+(pb-pa-1)
  for j in range(1,N-1):
    a = min(i,inf[j])
    b = max(i,inf[j])
    num = s[a]+(b-a-1)
    dic[pnum]  += [num]
    dist[num] += 1
    pa = a
    pb = b
    pnum = num

hq = []
ans = 0
for i in range(L):
  if dist[i]==0:
    hq += [i]
while hq:
  ans += 1
  nq = []
  for e in hq:
    for p in dic[e]:
      if dist[p]==0:
        continue
      dist[p] -= 1
      if dist[p]==0:
        nq += [p]
  hq = nq
if sum(dist) != 0:
  ans = -1
print(ans)

Solution (Python):
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
  A[i] = [-1]+[int(c)-1 for c in input().split()][::-1]

def f(cand):
  can_use = []
  candl = set()
  for i in cand:
    c = A[i][-1]
    if A[c][-1]==i:
      can_use += [i]
  for n in can_use:
    A[n].pop()
    candl.add(n)
    if A[n][-1]!=-1:
      candl.add(A[n][-1])
  return len(can_use),candl

ans = 0
rest = N*(N-1)
cand = set(range(N))
while True:
  ans += 1
  x, cand = f(cand)
  if x==0:
    ans = -1
    break
  rest -= x
  if rest==0:
    break
print(ans)

Solution (Python):
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]
candidate = list(range(N))
match = 0
day = 0

while True:
    day += 1
    used = set()
    next = set()
    bool = False
    for c in candidate:
        if len(A[c]) == 0:
            continue
        op = A[c][0] - 1
        if c in used or op in used:
            continue
        if A[op][0] - 1 == c:
            bool = True
            A[c].popleft()
            A[op].popleft()
            match += 1
            next |= {c, op}
            used |= {c, op}
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()
    candidate = next

print(day)

Solution (Python):
from collections import deque

def func(x):
    return x - 1

def main():
    N = int(input())
    A = [deque(map(func,map(int, input().split()))) for _ in range(N)]
    
    pre_players = range(N)
    game_cnt = 0
    day_cnt = 0
    max_cnt = N * (N - 1) // 2
    while day_cnt < max_cnt:
        
        players = set()
        for p in pre_players:
            if p in players:
                continue
            if not A[p]:
                continue
            opp = A[p][0]
            if opp in players:
                continue

            if p == A[opp][0]:
                A[p].popleft()
                A[opp].popleft()
                players |= {p,opp}
                game_cnt += 1

        pre_players = players
        day_cnt += 1

        if max_cnt == game_cnt:
            break

    if game_cnt != max_cnt:
        print(-1)
    else:
        print(day_cnt)
    
    

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

v = 0
ans = 0
t = N*(N-1)//2

last_used = set(range(1, N+1))
while v<t and ans<t:
    used = set()
    for n in last_used:
        if n in used:continue
        if not l[n]:continue
        pair = l[n][0]
        b = l[pair][0]
        if pair in used:continue

        if b==n:
            l[n].popleft()
            l[pair].popleft()
            used|={n,pair}
            v += 1
    last_used = used
    ans += 1

if ans==t and ans!=v:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
import collections
import copy

input = sys.stdin.readline


def main():
    N = int(input())
    A = [collections.deque([int(x) for x in input().split()]) for _ in range(N)]

    day = 0
    c = 0
    nxt = [x for x in range(N)]
    oppo = [0] * N

    while c != N * (N - 1):
        day += 1

        for i in nxt:
            oppo[i] = A[i].popleft() if A[i] else -1

        tmp = set()
        for i in nxt:
            if i == -1 or i in tmp:
                continue
            if i == oppo[oppo[i] - 1] - 1:
                tmp.add(i)
                tmp.add(oppo[i] - 1)
                c += 2
        if not tmp:
            print(-1)
            return

        nxt = tmp

    print(day)


if __name__ == '__main__':
    main()

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

ans = 0
matched = 0
marker = [0] * N
que = list(range(N))

while matched < N * (N - 1) // 2:
    already_matched = set()
    no_matched = True
    next_que = []

    while que:
        player = que.pop()
        partner = A[player][marker[player]]

        if A[partner][marker[partner]] == player:
            if not ((player not in already_matched) and (partner not in already_matched)):
                continue

            matched += 1

            marker[player] += 1
            marker[partner] += 1

            already_matched.add(player)
            already_matched.add(partner)

            next_que.append(player)
            next_que.append(partner)

            no_matched = False

    ans += 1
    que = next_que[:]
    if no_matched:
        print(-1)
        break

else:
    print(ans)

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

G = [list(map(int, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
    edge[i] = G[i][0] - 1

day = 0
player = set(range(N))
cnt = 0
while len(player) > 0:
    day += 1
    game = set()
    for i in player:
        e = edge[i]
        if i == edge[e] and i != e:
            game.add(i)
            game.add(e)
    player = set()
    for j in game:
        cur[j] += 1
        c = cur[j]
        if c >= N - 1:
            edge[j] = j
        else:
            edge[j] = G[j][c] - 1
            player.add(j)

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

Solution (Python):
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]
answer = 0
match = 0
candidate = list(range(N))
while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0] - 1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

answer = 0
match = 0

candidate = list(range(N))
while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

match = 0
candidate = []
used = set()
for i in range(N):    
    bool = False
    if len(A[i]) == 0:
        continue
    op = A[i][0] - 1
    if op in used or i in used:
        continue
    if A[op][0]-1 == i:
        used.add(i)
        used.add(op)
        candidate.extend([i, op])
        match += 1
        bool = True
        A[i].popleft()
        A[op].popleft()
answer = 1

while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

match = 0
candidate = []
used = set()
for i in range(N):    
    bool = False
    if len(A[i]) == 0:
        continue
    op = A[i][0] - 1
    if op in used or i in used:
        continue
    if A[op][0]-1 == i:
        used.add(i)
        used.add(op)
        candidate.extend([i, op])
        match += 1
        bool = True
        A[i].popleft()
        A[op].popleft()
answer = 1

while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Solution (Python):
def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if o == -1:
                continue
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
                w[i] = -1
                w[o] = -1
        if not nxt:
            return -1
        cur = []
        for i in nxt:
            if A[i]:
                w[i] = A[i].pop()
                cur.append(i)
            else:
                r -= 1
    return d


print(main())

Solution (Python):
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = N * (N - 1) / 2
    d = 0
    n = set(range(N))
    while True:
        p = 0
        l = set()
        d += 1
        for i in n:
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j].pop() 
                A[i].pop()
                t -= 1
                p += 1
        n = l
        if t == 0:
            print(d)
            break
        if p == 0:
            print(-1)
            break
main()

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

N = int(input())
A = [[]] + [list(map(int, input().split()))[::-1] for _ in range(N)]

pair = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

stack = []
for i in range(1, N + 1):
  a = A[i].pop()
  pair[i][a] += 1
  if pair[i][a] == pair[a][i] == 1:
    stack.append(i)
    stack.append(a)

r = []
answer = 1
while stack:
  while stack:
    i = stack.pop()
    if A[i]:
      a = A[i].pop()
      pair[i][a] += 1
      if pair[i][a] == pair[a][i] == 1:
        r.append(i)
        r.append(a)
  stack = r
  if r:
    answer += 1
  r = []
  
flag = 1
for i in range(1, N + 1):
  if A[i]:
    flag = 0
    break
if flag:
  print(answer)
else:
  print(-1)

Solution (Python):
from collections import deque

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

q = deque(range(n))

days = [0]*n  

while q:
    x = q.popleft()  
    if len(matches[x]) == 0:  
        continue
    y = matches[x][0]  
    if matches[y][0] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
        _ = matches[x].pop(0)
        _ = matches[y].pop(0)

if not any(matches):  
    print(max(days))
else:
    print(-1)

Solution (Python):
from collections import deque

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

q = deque(range(n))

days = [0]*n  

while q:
    x = q.popleft()  
    if len(matches[x]) == 0:  
        continue
    y = matches[x][0]  
    if matches[y][0] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
        _ = matches[x].pop(0)
        _ = matches[y].pop(0)

if not any(matches):  
    print(max(days))
else:
    print(-1)

Solution (Python):
from collections import deque

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

q = deque(range(n))

days = [0]*n  
pairs = [-1]*n  

while q:
    x = q.popleft()  
    if len(matches[x]) == 0:  
        continue
    y = matches[x].pop(0)  
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
    else:
        pairs[x] = y

if not any(matches):  
    print(max(days))
else:
    print(-1)

Solution (Python):
from collections import deque
a = int(input())
l = [] 
for i in range(a):
    tl = list(map(int,input().split()))
    tl = list(map(lambda x:x-1 ,tl))
    l.append(tl)

q = deque((range(a)))
days=[0]*a
pairs=[-1]*a
while q:
    x = q.popleft()
    if len(l[x]) == 0:continue
    y = l[x].pop(0)
    if pairs[y] == x:
        days[x]=days[y]=max(days[x],days[y])+1
        q.append(x)
        q.append(y)
    else:
        pairs[x]=y
if not any(l):
    print(max(days))
else:
    print(-1)

Solution (Python):
from collections import deque
N = int(input())
A = [deque(map(lambda x: int(x)-1,input().split(" "))) for _ in range(N)]
ans = 0
used_prev = set(range(N))

while any(A):
    used = set()
    for i in used_prev:
        a = A[i]
        if not a or i in used:
            continue
        j = a[0]
        b = A[j]
        if not b or j in used:
            continue
        if i == b[0]:
            A[i].popleft()
            A[j].popleft()
            used.add(i)
            used.add(j)
    if not used:
        ans = -1
        break
    used_prev = used
    ans += 1
print(ans)

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


def main():
    N = int(input())
    A = [deque(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
    ans = 0
    used_prev = set(range(N))
    while any(A):
        used = set()
        for i in used_prev:
            a = A[i]
            if not a or i in used:
                continue
            j = a[0]
            b = A[j]
            if not b or j in used:
                continue
            if i == b[0]:
                A[i].popleft()
                A[j].popleft()
                used.add(i)
                used.add(j)
        if not used:
            ans = -1
            break
        used_prev = used
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

CONT = True
IDXS=[0]*N
days = 0
ST=set()

next_check = range(N)
while CONT:
    cont = False
    _next_check = []
    for i in next_check:
        if IDXS[i] < N-1:
            pair = MATCHES[i][IDXS[i]]
            p, q = pair
            if pair in ST:
                ST.remove(pair)
                
                if IDXS[i] < N-1:
                    IDXS[p-1] += 1
                    IDXS[q-1] += 1
                    cont = True
                    _next_check.append(p-1)
                    _next_check.append(q-1)
            else:
                ST.add(pair)
    next_check = _next_check
    CONT = cont
    days += cont


if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Solution (Python):

import sys

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    MAXGAME = (N*(N-1))//2
    match = set()

    while True:
        if totalGame == 0:
            for i in range(N):
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1
        else:
            if totalGame == MAXGAME:
                break

            check_needed = list(match)
            
            match = set()

            for i in check_needed:
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1

        if len(match) == 0:
            print(-1)
            return

        answer += 1

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [[int(next(tokens)) for _ in range(N - 1)] for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

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

A = [None] * N



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


def f(candi):
    
    played = []
    
    
    for n in candi:
        target = A[n][-1]
        if A[target][-1] == n:
            played.append(n)
        
    new_candi = set()    
    for n in played:
        
        A[n].pop()
        
        new_candi.add(n)
        
        if A[n][-1] != -1:
            new_candi.add(A[n][-1])
            
    return len(played), new_candi


answer = 0

rest = N*(N-1)

play_candi = set(range(N))

while True:
    answer += 1
    x, play_candi = f(play_candi)
    
    if x == 0:
        answer = -1
        break
        
    rest -= x
    if rest ==0:
        break
        
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
league = [0]*(n+1)
cnt = 0

while True:
  topop = []
  if cnt == 0:
    for i,player in enumerate(a):
      x = player[-1]
      if league[x] == i+1:
        topop.append(x)
        topop.append(i+1)
      else:
        league[i+1] = x
  else:
    for player in popped:
      if a[player-1] == []:
        continue
      x = a[player-1][-1]
      if league[x] == player:
        topop.append(x)
        topop.append(player)
      else:
        league[player] = x
  popped = []
  if topop == []:
    print(-1)
    exit()
  for t in topop:
    if a[t-1] == []:
      print(-1)
      exit()
    a[t-1].pop()
    popped.append(t)
  cnt += 1
  if not any(a[i] for i in range(n)):
    break
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
league = [0]*(n+1)
cnt = 0

while True:
  topop = []
  if cnt == 0:
    for i,player in enumerate(a):
      x = player[-1]
      if league[x] == i+1:
        topop.append(x)
        topop.append(i+1)
      else:
        league[i+1] = x
  else:
    for player in popped:
      if a[player-1] == []:
        continue
      x = a[player-1][-1]
      if league[x] == player:
        topop.append(x)
        topop.append(player)
      else:
        league[player] = x
  popped = []
  if topop == []:
    print(-1)
    exit()
  for t in topop:
    if a[t-1] == []:
      print(-1)
      exit()
    a[t-1].pop()
    popped.append(t)
  cnt += 1
  if not any(a[i] for i in range(n)):
    break
print(cnt)