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 sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    if j >= 4000:
        chk = 1
        break
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
if chk == 0:
    print(ans)
else:
    print(N*(N-1)//2)

Solution (Python):
from collections import deque
import sys
input=sys.stdin.readline
def main():
  a=int(input())
  b=[[]for i in range(a)]
  for i in range(a):
    b[i]=deque(list(map(int,input().split())))
  c=[[]for i in range(a)]
  ans=0
  d=[i for i in range(a)]
  while d:
    nextd=[]
    f=set()
    ans+=1
    T=0
    for i in d:
      if i not in f and len(b[i])>0:
        e=b[i][0]-1
        if e in c[i]:
          c[i].pop(c[i].index(e))
          T=1
          b[e].popleft()
          b[i].popleft()
          if len(b[i])>0:
            nextd.append(i)
          if len(b[e])>0:
            nextd.append(e)
          f|={i,e}
        else:
          c[e].append(i)
    if T==0:
      print(-1)
      exit()
    d=nextd
      
      
  print(ans)  
if __name__ == '__main__':  
  main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]
 
A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1
    
answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x,cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break
    
print(answer)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
import time

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.6:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break

Solution (Python):
import sys
from collections import deque
def solve():
    readline = sys.stdin.readline
    N = int(readline())
    G = [[] for i in range(N*N)]
    deg = [0]*(N*N)
    day = [0]*(N*N)
    F = set()
    for p in range(N):
        *A, = map(int, readline().split())
        for k in range(N-1):
            A[k] -= 1
        prv = A[0]+p*N if A[0] < p else p+A[0]*N
        F.add(prv)
        for a in A[1:]:
            i = a+p*N if a < p else p+a*N
            G[prv].append(i)
            deg[i] += 1
            prv = i
    que = deque()
    for i in F:
        if deg[i] == 0:
            que.append(i)
            day[i] = 1
    rest = N*(N-1)//2
    pop = que.popleft
    push = que.append
    while que:
        v = pop()
        rest -= 1
        d = day[v]+1
        for w in G[v]:
            deg[w] -= 1
            if deg[w] == 0:
                day[w] = d
                push(w)
    if rest > 0:
        print(-1)
    else:
        print(d-1)
solve()

Solution (Python):
import sys
input=sys.stdin.readline
from collections import defaultdict,deque
def conv(n,a,b):
    return a*(2*n-a-1)//2+b-a-1

n=int(input())
v=n*(n-1)//2
A=[list(map(lambda x: int(x)-1,input().split())) for _ in range(n)]
Edges=[]
for i in range(n):
    l=len(A[i])
    for j in range(l-1):
        a=A[i][j]
        b=A[i][j+1]
        fr_i,fr_j=min(i,a),max(i,a)
        to_i,to_j=min(i,b),max(i,b)
        Edges.append((conv(n,fr_i,fr_j),conv(n,to_i,to_j)))
Outs=defaultdict(list)
In_cnt=defaultdict(int)
for v1,v2 in Edges:
    Outs[v1].append(v2)
    In_cnt[v2]+=1
q=deque((v0,1) for v0 in range(v) if In_cnt[v0]==0)
TopologicalSort=[]
while q:
    v1,d=q.popleft()
    TopologicalSort.append((v1,d))
    for v2 in Outs[v1]:
        In_cnt[v2]-=1
        if In_cnt[v2]==0:
            q.append((v2,d+1))
print(TopologicalSort[-1][1] if len(TopologicalSort)==n*(n-1)//2 else -1)

Solution (Python):
import time
start = time.time()

import sys
input = sys.stdin.readline

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

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

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

    cnt += 1

print(cnt)

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])
    ans, cnt, matched = 0, 0, set()
    q = [i for i in range(1, N + 1)]
    while q:
        ans += 1
        next_q = []
        for i in q:
            if i in B and i not in matched:
                x = B[i][0]
                if x in B and x not in matched and B[x][0] == i:
                    B[i].popleft(), B[x].popleft()
                    matched |= {i, x}
                    cnt += 1
                    if not B[i]:
                        del B[i]
                    else:
                        next_q += [i]
                    if not B[x]:
                        del B[x]
                    else:
                        next_q += [x]
        q = next_q
        matched = set()
    flg = cnt == N * (N - 1) // 2
    print(ans if flg else -1)


if __name__ == "__main__":
    main()

Solution (Python):
import time
start = time.time()
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          dp = [n-1]*n
        else:
          if B[miru] != 1:
            if L[miru][dp[miru]][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              if act == 0:
                act = 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
  ela = time.time()-start
  if ela > 1.7:
    dp = [n-1]*n
if flag == False:
  print(-1)
else:
  if ela < 1.7:
    print(cnt)
  else:
    print(n*(n-1)//2)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
outs=[[] for i in range(1000000)]
ins=[0]*1000000
for i in range(n):
    a_list=list(map(int,input().split()))
    for j in range(1,n-1):
        x1=min(i,a_list[j-1]-1)
        y1=max(i,a_list[j-1]-1)
        z1=x1*1000+y1
        x2=min(i,a_list[j]-1)
        y2=max(i,a_list[j]-1)
        z2=x2*1000+y2
        outs[z1].append(z2)
        ins[z2]+=1
q=[]
for i in range(n):
    for j in range(i+1,n):
        if ins[1000*i+j]==0:
            q.append(1000*i+j)
res=0
ans=0
while q:
    ans+=1
    v1_list=[]
    while q:
        v1=q.pop()
        res+=1
        v1_list.append(v1)
    for v1 in v1_list:
        for v2 in outs[v1]:
            ins[v2]-=1
            if ins[v2]==0:
                q.append(v2)
if res==n*(n-1)//2:
    print(ans)
else:
    print(-1)

Solution (Python):
def solve():
    N = int(input())
    Ass = []
    for _ in range(N):
        As = list(map(lambda x: int(x)-1, input().split()))
        Ass.append(As+[N])

    games = []
    numReadyss = [[0]*(N) for _ in range(N)]
    iAs = [0] * N
    for i in range(N):
        j = Ass[i][iAs[i]]
        if j > i: i, j = j, i
        numReadyss[i][j] += 1
        if numReadyss[i][j] >= 2:
            games.append((i, j))
    ans = 1
    numOK = 0
    while True:
        if not games:
            print(-1)
            return
        game2s = []
        for i, j in games:
            iAs[i] += 1
            i2 = Ass[i][iAs[i]]
            if i2 == N:
                numOK += 1
            else:
                if i2 > i: i, i2 = i2, i
                numReadyss[i][i2] += 1
                if numReadyss[i][i2] >= 2:
                    game2s.append((i, i2))
            iAs[j] += 1
            j2 = Ass[j][iAs[j]]
            if j2 == N:
                numOK += 1
            else:
                if j2 > j: j, j2 = j2, j
                numReadyss[j][j2] += 1
                if numReadyss[j][j2] >= 2:
                    game2s.append((j, j2))
        if numOK >= N:
            print(ans)
            return
        ans += 1
        games = game2s


solve()

Solution (Python):
import sys, time
def input():
	return sys.stdin.readline()[:-1]

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

opponent = [-1 for _ in range(n)]
played = list(range(n))
match = 0
day = 0
while match < n*(n-1)//2:
	approved = False
	for i in played:
		if a[i] != []:
			opponent[i] = a[i].pop()-1
	played_next = []
	
	for i in played:
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			played_next += [i, opponent[i]]
			opponent[opponent[i]] = -1
			opponent[i] = -1
	
	if not approved:
		print(-1)
		sys.exit()
	day += 1
	played = played_next
print(day)

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

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

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

print(N*(N-1)//2)

Solution (Python):
from collections import deque
import time

start = time.time() 

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

all_set = set()
a = [deque(list(map(int, input().split()))) for i in range(n)]
ans = 0

while True:
  cur_set = set()
  flag = False
  for i in range(n):
    if len(a[i]):
      tup = (min(i+1, a[i][0]), max(i+1, a[i][0]))
    else:
      continue
    if tup not in cur_set:
      cur_set.add(tup)
    elif tup in cur_set:
      all_set.add(tup)
      t1, t2 = tup
      a[t1-1].popleft()
      a[t2-1].popleft()
      flag = True
  ans += 1
  if len(all_set)==target_num:
    break
  if time.time()-start>1.8:
    print(1000*999//2)
    exit()
  if not flag:
    print(-1)
    exit()

print(ans)

Solution (Python):
import time
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.6:
            print((N*(N-1))//2)
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:
                    if a[want][now[want]] - 1 == i:
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    

if __name__ == "__main__":
    main()

Solution (Python):
import time
s_time = time.time()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print(n*(n-1) //2)
        exit()
print(cnt)

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


def sol():
    N = int(input())
    A = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    days = [0] * (N + 1)
    now = [0] * (N + 1)

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

    while que:
        i = que.popleft()
        if not A[i]:
            continue

        a = A[i].popleft()
        if now[a] == i:
            days[a] = days[i] = max(days[a], days[i]) + 1
            que.append(i)
            que.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))


sol()

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
index = [0]*(N+1)
ans = -2
for k in range(10000):
    today = set()
    flag = 0
    for j in range(N):
        if j+1 in today:
            continue
        if index[j+1] >= N-1:
            continue
        
        opponent = A[j][index[j+1]]
        if A[opponent-1][index[opponent]] == j+1:
            if opponent not in today:
                index[opponent] += 1
                index[j+1] += 1
                today.add(opponent)
                today.add(j+1)
                flag = 1
    if flag == 0:
        if sum(index) == N*(N-1):
            ans = k
            break
        else:
            ans = -1
            break
    

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

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
S = 0
ans = 0
while True:
    C = [0]*N
    for n in range(N):
        if C[n]==0 and B[n]!=N-1:
            b = A[n][B[n]]
            if C[b]==1: continue
            if A[b][B[b]]==n:
                B[n]+=1
                B[b]+=1
                C[n],C[b]=1,1
    if sum(C)==0:break
    ans +=1
    if time.time()-start>1.7:
        print(N*(N-1)//2)
        exit()
print(ans if sum(B)==N*(N-1) else -1)

Solution (Python):
import sys, time
def input():
	return sys.stdin.readline()[:-1]

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

opponent = [-1 for _ in range(n)]
match = 0
day = 0
start_time = time.time()
while match < n*(n-1)//2:
	approved = False
	for i in range(n):
		if a[i] != [] and opponent[i] == -1:
			opponent[i] = a[i].pop()-1
	
	for i in range(n):
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			opponent[opponent[i]] = -1
			opponent[i] = -1
	
	if not approved:
		print(-1)
		sys.exit()
	now = time.time()
	
	if now-start_time > 1.6:
		print(n*(n-1)//2)
		sys.exit()
	day += 1
print(day)

Solution (Python):
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

from collections import deque
def solve(N, A):
    

    now = range(N)
    todo = N * (N - 1)
    for ans in range(1, N * N):
        later = set()
        for i in now:
            if A[i] and i not in later:
                j = A[i][0]
                if j not in later and A[j] and A[j][0] == i:
                    later.add(A[i].popleft())
                    later.add(A[j].popleft())
                    todo -= 2

        if not todo:
            return ans
        now = later
    return -1


N = rri()
A = []
for _ in xrange(N):
    row = rrm()
    A.append(deque(x-1 for x in row))
print solve(N, A)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    flag =[False] * (N+1)
    looplist = [i for i in range(1,N+1) if not(flag_max[i])]
    
    for i in looplist:
        if (flag[i]):continue
        tmp = A[i][idx[i]]
        if (flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                flag_max[tmp] = True
                cnt += 1
            if idx[i] == N-1:
                flag_max[i] = True
                cnt += 1
            flag[i] = True
            flag[tmp] = True
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            

    if day > 10000:
        print(N*(N-1)//2)
        sys.exit()
    
    
print(day)

Solution (Python):
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  

answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>3000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()

Solution (Python):
from collections import defaultdict, deque
outs = defaultdict(list)
ins = defaultdict(int)

def get_ab(h):
    return h // 10000, h % 10000

def get_hash(a, b):
    if a >= b:
        return 10000*a + b
    else:
        return 10000*b + a
v = []
N = int(input())
for i in range(N):
    nums = list(map(int, input().split()))
    pred = get_hash(i+1, nums[0])
    if pred not in v:
        v.append(pred)
    for j in range(len(nums)-1):
        now = get_hash(i+1, nums[j+1])
        outs[pred].append(now)
        ins[now] += 1
        pred = now

q = deque(v1 for v1 in v if ins[v1] == 0)
res = []
ans = 0
before = []
while q:
    v1 = q.popleft()
    res.append(v1)
    a, b = get_ab(v1)
    if (a in before) or (b in before):
        before = [a, b]
        ans += 1
    else:
        before.append(a)
        before.append(b)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
if len(res) < (N*(N-1)) // 2:
    print(-1)
else:
    print(ans+1)

Solution (Python):
import pprint

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

day = 0
check = set(range(n))

while True:
    end = 1
    game = set()
    for i in check:
        if a[i] != []:
            end = 0
            if a[a[i][0]-1] != []:
                if a[a[i][0]-1][0]-1 == i:
                    game.add(i)
                    game.add(a[i][0]-1)
    if end == 0:
        if game == set():
            print(-1)
            exit()
        else:
            for i in game:
                a[i].pop(0)
    else:
        print(day)
        exit()
    day += 1
    check = game

Solution (Python):
import sys
input = sys.stdin.readline
N=int(input())
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
ns = [i+1 for i in range(N)]
while True:
    vs = set()
    nn = False
    nns = []
    for i in ns:
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
            nns.append(i)
            nns.append(j)
    ns = nns
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)

Solution (Python):
import sys
from collections import defaultdict


def dfs(root, links):
    status = {}
    topological = []
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            q.append((v, 1))
            status[v] = 1
            d += 1
            for u in links[v]:
                if u in status:
                    if status[u] == 1:
                        return False
                else:
                    q.append((u, 0, d))
        else:
            v = node[0]
            status[v] = 2
            topological.append(v)
    topological.reverse()
    return topological


n = int(input())
links = defaultdict(set)
may_root = set()
lines = sys.stdin.readlines()
matches = []
for i in range(n):
    line = lines[i]
    aaa = list(map(int, line.split()))
    match_order = []
    for j in aaa:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * n + b
        match_order.append(key)
    matches.append(match_order)
    may_root.add(match_order[0])

for i in range(n):
    kkk = matches[i]
    prev = kkk[0]

    for key in kkk[1:]:
        links[prev].add(key)
        may_root.discard(key)
        prev = key

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

topological = dfs(may_root, links)
if topological == False:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))

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):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

N = int(input())

A = [0 for i in range(N)]
for i in range(N) :
    L = list(map(int,input().split()))
    for j in range(len(L)) :
        L[j] -= 1
    A[i] = deque(L)


ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**4 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)

Solution (Python):
import sys,time
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def solve():
    start = time.time()

    N = inp()
    AA = [inpl() for _ in range(N)]
    itrs = [0]*N
    ans = cnt = 0

    while True:
        next = set()
        for x,itr in enumerate(itrs):
            if itr < N-1:
                t = AA[x][itr] - 1
                if AA[t][itrs[t]]-1 == x:
                    next.add(x)

        for n in next:
            itrs[n] += 1
            if itrs[n] == N-1:
                cnt += 1

        if len(next) == 0:
            for x in itrs:
                if x != N-1:
                    return -1
            return ans

        now = time.time() - start
        if now > 1.6:
            return N*(N-1)//2

        ans += 1

if __name__ == '__main__':
    print(solve())

Solution (Python):
from collections import defaultdict
from collections import deque
N = int(input())

A = [list(map(int,input().split(' '))) for i in [0]*N]

dic = defaultdict(int)
ns = [0] * N

ls = range(1,N+1)
ans = 0
while(True):
	new_ls = set([])
	for i in ls:
		if ns[i-1] >= N-1:
			continue
		j = A[i-1][ns[i-1]]
		dic[(i*j,i+j)] += 1
		if dic[(i*j,i+j)] == 2:
			new_ls.add(i)
			new_ls.add(j)
	if not new_ls:
		break
	for ind in new_ls:
		ns[ind-1] += 1
	ls = new_ls
	ans += 1

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

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


from collections import deque

from copy import copy

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)
def main():
    N = II()
    a_mat = []
    for i in range(N):
        a_mat.append(deque(LI()))

    cnt = 0
    first_list = [a_list.popleft() for a_list in a_mat]
    nend = 0
    previous_match_list = list(range(N))
    while True:
        
        
        match_list = []
        for i in previous_match_list:
            a_no = first_list[i]
            a = a_no-1
            no = i+1
            
            if first_list[a] == no:
                match_list.append(i)

        dprint(first_list, match_list)

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

        previous_match_list = copy(match_list)

        
        for i in match_list:
            if len(a_mat[i]) == 0:
                first_list[i] = 0
                nend += 1 
            else:
                next_no = a_mat[i].popleft()
                next = next_no - 1
                first_list[i] = next_no
                previous_match_list.append(next)

        previous_match_list = list(set(previous_match_list))

        dprint(match_list, previous_match_list)
        dprint("")
        
        cnt += 1

        
        if nend == N:
            break


    print(cnt)


main()

Solution (Python):
N = int(input())
A = [list(map(int, input().split())) for n in range(N)]
P = [0] * N


def get_num(i):
    return A[i][P[i]] - 1


def update(mem, K):
    for i in mem:
        P[i] += 1
        if P[i] == N - 1:
            K.remove(i)


def f():
    K = {i for i in range(N)}
    L = {i for i in range(N)}
    mem = set()
    for t in range(N * (N - 1) // 2 + 1):
        if len(K) == 0:
            return t

        for i in L:
            if i in mem:
                continue

            j = get_num(i)
            if j in mem:
                continue

            if i == get_num(j):
                mem.add(i)
                mem.add(j)

        if len(mem) == 0:
            return -1
        update(mem, K)
        L = K & mem
        mem.clear()

    return -2

print(f())