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
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep="\n") if type(a)!=type("a") else print(a)
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    
    
    
    

    N = I()
    A = LLIN_(N)
    matches = set()
    id = [[-inf]*N for _ in range(N)]
    cnt = 0
    for i,a in enumerate(A):
        for j,rival in enumerate(a):
            if i < rival:
                id[i][rival] = cnt
                cnt += 1

    edge = defaultdict(list)

    def to_ID(i,j):
        if i>j:
            i,j = j,i
        return id[i][j]

    for i,a in enumerate(A):
        for j,rival in enumerate(a[:-1]):
            match_id = to_ID(i,rival)
            next_rival = a[j+1]
            next_match_id = to_ID(i,next_rival)
            edge[match_id].append(next_match_id)

    
    
    

    dp = {}
    visited = set()
    caluculated = set()
    def dfs(match):
        
        if match in visited:
            
            if match in caluculated:
                return dp[match]
            else:
                print(-1)
                exit()
        visited.add(match)
        dp[match] = 1
        for next_match in edge[match]:
            
            dp[match] = max(dfs(next_match)+1, dp[match])

        
        caluculated.add(match)
        return dp[match]

    ans = 0
    for match in range(cnt):
        res = dfs(match)
        
        ans = max(ans,res)
    print(ans)




    """
    N = I()
    A = []
    
    for _ in range(N):
        *a, = reversed(LI_())
        A.append(a)
    
    
    match = set()
    for i,a in enumerate(A):
        rival = a[-1]
        rival_of_rival = A[rival][-1]
        if rival_of_rival == i:
            match.add(i)
            match.add(rival)

    
    day = 0
    while match:
        day += 1
        last_match = set()
        last_match,match = match,last_match

        for i in last_match:
            A[i].pop()
        
        for i in last_match:
            if A[i]:
                rival = A[i][-1]
                rival_of_rival = A[rival][-1]
                if rival_of_rival == i:
                    match.add(i)
                    match.add(rival)
    for a in A:
        if a:
            print(-1)
            exit()

    print(day)"""

    """ O(N^3)
    N = I()
    A = LLIN_(N)
    indexes = [0] * N
    cnt = 0
    match = set()
    for i in range(N*N):
        update = False
        today_players = set()
        for k in range(N):
            index = indexes[k]
            if index >= N-1: 
                continue
            rival = A[k][index]
            if (k,rival) in match: 
                continue
            if (rival,k) in match :
                if not {k,rival} & today_players:
                    cnt += 1
                    update = True
                    match.remove((rival,k))
                    today_players.add(k)
                    today_players.add(rival)
                    indexes[k] += 1
                    indexes[rival] += 1
            else:
                match.add((k,rival))


            
        if not update:
            if cnt != (N*(N-1))//2:
                print(-1)
                exit()
            else:
                print(i)
                exit()"""

if __name__ == '__main__':
    main()

Solution (Python):
import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
maxmatch=n*(n-1)
day=0
q=[i for i in range(n)]
nq=[]
match=[0]*(n+1)
check=[0]*(n+1)
while q:
  day+=1
  for i in q:
    if match[i]==n-1 or check[i]==day:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[vs]!=day and check[i]!=day and a[vs][match[vs]]-1==i and a[i][match[i]]-1==vs:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=day
        check[vs]=day
        check[n]=day
        nq.append(i)
        nq.append(vs)
      
    if i==q[-1]:
      if check[n]!=day:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
  q=nq[:]
  nq=[]
        
print(day)

Solution (Python):

def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

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


NEXT = [ [] for i in range(N*N) ]

before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        
        NEXT[ match(i,A[i][j]) ].append( match(i,A[i][j+1]) )
        before[ match(i,A[i][j+1]) ] += 1
        
q  = []
q0 = []

for i in range(N):
    for j in range(i+1,N):
        if before[ match(i,j) ] == 0:
            q.append( match(i,j) )
            
day = 0

while True:
    day += 1
    for M in q:
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.append(m)
        NEXT[M] = []
    q = q0
    q0 = []
    
    
    if q == []:
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)

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

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: 
    
    
    if m in player_in_this_game:
      
      continue

    la = len(a[m])      
    if la: 
      teki = a[m][0] 
      jibun = m + 1 
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        
        continue

      if a[teki_idx][0] == jibun: 
        a[m].popleft() 
        a[teki_idx].popleft() 
        player_in_this_game.add(m) 
        player_in_this_game.add(teki_idx) 
        nokori_games -= 1 

  if nokori_games: 
    if not len(player_in_this_game): 
      print(-1)
      sys.exit()
  else: 
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()

Solution (Python):
import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
maxmatch=n*(n-1)
day=0
q=[i for i in range(n)]
nq=[]
match=[0]*(n+1)
check=[0]*(n+1)
while q:
  day+=1
  for i in q:
    if match[i]==n-1 or check[i]==day:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[vs]!=day and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=day
        check[vs]=day
        check[n]=day
        nq.append(i)
        nq.append(vs)
      
    if i==q[-1]:
      if check[n]!=day:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
  q=nq[:]
  nq=[]
        
print(day)

Solution (Python):
import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
maxmatch=n*(n-1)
day=0
q=[i for i in range(n)]
nq=[]
match=[0]*(n+1)
check=[0]*(n+1)
while q:
  day+=1
  for i in q:
    if match[i]==n-1 or check[i]==day:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[vs]!=day and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=day
        check[vs]=day
        check[n]=day
        nq.append(i)
        nq.append(vs)
      
    if i==q[-1]:
      if check[n]!=day:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
  q=nq[:]
  nq=[]
        
print(day)

Solution (Python):

from collections import deque
n = int(input())
matches = [list(a -1 for a in map(int,input().split()))
     for _ in range(n)]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n

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

Solution (Python):
import sys

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

canUse = set(range(N))

ans = 0
done = 0
while done < N:
    ans += 1
    canUseNew = set()
    
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            
            A[n].pop()
            if len(A[n]) == 0:
                done += 1
            A[first].pop()
            if len(A[first]) == 0:
                done += 1
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print(-1)
        sys.exit(0)
    canUse = canUseNew

print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep="\n") if type(a)!=type("a") else print(a)
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    """
    
    
    
    N = I()
    A = LLIN_(N)
    
    edge = defaultdict(list)
    matches = set()
    for i,a in enumerate(A):
        for j,rival in enumerate(a):
            p1,p2 = sorted([i,rival])
            match = (p1,p2)
            matches.add(match)
            if j != N-2:
                p1,p2 = sorted([i,a[j+1]])
                next_match = (p1,p2)
                edge[match].append(next_match)

    dp = {}
    visited = set()
    def dfs(match):
        
        if match in visited:
            
            if match in dp:
                return dp[match]
            else:
                print(-1)
                exit()
        visited.add(match)
        dp[match] = 0
        for next_match in edge[match]:
            dp[match] = max(dp[match], dfs(next_match)+1)

        
        return dp[match]

    ans = 0
    for match in matches:
        
        res = dfs(match) + 1
        ans = max(ans,res)
    print(ans)"""




    
    N = I()
    A = []
    
    for _ in range(N):
        *a, = reversed(LI_())
        A.append(a)
    
    
    match = set()
    for i,a in enumerate(A):
        rival = a[-1]
        rival_of_rival = A[rival][-1]
        if rival_of_rival == i:
            match.add(i)
            match.add(rival)

    
    day = 0
    while match:
        day += 1
        last_match = set()
        last_match,match = match,last_match

        for i in last_match:
            A[i].pop()
        
        for i in last_match:
            if A[i]:
                rival = A[i][-1]
                rival_of_rival = A[rival][-1]
                if rival_of_rival == i:
                    match.add(i)
                    match.add(rival)
    for a in A:
        if a:
            print(-1)
            exit()

    print(day)

    """ O(N^3)
    N = I()
    A = LLIN_(N)
    indexes = [0] * N
    cnt = 0
    match = set()
    for i in range(N*N):
        update = False
        today_players = set()
        for k in range(N):
            index = indexes[k]
            if index >= N-1: 
                continue
            rival = A[k][index]
            if (k,rival) in match: 
                continue
            if (rival,k) in match :
                if not {k,rival} & today_players:
                    cnt += 1
                    update = True
                    match.remove((rival,k))
                    today_players.add(k)
                    today_players.add(rival)
                    indexes[k] += 1
                    indexes[rival] += 1
            else:
                match.add((k,rival))


            
        if not update:
            if cnt != (N*(N-1))//2:
                print(-1)
                exit()
            else:
                print(i)
                exit()"""

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Solution (Python):
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    
    
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1


if cnt == total:
  print(days)
else:
  print(-1)

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

N=int(input())
L=[list(map(lambda x:int(x)-1,input().split())) for _ in range(N)]
q=deque(range(N))
days=[0]*N
pairs=[-1]*N
while q:
	a=q.popleft()
	if len(L[a])==0:continue
	b=L[a].pop(0)
	if pairs[b]==a:
		days[a]=days[b]=max(days[a],days[b])+1
		q.append(a);q.append(b)
	else:
		pairs[a]=b
print(max(days) if not any(L)else -1)

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

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


match_q = set([])
for i in range(N):
    a = A[i][0] 
    b = A[a][0] 
    if i == b:
        if i > a:
            i, a = a, i
        
        match_q.add((i, a))


def check(pair):
    i, j = pair
    if i > j:
        i, j = j, i
    if len(A[i]) == 0:
        return
    if len(A[j]) == 0:
        return
    
    A[i].popleft()
    A[j].popleft()

    for idx in [i, j]:
        if len(A[idx]) != 0:
            a = A[idx][0] 
            b = A[a][0] 
            if idx == b:
                if idx > a:
                    idx, a = a, idx
                match_q.add((idx, a))
    return


count = 0
while(len(match_q) != 0):
    count += 1
    old_q = match_q
    match_q = set([])
    for pair in old_q:
        check(pair)


if any(len(pair) != 0 for pair in A):
    print(-1)
else:
    print(count)

Solution (Python):
n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
  j = raw[i][cnt[i]]
  if raw[j][cnt[j]] == i and i < j:
    now.append([i,j])
ans = 0
while now:
  
  last = now
  now = []
  for x in last:
    i,j = x[0],x[1]
    cnt[i] += 1
    cnt[j] += 1
    if cnt[i] < n-1:
      k = raw[i][cnt[i]]
      if raw[k][cnt[k]] == i:
        now.append([i,k])
    if cnt[j] < n-1:
      k = raw[j][cnt[j]]
      if raw[k][cnt[k]] == j:
        now.append([j,k])
  ans += 1
if all( cnt[i] == n-1 for i in range(n) ):
  print(ans)
else:
  print(-1)

Solution (Python):
class DirectedGraph:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.is_asyclic = False
        self.max_path_len = None

    def topological_sort(self):
        indegree = [0] * self.n
        for i, vs in enumerate(self.adj):
            for dest in vs:
                indegree[dest] += 1
        zero_v = []
        for v, indeg in enumerate(indegree):
            if indeg == 0:
                zero_v.append(v)
        max_path_len = 1
        tp_sorted = []
        to_be_added = []
        while True:
            while zero_v:
                v = zero_v.pop()
                tp_sorted.append(v)
                for dest in self.adj[v]:
                    indegree[dest] -= 1
                    if indegree[dest] == 0:
                        to_be_added.append(dest)
            if len(to_be_added) > 0:
                zero_v += to_be_added
                to_be_added = []
                max_path_len += 1
            else:
                break
        if len(tp_sorted) == self.n:
            self.is_asyclic = True
            self.max_path_len = max_path_len
            return tp_sorted
        else:
            self.is_asyclic = False
            return None

if __name__ == "__main__":
    n = int(input())
    dic = {}
    itr = 0
    for i in range(n):
        for j in range(i+1, n):
            dic[i*n + j] = itr
            itr += 1
    edge = [[] for _ in range(n * (n-1) // 2)]
    for i in range(n):
        a = [int(item) - 1 for item in input().split()]
        for j1, j2 in zip(a, a[1:]):
            if i < j1:
                u = i * n + j1 
            else:
                u = j1 * n + i 
            if i < j2:
                v = i * n + j2 
            else:
                v = j2 * n + i 
            edge[dic[u]].append(dic[v])

    DG = DirectedGraph(edge)
    tps = DG.topological_sort()

    if DG.is_asyclic:
        print(DG.max_path_len)
    else:
        print(-1)

Solution (Python):

n = int(input())
a = []
for _ in range(n):
  a.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
  j = a[i][cnt[i]]
  if a[j][cnt[j]] == i and i < j:
    now.append([i,j])
ans = 0
while now:
  
  last = now
  now = []
  for x in last:
    i = x[0]
    j = x[1]
    cnt[i] += 1
    cnt[j] += 1
    if cnt[i] < n-1:
      k = a[i][cnt[i]]
      if a[k][cnt[k]] == i:
        now.append([i,k])
    if cnt[j] < n-1:
      k = a[j][cnt[j]]
      if a[k][cnt[k]] == j:
        now.append([j,k])
  ans += 1
if all(cnt[i] == n-1 for i in range(n)):
  print(ans)
else:
  print(-1)

Solution (Python):
import time
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()
    now=time.time()
    if (now-start)>1.6:
        print(m)
        exit()

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

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append((x,tmp))
        return

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = list(set(q))
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)

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

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append((x,tmp))
        return

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = list(set(q))
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)

Solution (Python):
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    
    
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1


if cnt == total:
  print(days)
else:
  print(-1)

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

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


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


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


if __name__ == "__main__":
    main()

Solution (Python):
def ts(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    Q = []
    for i in range(n)[::-1]:
        Q.append(-1)
        Q.append(i)
        Q.append(3)
        Q.append(i)
        Q.append(2)
        Q.append(i)
        Q.append(1)
    while Q:
        tp = Q.pop()
        if tp == 2:
            j = Q.pop()
            if done[j]: continue
            done[j] = 1
            L.append(j)
            checking[j] = 0
            continue
        elif tp == 3:
            j = Q.pop()
            k = Q.pop()
            D[j] = max(D[j], (D[k] + 1 if k >= 0 else 0))
        elif tp == 1:
            j = Q.pop()
            if done[j]: continue
            checking[j] = 1
            for k in E[j]:
                if checking[k]:
                    return []
                Q.append(k)
                Q.append(j)
                Q.append(3)
                Q.append(k)
                Q.append(2)
                Q.append(k)
                Q.append(1)
    return L[::-1]
def ca(i, j):
    return max(i, j) * (max(i, j)-1) // 2 + min(i, j)

N = int(input())
M = N * (N-1) // 2
X = [[] for i in range(M)]
for i in range(N):
    A = [int(a)-1 for a in input().split()]
    for j in range(N-2):
        X[ca(i, A[j])].append(ca(i, A[j+1]))
D = [0] * M
L = ts(X)
print(max(D) + 1 if L else -1)

Solution (Python):

from collections import deque

N = int(input())
A = [deque(a - 1 for a in map(int, input().split())) for _ in range(N)]
matchAvailablePlayers = deque(range(N))  
daysPassedWhenPlayedMostRecentMatch = [0] * N
desiredOpponentIdx = [-1] * N  

while matchAvailablePlayers:
    playerIdx = matchAvailablePlayers.popleft()
    matchesOrderForThisPlayer = A[playerIdx]  

    if not matchesOrderForThisPlayer:  
        continue

    opponentIdx = matchesOrderForThisPlayer.popleft()  

    if desiredOpponentIdx[opponentIdx] == playerIdx:  
        daysPassedWhenPlayedMostRecentMatch[playerIdx] = daysPassedWhenPlayedMostRecentMatch[opponentIdx] = max(daysPassedWhenPlayedMostRecentMatch[playerIdx], daysPassedWhenPlayedMostRecentMatch[opponentIdx]) + 1  
        matchAvailablePlayers.append(playerIdx)  
        matchAvailablePlayers.append(opponentIdx)
    else:  
        desiredOpponentIdx[playerIdx] = opponentIdx

if any(A):  
    print(-1)
else:
    print(max(daysPassedWhenPlayedMostRecentMatch))

Solution (Python):
import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]

q = deque(range(n))

depth = [0] * n
waiting = [-1] * n

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

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

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




def code(l, r, of):
  if l > r:
      l, r = r, l
  return of[l] + r - l - 1


of = [0] * (N + 1)
for i in range(N):
  of[i + 1] = of[i] + N - i - 1



g = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
  for j in range(N - 2):
      fcode = code(i, A[i][j] - 1, of)
      tcode = code(i, A[i][j + 1] - 1, of)
      g[fcode].append(tcode)

def sort_topologically(g):
  n = len(g)
  
  ec = [0] * n
  for i in range(n):
    for e in g[i]:
      ec[e] += 1
  
  
  ret = [0] * n
  q = 0
  for i in range(n):
    if ec[i] == 0:
      ret[q] = i
      q += 1
  
  
  
  
  
  
  p = 0
  
  while p < q:
    for to in g[ret[p]]:
      ec[to] -= 1
      if ec[to] == 0:
        ret[q] = to
        q += 1
    p += 1
  
  
  for i in range(n):
    if ec[i] > 0:
      return None
  return ret

od = sort_topologically(g)


if not od:
  print(-1)
else:
  
  dp = [1] * (N * (N - 1) // 2)
  for i in range(N * (N - 1) // 2):
    for e in g[od[i]]:
      dp[e] = max(dp[e], dp[od[i]] + 1)
  
  print(max(dp))

Solution (Python):
import collections

n = int(input())
a = [collections.deque(int(s) - 1 for s in input().split()) for _ in range(n)]

day = 0
players = set(range(n))
while any(v for v in a):
    nxt_players = set()
    for player in players:
        if len(a[player]) == 0 or player in nxt_players:
            continue
        
        other = a[player][0]
        if len(a[other]) == 0 or other in nxt_players:
            continue
        
        if player == a[other][0]:
            a[player].popleft()
            a[other].popleft()
            nxt_players.add(player)
            nxt_players.add(other)

    if nxt_players:
        day += 1
        players = nxt_players
    else:
        print(-1)
        exit()

print(day)

Solution (Python):
import sys
import time
def solve(matrix):
    N = len(matrix)
    
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        
        
        
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                
                
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                
        if time.time() - start > 1.5:
            print worst
            return
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)