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

game = []
for p1 in range(N):
    p2 = A[p1][0]
    if A[p2][0] == p1 and p1 < p2:
        game.append((p1, p2))

cursors = [0] * N
days = 0
while game:
    days += 1
    new_game = []
    for p1, p2 in game:
        cursors[p1] += 1
        if cursors[p1] < N - 1:
            p3 = A[p1][cursors[p1]]
            if cursors[p3] < N - 1 and A[p3][cursors[p3]] == p1:
                new_game.append((p1, p3))
        cursors[p2] += 1
        if cursors[p2] < N - 1:
            p3 = A[p2][cursors[p2]]
            if cursors[p3] < N - 1 and A[p3][cursors[p3]] == p2:
                new_game.append((p2, p3))
    game = new_game

if all(c == N - 1 for c in cursors):
    print(days)
else:
    print(-1)

Solution (Python):
def main():
    n = int(input())
    a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
    id = [[0]*n for _ in range(n)]
    V = 0
    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:
            return id[i][j]
        else:
            return id[j][i]
    
    to = [[] for _ in range(V)]
    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])

    dp, visited, calculated = [1] * V, [0] * V, [0] * V

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

    ans = 0
    for v in range(V):
        res = dfs(v, dp, visited, calculated)
        if res == -1:
            print(-1)
            return
        ans = max(ans, res)
    print(ans)
    return

main()

Solution (Python):
def main():
    n = int(input())
    a = [list(map(lambda x : int(x)-1, input().split())) for _ in range(n)]
    for i in range(n):
        a[i].reverse()
    
    s = set()

    def check(i, s):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if len(a[j]) == 0:
            return
        if a[j][-1] == i:
            if i < j:
                s.add((i, j))
            else:
                s.add((j, i))
    
    for i in range(n):
        check(i, s)
    day = 0
    while s:
        day += 1
        prevS = set()
        s, prevS = prevS, s
        for p in prevS:
            i = p[0]
            j = p[1]
            a[i].pop()
            a[j].pop()
        for p in prevS:
            i = p[0]
            j = p[1]
            check(i, s)
            check(j, s)
    
    for i in range(n):
        if len(a[i]):
            print(-1)
            return
    print(day)
    return

main()

Solution (Python):

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

while len(tmp) >= 1:
    check = [0] * n
    t = []
    for i in tmp:
        if check[i] == 0 :
            j = a[i][count[i]]
            if i == a[j][count[j]] and check[j] == 0:
                count[i] += 1
                count[j] += 1
                check[i], check[j] = 1, 1
                if count[i] < n-1:
                    t.append(i)
                if count[j] < n-1:
                    t.append(j)
    tmp = t
    ans += 1

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

Solution (Python):
from collections import deque

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

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(i+1, N):
    hash_table[i][j] = hash_table[j][i] = count
    count += 1


graph = [[] for i in range(m)]
before_this = [0] * m
for i in range(1, N+1):
  A = deque(list(map(int, input().split())))
  pre_a = A.popleft()
  pre_pair = hash_table[i-1][pre_a-1]
  for a in A:
    pair = hash_table[i-1][a-1]
    graph[pre_pair].append(pair)
    before_this[pair] += 1
    pre_pair = pair


games = deque([])
for i in range(m):
  if not before_this[i]:
    games.append(i)


if not games:
  ans = -1
else:
  ans = 0
  num_finished = 0
  while games:
    ans += 1
    num_games = len(games)
    num_finished += num_games
    for i in range(num_games):
      pair = games.popleft()
      subseq = graph[pair]
      for ss in subseq:
        before_this[ss] -= 1
        if not before_this[ss]:
          games.append(ss)
    
  if num_finished != m:
    ans = -1

print(ans)

Solution (Python):
N=int(input())
A=[[] for _ in range(N)]

for i in range(N):
    A[i]=list(map(int,input().split()))

NE=[0]*N
F=[0]*N


Q=[[],[]]


for i in range(N):
    opp=A[i][0]-1
    if A[opp][0]-1==i:
        NE[i]+=1
        Q[0].append(i)

ans=1

for d in range(N*(N-1)//2):
    F=[0]*N
    a=d%2
    b=(d+1)%2
    while len(Q[a])!=0:
        i=Q[a].pop()
        if NE[i]==N-1:
            continue
        opp=A[i][NE[i]]-1
        if F[i]==1 or F[opp]==1:
            continue
        if A[opp][NE[opp]]-1==i:
            NE[i]+=1
            NE[opp]+=1
            F[i]=1
            F[opp]=1
            if NE[i]!=N-1:
                Q[b].append(i)
            if NE[opp]!=N-1:
                Q[b].append(opp)
    ans+=1
    if len(Q[a])==0 and len(Q[b])==0:
        break

for i in range(N):
    if NE[i]!=N-1:
        ans=-1
print(ans)

Solution (Python):
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.buffer.readline

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

    adj = defaultdict(list)
    in_num = defaultdict(int)
    for i in range(N):
        for j in range(N-2):
            x1 = x2 = i+1
            y1 = A[i][j]
            y2 = A[i][j+1]
            if x1 > y1:
                x1, y1 = y1, x1
            if x2 > y2:
                x2, y2 = y2, x2
            adj[x1*(N+1)+y1].append(x2*(N+1)+y2)
            in_num[x2*(N+1)+y2] += 1
    st = []
    ng = (N * (N - 1)) // 2
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if in_num[i*(N+1)+j] == 0:
                st.append(i*(N+1)+j)
                ng -= 1
    ans = 0
    while st:
        ans += 1
        st_new = []
        for par in st:
            for child in adj[par]:
                if in_num[child] == 1:
                    st_new.append(child)
                    ng -= 1
                in_num[child] -= 1
        if st_new:
            st = st_new
        else:
            break

    if ng:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
 
to = [[] for _ in range(MAXV)]
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)]
 
def toId(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]
visited = [False] * MAXV
calculated = [False] * MAXV
dp = [1] * 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]:
        res = dfs(u)
        if res == -1: return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]
 
def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1
    
    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])
    
    ans = 0
    
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1')
            return
        ans = max(ans, res)
    print(ans)
    return
  
if __name__ == '__main__':
    main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
now=[0]*n
rest=n*(n-1)//2
for i in range(n):
    for j in range(n-1):
        A[i][j]=A[i][j]-1

S={i for i in range(n)}
tmp=set()
while rest and S:
    used=[0]*n  
    
    count+=1
    for si in S:
        if n-1<=now[si]:
            continue
        ene=A[si][now[si]]
        if n-1<=now[ene]:
            continue
        if A[ene][now[ene]] == si and not(used[si] or used[ene]):
            rest-=1
            now[si]+=1; now[ene]+=1
            used[si]=used[ene]=1
            tmp.add(si); tmp.add(ene)
    S=tmp.copy(); tmp=set()
for ni in now:
    if ni != n-1:
        print(-1)
        break
else:
    print(count)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    M=[None]*n
    for i in range(n):
        M[i]=list(map(lambda x:int(x)-1,input().split()))[::-1]

    
    def check(i):
        if(not M[i]): 
            return False
        j=M[i][-1]
        if(not M[j]): 
            return False
        return i==M[j][-1]

    
    
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i 
            Q.append((i,j))

    
    day=0
    nQ=[] 
    while(Q):
        
        Q=list(set(Q))
        
        for i,j in Q:
            M[i].pop(); M[j].pop()
        
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print(day if(all(M[i]==[] for i in range(n))) else "-1")
resolve()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
  N=int(input())
  A=[deque()]+[deque(map(int,input().split())) for _ in range(N)]
  Days=[0]*(N+1)
  NOW=[0]*(N+1)
  
  q=deque([i+1 for i in range(N)])
  
  while q:
    i=q.popleft()

    if not A[i]:
      continue
    a=A[i].popleft()
    
    if NOW[a]==i:
      Days[a]=Days[i]=max(Days[a],Days[i])+1
      q.append(i)
      q.append(a)
      NOW[a]=NOW[i]=0
    else:
      NOW[i]=a
    
  for i in range(1,N+1):
    if A[i]:
      print(-1)
      return
  print(max(Days))
      

if __name__ == '__main__':
  main()

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

def main():

  n=int(input())

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

  day=0
  zan=[n-1]*n
  zann=sum(zan)
  sumi=set(range(n))

  while True:
    day+=1

    kouho=list(sumi)
    sumi=set()
  
    for i in kouho:
      try:
        if A[A[i][-1]-1][-1]-1==i:
          sumi.add(i)
          sumi.add(A[i][-1]-1)
      except:
        pass

    for k in sumi:
      A[k].pop()
      zan[k]-=1

    if zann==sum(zan):
      print(-1)
      exit(0)
  
    zann=sum(zan)
  
    if zann==0:
      print(day)
      exit(0)
    
if __name__ == "__main__":
	main()

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

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

day=0
zan=[n-1]*n
zann=sum(zan)
sumi=set(range(n))

while True:
  day+=1

  kouho=list(sumi)
  sumi=set()
  
  for i in kouho:
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print(-1)
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)

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


def main():
	n = int(input())

	def label(a, b):
		if a > b:
			a, b = b, a
		return (a - 1) * (2 * n - a) // 2 + b - a - 1

	m = n * (n - 1) // 2
	g = [[] for _ in range(m)]
	deg = [0] * m
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y)
			g[label(i, x)].append(t)
			deg[t] += 1

	depth = [None] * m
	q = deque()
	ans = 1
	for i, d in enumerate(deg):
		if not d:
			depth[i] = 1
			q.append(i)
	while q:
		cur = q.popleft()
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				if ans < depth[nxt]:
					ans = depth[nxt]
				q.append(nxt)
	print(ans if all(depth) else -1)

if __name__ == "__main__":
	main()

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

def f(g: list, deg: list):
	l = len(g)
	depth = [0] * l
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				ret.append(nxt)
				q.append(nxt)
	if l > len(ret):
		return False
	return max(depth)

def label(a, b, n):
	if a > b:
		a, b = b, a
	return (a - 1) * (2 * n - a) // 2 + b - a - 1


def main():
	n = int(input())
	g = [[] for _ in range(n * (n - 1) // 2)]
	deg = [0] * (n * (n - 1) // 2)
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y, n)
			g[label(i, x, n)].append(t)
			deg[t] += 1
	depth = f(g, deg)
	if not depth:
		print(-1)
		exit()
	print(depth + 1)

if __name__ == "__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n=int(input())
a=[]
for i in range(n):
    a.append(tuple(map(int,input().split())))


root=[[] for i in range(n*(n-1)//2)]
buf=0
for i in range(n):
    buf=0
    for j in range(n-1):
        if j==0:
            x=min(i,a[i][j]-1)
            y=max(i,a[i][j]-1)
            buf=x*(2*n-2-x+1)//2+(y-x)-1
            
            continue
        x=min(i,a[i][j]-1)
        y=max(i,a[i][j]-1)
        node=x*(2*n-2-x+1)//2+(y-x)-1
        
        root[buf].append(node)
        buf=node
flag=[True]


def dfs(node,par): 
    dp[node]=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]==0:
            flag[0]=False
            return
        if dp[item]==-1: 
            dfs(item,node)
    dp[node]=1
dp=[-1]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dfs(i,i)
        if flag[0]==False:
            break
if flag[0]==False:
    print(-1)
    sys.exit()
dp=[-1]*(n*(n-1)//2)
def dfs1(node,par): 
    buf=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]!=-1:
            buf=max(buf,dp[item])
            continue
        if dp[item]==-1: 
            buf=max([buf,dfs1(item,node)])
    dp[node]=buf+1
    return buf+1

for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dp[i]=dfs1(i,i)
print(max(dp))

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

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

id=[[0 for j in range(N)] for i in range(N)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    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(v)]
inner=[0 for i in range(v)]
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]].append(a[i][j+1])
    inner[a[i][j+1]]+=1

stack=[]
isstarted=[False for i in range(v)]
dist=[0 for i in range(v)]
for i in range(v):
  if inner[i]==0:
    stack.append([i,1])

while stack:
  node=stack.pop()
  e=node[0]
  d=node[1]
  if d>dist[e]:
    dist[e]=d
  inner[e]-=1
  if inner[e]<=0 and not isstarted[e]:
    isstarted[e]=True
    children=to[e]
    for child in children:
      stack.append([child,dist[e]+1])
for i in range(len(isstarted)):
  if not isstarted[i]:
    print(-1)
    break
else:
  ans=0
  for i in range(len(dist)):
    if dist[i]>ans:
      ans=dist[i]
  print(ans)

Solution (Python):
N=int(input())
MAXN=1005
MAXV=N*(N-1)//2

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

id=[[0 for j in range(MAXN)] for i in range(MAXN)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    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)]
inner=[0 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]].append(a[i][j+1])
    inner[a[i][j+1]]+=1

ans=0
stack=[]
isstarted=[False for i in range(v)]
dist=[0 for i in range(v)]
for i in range(v):
  if inner[i]==0:
    stack.append([i,1])

while stack:
  node=stack.pop()
  e=node[0]
  d=node[1]
  if d>dist[e]:
    dist[e]=d
  else:
    d=dist[e]
  if dist[e]>ans:
    ans=dist[e]
  inner[e]-=1
  if inner[e]<=0 and not isstarted[e]:
    isstarted[e]=True
    children=to[e]
    for child in children:
      stack.append([child,d+1])
for i in range(len(isstarted)):
  if not isstarted[i]:
    print(-1)
    break
else:
  print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N=int(input())
MAXN=1005
MAXV=N*(N-1)//2

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

id=[[0 for j in range(MAXN)] for i in range(MAXN)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    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
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(v):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

Solution (Python):
N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
stack=[]

def addmatch(i):
  if len(a[i])==0:
    return
  j=a[i][-1]
  if a[j][-1]==i:
    stack.append([i,j])

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

day=0
while stack:
  day+=1
  member=set()
  for i in range(len(stack)):
    g=stack.pop()
    y=g[0]
    x=g[1]
    if len(a[y])>0 and a[y][-1]==x:
      a[y].pop()
      a[x].pop()
      member.add(y)
      member.add(x)
  for m in member:
    addmatch(m)

for i in range(len(a)):
  if len(a[i])>0:
    print(-1)
    break
else:
  print(day)

Solution (Python):
N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]




def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)

Solution (Python):
from collections import deque

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

M = N*(N-1)//2

for i in range(N):
    for j in range(N-1):
        p = min(i+1,A[i][j])
        q = max(i+1,A[i][j])
        match = M-(N-p+1)*(N-p)//2+q-p-1
        A[i][j] = match
        
graph = [[] for _ in range(M)]
indegree = [0 for _ in range(M)]

for i in range(N):
    for j in range(1,N-1):
        graph[A[i][j-1]].append(A[i][j])
        indegree[A[i][j]] += 1
        
dist = [None for _ in range(M)]
queue = deque([])

for k in range(M):
    if indegree[k]==0:
        dist[k] = 0
        queue.append(k)

cycle = False

while queue:
    node = queue.popleft()
    for adj in graph[node]:
        indegree[adj] -= 1
        dist[adj] = dist[node] + 1
        if indegree[adj]==0:
            queue.append(adj)
            
if any(indegree):
    cycle = True

print(-1 if cycle else max(dist)+1)

Solution (Python):
n=int(input())
match=[]
for i in range(n):
    a=list(map(int, input().split()))
    match.append(a)

select=[list(range(n))]

day=0
mat=0
for _ in range(int(n*(n-1)/2)):
    nex=[]
    for x in select[day]:
        if len(match[x]) != 0 and not x in nex and not match[x][0]-1 in nex and match[match[x][0]-1][0] == (x+1):
            nex.append(x)
            nex.append(match[x][0]-1)
            match[match[x][0]-1].pop(0)
            match[x].pop(0)
            mat+=1

    if len(nex) == 0 and mat==int(n*(n-1)/2):
        break
    
    if len(nex) == 0:
        print(-1)
        exit()

    select.append(nex)
    day+=1

print(day)

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

from collections import deque

def main():

    n = int(input())
    
    a = [[int(i) for i in input().split()] for j in range(n)]
    
    check = [0]*n
    used = [0]*n
    
    d = deque()
    
    for i in range(n):
        if used[i] == 1:
            continue
        ai = a[i][0]-1
        if a[ai][0] == i+1:
            d.append([i+1,ai+1])
            used[i] = 1
            used[ai] = 1
            check[i] = 1
            check[ai] = 1
            
    ans = 0
    
    if len(d) == 0:
        print(-1)
        exit()
    
    
    
    while len(d) > 0:
        used = [0]*n
        ans += 1
        num = len(d)
        for i in range(num):
            tmp = d.popleft()
            for j in range(2):
                mys = tmp[j]-1
                if check[mys] != n-1 and used[mys] == 0:
                    psn = a[mys][check[mys]]-1
                    if check[psn] != n-1 and used[psn] == 0:
                    
                    
        
                        if a[psn][check[psn]] == mys+1:
                            d.append([psn+1,mys+1])
                            used[mys] = 1
                            used[psn] = 1
                            check[mys] += 1
                            check[psn] += 1
        
        
    for i in range(n):
        if check[i] != n-1:
            print(-1)
            exit()
    
    print(ans)

if __name__ == '__main__':
    main()

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

from collections import deque

def main():
    t1 = time.time()

    n = int(input())
    
    a = [[int(i) for i in input().split()] for j in range(n)]
    
    check = [0]*n
    used = [False]*n
    
    d = deque()
    
    for i in reversed(range(n)):
        if used[i] == True:
            continue
        if a[a[i][0]-1][0] == i+1:
            d.appendleft([i+1,a[i][0]])
            used[i] = True
            used[a[i][0]-1] = True
            check[i] = 1
            check[a[i][0]-1] = 1
            
    ans = 0
    
    if len(d) == 0:
        print(-1)
        exit()
    
    
    
    while len(d) > 0:
        if time.time() - t1 >= 1.95:
            print(n*(n-1)//2)
            exit()
        used = [False]*n
        ans += 1
        num = len(d)
        for i in range(num):
            tmp = d.popleft()
            for j in range(2):
                if check[tmp[j]-1] == n-1:
                    continue
                psn = a[tmp[j]-1][check[tmp[j]-1]]-1
                mys = tmp[j]-1
                
                if check[mys] == n-1 or check[psn] == n-1:
                    continue
                
                
                if used[mys] == True or used[psn] == True:
                    continue
    
                if a[psn][check[psn]] == mys+1:
                    d.append([psn+1,mys+1])
                    used[mys] = True
                    used[psn] = True
                    check[mys] += 1
                    check[psn] += 1
        
        
    for i in range(n):
        if check[i] != n-1:
            print(-1)
            exit()
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline

def main(): 
    N = int(input())
    
    Id = {}
    
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    cur = 0
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: a, b = i, j
            else: a, b = j, i
        
            if (a, b) not in Id:
                Id[(a, b)] = cur
                cur += 1
            k = Id[(a, b)]
        
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print(-1)
            sys.exit()
    print(ans)           

if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    Id = {}
    
    cur = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            Id[(i,j)] = cur
            cur += 1
            
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: k = Id[(i, j)]
            else: k = Id[(j, i)]
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print(-1)
            sys.exit()
    print(ans)
            
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    M=[None]*n
    for i in range(n):
        M[i]=list(map(lambda x:int(x)-1,input().split()))[::-1]

    
    def check(i):
        if(not M[i]): 
            return False
        j=M[i][-1]
        if(not M[j]): 
            return False
        return i==M[j][-1]

    
    
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i 
            Q.append((i,j))

    
    day=0
    nQ=[] 
    while(Q):
        
        Q=list(set(Q))
        
        for i,j in Q:
            M[i].pop(); M[j].pop()
        
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print(day if(all(M[i]==[] for i in range(n))) else "-1")
resolve()

Solution (Python):
import sys
from collections import defaultdict
from itertools import product, permutations, combinations
from time import time

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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

q = list(range(N))
c = defaultdict(int)
t = [0]*N
r = 0
a = time()

while q:
    b = time()
    if b - a > 1.7:
        print(N*(N-1)//2)
        exit()
    r += 1
    nq = []
    for i in q:
        j = A[i][t[i]] - 1
        k = i
        if k < j:
            j, k = k, j
        c[(j, k)] += 1
        if c[(j, k)] == 2:
            t[j] += 1
            t[k] += 1
            if t[j] < N-1:
                nq.append(j)
            if t[k] < N-1:
                nq.append(k) 
    q = nq

for tt in t:
    if tt != N-1:
        print(-1)
        exit()

print(r)

Solution (Python):
import sys
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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

q = list(range(N))
c = defaultdict(int)
t = [0]*N
r = 0

while q:
    r += 1
    nq = []
    for i in q:
        j = A[i][t[i]] - 1
        k = i
        if k < j:
            j, k = k, j
        c[(j, k)] += 1
        if c[(j, k)] == 2:
            t[j] += 1
            t[k] += 1
            if t[j] < N-1:
                nq.append(j)
            if t[k] < N-1:
                nq.append(k) 
    q = nq

for tt in t:
    if tt != N-1:
        print(-1)
        exit()

print(r)