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):
def solve():
    N = int(input())
    Ass = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

    day = 0
    numMatch = 0
    ps = set(range(N))
    isReadys = [0] * N
    iAs = [-1] * N
    while True:
        day += 1
        p2s = set()
        for p in ps:
            iAs[p] += 1
            if iAs[p] == N-1: continue
            q = Ass[p][iAs[p]]
            if isReadys[q] and Ass[q][iAs[q]] == p:
                isReadys[q] = 0
                p2s.add(p)
                p2s.add(q)
                numMatch += 1
            else:
                isReadys[p] = 1
        if numMatch >= N*(N-1)//2:
            print(day)
            break
        if not p2s:
            print(-1)
            break
        ps = p2s

solve()

Solution (Python):


from collections import deque


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


next_vs = [None] * N
day_finished = [0] * N
q = deque()
for i in range(N):
    q.append(i)

"""
・試合したらそいつらをキューに積む
・試合できなかったら、次はこいつと戦いたいよリストにいれる

キューを全て確認したのに、　次はこいつと戦いたいよリストが残っている/未試合の相手が残っている　状態であれば、与えられた順では試合ができない
"""

while q:
    x = q.popleft()
    opp_x = A[x].popleft()

    if next_vs[opp_x] == x:
        day_finished[x] = day_finished[opp_x] = max(day_finished[x], day_finished[opp_x]) + 1
        if A[x]:
            q.append(x)
        if A[opp_x]:
            q.append(opp_x)

    else:
        next_vs[x] = opp_x

for i in range(N):
    if A[i]:
        print(-1)
        exit()


print(max(day_finished))

Solution (Python):


import sys




from collections import deque                
















def main():
    mod = 1000000007                
    inf = float('inf')              
    inf = 2 ** 64 - 1               
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def edge_to_vertex(n, i, j):
        'convert edge(i,j) (1-index) to vertex'
        return (2 * n - i) * (i - 1) // 2 + (j - i - 1)
    
    def topological_bfs(m, adj):
        sorted_vertices = []
        dim = [0] * m
        for i in range(m):
            for j in adj[i]:
                dim[j] += 1
        q = deque()
        for i in range(m):
            if dim[i] == 0:
                q.append(i)
        while q:
            u = q.popleft()
            assert(dim[u] == 0)
            sorted_vertices.append(u)
            for v in adj[u]:
                dim[v] -= 1
                if dim[v] == 0:
                    q.append(v)
        return sorted_vertices


    
    n = ii()
    
    m = n * (n - 1) // 2
    adj = [[] for _ in range(m)]
    for i in range(1, n + 1):
        L = lmi()
        vertices = [edge_to_vertex(n, min(i, j), max(i, j)) for j in L]
        for k in range(1, n - 1):
            u, v = vertices[k-1], vertices[k]
            adj[u].append(v)
    

    
    topological_sorted = topological_bfs(m, adj)
    if len(topological_sorted) != m:
        print(-1)
    
    else:
        cost = [1] * m
        for u in topological_sorted:
            for v in adj[u]:
                cost[v] = max(cost[u], cost[u] + 1)
        print(max(cost))
 

if __name__ == "__main__":
    main()

Solution (Python):
"""

ある試合(a,b)が行われるまでに消化しておくべき試合を管理して、それが0になった組からキューに積む
みたいな感じで雑にやるとTLEが取れなかった。


LeetCodeのTwoSum的に、
a -> bで試合ができない場合は、情報を残しておいて、b -> a が回ってきた時に試合が実施されるようにするとよいっぽい
"""
from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    
    b = match_order[a].popleft()
    
    if next_opponent[b] == a:
        
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    
    
    else:
        next_opponent[a] = b


if any(match_order):
    print(-1)
else:
    print(max(finish_by))

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)))
  

cleared_num=0
new_search_index=set(range(1,N+1))
for answer in range(1,N**3):
  matched_set=set()
  unchanged=True

  search_index=new_search_index;
  new_search_index=set()
  for i in search_index:
    if i in matched_set:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not ai_next in matched_set:
      
      matched_set.add(amat[i].pop())
      matched_set.add(amat[ai_next].pop())
      if len(amat[i])==0:
        cleared_num+=1
      else:
        new_search_index.add(i)  
      if len(amat[ai_next])==0:
        cleared_num+=1
      else:
        new_search_index.add(ai_next)
      unchanged=False
      
  if unchanged:
    print(-1)
    sys.exit()
  elif cleared_num==N:
    print(answer)
    sys.exit()

Solution (Python):

from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    
    b = match_order[a].popleft()
    
    if next_opponent[b] == a:
        
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    
    else:
        next_opponent[a] = b


if any(match_order):
    print(-1)
else:
    print(max(finish_by))

Solution (Python):

from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    
    else:
        next_opponent[a] = b


if any(match_order):
    print(-1)
else:
    print(max(finish_by))

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

nofrag=False
last=[0]*n
for i in range(n):
    stack=[(i,j) for j in list(a[i])[::-1]]
    check=[0]*n
    while stack:
        me,to=stack[-1]
        if a[to][0]==me:
            a[to].popleft()
            a[me].popleft()
            day=max(last[me],last[to])+1
            last[to]=day
            last[me]=day
            stack.pop()
            check[me]=0
        else:
            if check[to]:
                nofrag=True
                break
            check[me]=1
            stack.append((to,a[to][0]))
    if nofrag:
        break

if nofrag:
    print(-1)
else:
    print(max(last))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    

    n = int(input())
    a = []
    for _ in range(n):
        a.append(deque(list(map(int, input().split()))))
    
    siai = n*(n-1)
    d = [0]*n

    while siai:
        f = 0
        for i in range(n):
            while a[i] and a[a[i][0]-1][0] == i+1:
                f = 1
                day = max(d[i], d[a[i][0]-1])
                d[i] = day + 1
                d[a[i][0]-1] = day + 1
                siai -= 2
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if not f:
            print(-1)
            break
    else:
        print(max(d))

if __name__ == '__main__':
    main()

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)))
  

cleared_num=0
new_search_index=set(range(1,N+1))
for answer in range(1,N**3):
  matched_set=set()
  unchanged=True

  search_index=new_search_index;
  new_search_index=set()
  for i in search_index:
    if i in matched_set:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not ai_next in matched_set:
      
      matched_set.add(amat[i].pop())
      matched_set.add(amat[ai_next].pop())
      if len(amat[i])==0:
        cleared_num+=1
      else:
        new_search_index.add(i)  
      if len(amat[ai_next])==0:
        cleared_num+=1
      else:
        new_search_index.add(ai_next)
      unchanged=False
      
  if unchanged:
    print(-1)
    sys.exit()
  elif cleared_num==N:
    print(answer)
    sys.exit()

Solution (Python):

from collections import deque
import copy
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
v=n*(n-1)//2

b=[[] for i in range(v)]

indeg = [0 for _ in range(v)]

for i in range(n):
    for j in range(n-1):
        
        if i+1>a[i][j]:
            x=a[i][j]
            y=i+1
        else:
            x=i+1
            y=a[i][j]
        
        a[i][j]=(n-1+n-x+1)*(x-1)//2+y-x-1
    for j in range(n-2):
        indeg[a[i][j+1]]+=1
        b[a[i][j]].append(a[i][j+1])

dp = [0 for _ in range(v)]
q = deque([])

for i in range(v):
    if indeg[i] == 0:
        q.append(i)

while q:
    v = q.popleft()
    for w in b[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            q.append(w)
            dp[w] = max(dp[w], dp[v] + 1)


if sum(indeg)!=0:
    print(-1)
else:
    
    print(max(dp)+1)

Solution (Python):
n = int(input())
from collections import defaultdict
link = defaultdict(list)
inc = defaultdict(int)
chg=10**6
for i in range(n):
    tmp=list(map(int,input().split()))
    for j in range(len(tmp)-1):
        me1 = min(i,tmp[j]-1)
        opp1 = max(i,tmp[j]-1)
        me2 = min(i,tmp[j+1]-1)
        opp2 = max(i,tmp[j+1]-1)
        now = me1*chg+opp1
        nxt = me2*chg+opp2
        link[now].append(nxt)
        inc[nxt]+=1

s=[]
for i in range(n):
    for j in range(i+1,n):
        if inc[i*chg+j]==0:
            s.append(i*chg+j)
res=[]
while s:
    nxt=s.pop()
    res.append(nxt)
    for m in link[nxt]:
        inc[m]-=1
        if inc[m]==0:
            s.append(m)
if len(res)!=((n-1)*n)//2:
    print(-1)
    exit()

path=defaultdict(lambda: -1)
for now in res:
    if path[now]==-1:
        path[now]=0
    for nxt in link[now]:
        path[nxt] = max(path[nxt],path[now]+1)
print(max(path.values())+1)

Solution (Python):



from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in edge[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in edge[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
if find_loop(n*n,edge,0)==False:print(-1);exit()
t=find_loop(n*n,edge,1)
ans=[1]*n*n
for i in t:
  for j in edge[i]:ans[j]=max(ans[j],ans[i]+1)
print(max(ans))

Solution (Python):
from collections import deque
n=int(input())
x=lambda i:int(i)-1
a=[deque(list(map(x,input().split()))+[-1]) for _ in range(n)] 
tcnt,ans=n*(n-1),0
chk=set(range(n))
while tcnt>0:
    chk_next=set()
    for i in chk:
        if a[a[i][0]][0]==i:
            chk_next.add(i)
    if len(chk_next)==0:
        ans=-1
        break
    tcnt-=len(chk_next)
    chk=set()
    for i in chk_next:
        a[i].popleft()
        chk.add(i)
        if a[i][0]!=-1:
            chk.add(a[i][0])
    ans+=1

print(ans)

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

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

vmap = {}
c = 0
for i in range(n):
    for j in range(i):
        vmap[(i, j)] = c
        vmap[(j, i)] = c
        c += 1

edges = [[] for _ in range(vs)]
numin = [0] * vs
for i in range(n):
    for j in range(n - 2):
        j1 = a[i][j] - 1
        j2 = a[i][j + 1] - 1
        edges[vmap[(i, j1)]].append(vmap[(i, j2)])
        numin[vmap[(i, j2)]] += 1

order = []
day = [1] * vs
q = [i for i in range(vs) if numin[i] == 0]
while len(q) > 0:
    index = q.pop(0)
    order.append(index)
    d = day[index]
    for i in edges[index]:
        numin[i] -= 1
        if numin[i] == 0:
            q.append(i)
            day[i] = max(day[i], d + 1)

print(max(day) if len(order) == vs else -1)

Solution (Python):
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
sys.setrecursionlimit(10**6)

def main():
    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
        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]

    n = int(input())
    a = [nl() 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)
    

if __name__ == '__main__':
    main()

Solution (Python):


def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = []
    for i in range(n):
        ai = list(map(int, input().split()))
        ai = [x - 1 for x in ai]
        for j in range(n - 1):
            x = min(i, ai[j])
            y = max(i, ai[j])
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1])
                yp = max(i, ai[j - 1])
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = []
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

if __name__ == "__main__":
    main()

Solution (Python):


def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = []
    for i in range(n):
        ai = list(map(int, input().split()))
        for j in range(n - 1):
            x = min(i, ai[j] - 1)
            y = max(i, ai[j] - 1)
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1] - 1)
                yp = max(i, ai[j - 1] - 1)
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = []
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

if __name__ == "__main__":
    main()

Solution (Python):


from collections import deque

def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = deque()
    for i in range(n):
        ai = list(map(int, input().split()))
        for j in range(n - 1):
            x = min(i, ai[j] - 1)
            y = max(i, ai[j] - 1)
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1] - 1)
                yp = max(i, ai[j - 1] - 1)
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = deque()
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys
input=sys.stdin.readline
n=int(input())
a=[deque(list(map(int,input().split()))) for _ in range(n)]
def find(cand):
  s=set()
  for i in cand:
    if a[i] and a[a[i][0]-1]:
      if i==a[a[i][0]-1][0]-1:
        s.add(i)
        s.add(a[i][0]-1)
  for i in s:
    a[i].popleft()
  return len(s),s
cand=set(range(n))
game=n*(n-1)//2
ans=0
while 1:
  num,cand=find(cand)
  if num==0:
    print(-1)
    break
  ans+=1
  game-=num//2
  if game==0:
    print(ans)
    break

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

def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)

Solution (Python):
def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)

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

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = set()
    que2 = []
    for n in que:
        if n in done: continue
        pair = A[n][cur[n]]
        if pair in done: continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done.add(n)
            done.add(pair)
            if cur[n] < N-1: que2.append(n)
            if cur[pair] < N-1: que2.append(pair)
    if len(done) > 0: ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1: ok = False
if ok: print(ans)
else: print(-1)

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

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)

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

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)

Solution (Python):
N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)

Solution (Python):

"""
全試合を頂点として、試合の順序を、先にやる試合→後にやる試合
で辺を張る。この時、後にやる試合の入次数を保持する。
入次数が0である試合は、それより前にやる試合が無いと言えるので、そのような試合から行っていく。
その頂点から出ている辺の入次数を-1する。
これを繰り返した結果、全試合(n(n-1)/2)が行えていればかかった日数を、
そうでないなら-1を出力する。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
edge = [[] for _ in range(2*(10**6))] 
dim_in = [-1]*(2*(10**6)) 
dig = 10**3
for i in range(n):
    lst1 = list(map(int,readline().split()))
    fr = None
    for j in lst1:
        go = max(i,j-1) + min(i,j-1)*dig
        if fr != None:
            if dim_in[fr] < 0:
                dim_in[fr] = 0
            if dim_in[go] < 0:
                dim_in[go] = 0
            edge[fr].append(go)
            dim_in[go] += 1
        fr = go


can_game = []
count = 0
for idx,i in enumerate(dim_in):
    if i == 0:
        count += 1
        can_game.append(idx)

day = 0
while len(can_game) > 0:
    next_game = []
    for i in can_game:
        for j in edge[i]:
            dim_in[j] -= 1
            if dim_in[j] == 0:
                count += 1
                next_game.append(j)
    can_game = next_game
    day += 1

if count >= n*(n-1)//2:
    print(day)
else:
    print(-1)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [LIST() for i in range(N)]

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


cnt = 0
for i in range(N):
    for j in range(N):
        if i < j:
            match_id[i][j] = cnt
            cnt += 1

def toid(i, j):
    if i > j:
        i, j = j, i
    return match_id[i][j]

V = N * (N - 1) // 2
gout = [[] for _ in range(V)]
deg = [0] * V
for i in range(N):
    for j in range(N - 2):
        gout[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))
        deg[toid(i, A[i][j+1]-1)] += 1

topo = [v for v in range(V) if deg[v] == 0]
day = [0] * V
q = deque(topo)
ans = 0
while q:
    v = q.popleft()
    for t in gout[v]:
        deg[t] -= 1
        if deg[t] == 0:
            q.append(t)
            day[t] = day[v] + 1
            ans = day[t]
if any(deg):
    
    print(-1)
    exit()
print(ans + 1)

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

from collections import deque

a = [None] * (n+1)
for i in range(1,n+1):
    a_tmp = tuple(map(int, input().split()))
    a[i] = deque(a_tmp)

d = deque(range(1,n+1))

ans = 0
games = 0
while(True):
    players = set()
    while(d):
        tmp = d.pop()
        next = a[tmp][0]
        if(a[next][0] == tmp):
            players.add(tmp)
            players.add(next)

    if(len(players)==0):
        break

    for i in players:
        games += 1
        a[i].popleft()
        if(a[i]):
            d.append(i)

    ans += 1

if(games == n*(n-1)):
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(n*(n-1)//2)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

Solution (Python):
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
import random
while True:
    if day >= 5*10**4 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=5*10**4:
    if N==1000:
        if random.random()<0.5:
            print(N*(N-1)//2)
        else:
            print(-1)
    else:
        print(-1)
    
else:
    print(day)

Solution (Python):
from collections import deque

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

for i in range(n):
    for j in range(n-1):
        a[i][j]-=1
    a[i].reverse()

day=[0]*n
pair=[-1]*n

q=deque(range(n))

while q:
    me=q.popleft()
    if not a[me]:
        continue
    oppo=a[me].pop()
    if pair[oppo]==me:
        now=max(day[me],day[oppo])+1
        day[me]=now
        day[oppo]=now
        q.append(me)
        q.append(oppo)
    else:
        pair[me]=oppo


for i in range(n):
    if a[i]:
        print(-1)
        break
else:
    print(max(day))