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
read = sys.stdin.readline

n = int(read())
V = 1001000

g = [[] for _ in range(V)]
deg = [0] * V
vlist = set()

for i in range(1, n + 1):
    a = list(map(int, read().rstrip().split()))
    for j in range(n - 2):
        v1 = min(i, a[j]) * 1001 + max(i, a[j])
        v2 = min(i, a[j + 1]) * 1001 + max(i, a[j + 1])
        vlist.add(v1)
        vlist.add(v2)
        g[v1].append(v2)
        deg[v2] += 1

d = [0] * V
check_cnt = 0
q = []
for v in vlist:
    if deg[v] == 0:
        q.append(v)

if len(q) == 0:
    print(-1)
    exit()

for v in q:
    check_cnt += 1
    for nv in g[v]:
        d[nv] = max(d[nv], d[v] + 1)
        deg[nv] -= 1
        if deg[nv] == 0:
            q.append(nv)
if check_cnt == n * (n - 1) // 2:
    print(max(d) + 1)
else:
    print(-1)

Solution (Python):
import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = input_int_list()[::-1]
    day = 0
    candi = set(range(1, n + 1))
    rest = (n * (n - 1)) // 2
    while rest:
        played = set()
        for a in candi:
            if d[a] and d[d[a][-1]][-1] and a == d[d[a][-1]][-1]:
                played.add(a)
                played.add(d[a][-1])

        if not played:
            break

        candi.clear()

        rest -= len(played) // 2
        for a in played:
            candi.add(a)
            d[a].pop()
            
            
        day += 1

    if rest == 0:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = input_int_list()[::-1]
    day = 0
    candi = set(range(1, n + 1))
    rest = (n * (n - 1)) // 2
    while rest:
        played = set()
        for a in candi:
            if d[a] and d[d[a][-1]][-1] and a == d[d[a][-1]][-1]:
                played.add(a)
                played.add(d[a][-1])

        if not played:
            break

        candi.clear()

        rest -= len(played) // 2
        for a in played:
            candi.add(a)
            d[a].pop()
            if d[a]:
                candi.add(d[a][-1])
        day += 1

    if rest == 0:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
def main(N, A):
    idx = [0] * N
    D = [[-1] * (N) for _ in range(N)]
    for j in range(N):
        D[j][0] = 0
    while True:
        f = True
        for i in range(N):
            if idx[i] >= N - 1: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                d = max(D[i][idx[i]], D[m][idx[m]])
                idx[i] += 1
                idx[m] += 1
                D[i][idx[i]] = d + 1
                D[m][idx[m]] = d + 1
                f = False
        if f: break
    ans = -1
    for i in range(N):
        ans = max(ans, D[i][N - 1])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, A)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
sys.setrecursionlimit(10**6)

n = ni()
def idx(u,v):
    return u*n+v
tree = [[] for i in range(n**2)]
go=[False]*n**2
back=[False]*n**2
memo = [1]*n**2 
start = []
for i in range(n):
    A1 = lma()
    pu,pv = i,A1[0]-1
    if pu>pv:pu,pv=pv,pu
    start.append(idx(pu,pv))
    for j in range(1,n-1):
        u,v = i,A1[j]-1
        if u>v:u,v=v,u
        tree[idx(pu,pv)].append(idx(u,v))
        pu,pv=u,v
        start.append(idx(pu,pv))

def dfs(s):
    go[s]=True
    for node in tree[s]:
        if not go[node]:
            memo[s] = max(dfs(node)+1,memo[s])
        else:
            if back[node]:
                memo[s] = max(memo[node]+1,memo[s])
            else:
                print(-1)
                exit()
    back[s]=True
    return memo[s]
ans = 0
for s in start:
    if not go[s]:
        ans = max(ans,dfs(s))
print(ans)

Solution (Python):
N = int(input())
A = [None] * N

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



playable = set(range(N))

day = 0
while True:
  next_playable = set() 
  done = set() 
  for player in playable:
    if player in done:
      continue
    if len(A[player]) == 0:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if len(A[rival]) == 0:
      continue
    if A[rival][-1] == player:
      done.add(player)
      done.add(rival)
      A[player].pop()
      A[rival].pop()
      
      next_playable.add(player)
      next_playable.add(rival)
  if len(next_playable) == 0:
    break
  playable = next_playable
  day += 1


ok = True
for i in range(len(A)):
  if len(A[i]) != 0:
    ok = False
    break
    
print((-1,day)[ok])

Solution (Python):
from collections import deque

def id(i, j):
    return v_id[min(i, j)][max(i, j)]

def TopologicalSort(graph, in_deg, N):
    sorted_v = []
    q = deque()

    for i in range(N):
        if in_deg[i] == 0:
            q.append(i)
    
    while q:
        v = q.popleft()
        for n_v in graph[v]:
            in_deg[n_v] -= 1
            if in_deg[n_v] == 0:
                q.append(n_v)
        
        sorted_v.append(v)

    if len(sorted_v) == N:
        return sorted_v
    else:
        return 0

N = int(input())
v_id = [[-1]*N for _ in range(N)]
graph = [[] for _ in range(N * (N - 1) // 2)]
in_deg = [0]*(N * (N - 1) // 2)

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

for i in range(N):
    a = list(map(lambda x: int(x) - 1, input().split()))
    for j in range(N - 2):
        graph[id(i, a[j])].append(id(i, a[j + 1]))
        in_deg[id(i, a[j + 1])] += 1

sorted_v = TopologicalSort(graph, in_deg, N * (N - 1) // 2)

if not sorted_v:
    print(-1)
else:
    dist = [0]*(N * (N - 1) // 2)

    for v in sorted_v:
        for n_v in graph[v]:
            dist[n_v] = max(dist[n_v], dist[v] + 1)
    
    print(max(dist) + 1)

Solution (Python):
from collections import defaultdict,deque
def hash(x,y):
    x,y =min(x,y),max(x,y)
    return x*(N+1)+y
s = set()
N = int(input())
edge = [[] for _ in range(N*N+N)]
ind = [0]*(N*N+N)
for i in range(1,N+1):
    A = list(map(int,input().split()))
    s.add(hash(i,A[0]))
    for j in range(N-2):
            edge[hash(i,A[j])].append(hash(i,A[j+1]))
            ind[hash(i,A[j+1])] += 1
d = deque()
nd = deque()
for hash in s:
    if ind[hash] == 0:
        d.append(hash)
ans = 0
finished = 0
while d:
    while d:
        hash = d.popleft()
        finished += 1
        for nhash in edge[hash]:
            ind[nhash] -= 1
            if ind[nhash] == 0:
                nd.append(nhash)
    d = nd
    nd = deque()
    ans += 1
if finished == N*(N-1)//2:
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import deque
n = int(input())
a = [list(map(int, input().split())) + [0] for i in range(n)]
for i in range(n):
    for j in range(n):
        a[i][j] -= 1
l = [0] * n
d = [0] * n
Q = deque(range(n))
while Q:
    p = Q.popleft()
    q = a[p][l[p]]
    if a[q][l[q]] == p:
        m = max(d[p], d[q]) + 1
        d[p] = m
        d[q] = m
        l[p] += 1
        l[q] += 1
        Q.append(p)
        Q.append(q)
for i in l:
    if i != n - 1:
        exit(print(-1))
print(max(d))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

es = [[[] for j in range(i)] for i in range(N)]
indeg = [[0]*i for i in range(N)]
for i,row in enumerate(A):
    for x,y in zip(row,row[1:]):
        x,y = x-1,y-1
        a0,b0 = (i,x) if i>x else (x,i)
        a1,b1 = (i,y) if i>y else (y,i)
        es[a0][b0].append((a1,b1))
        indeg[a1][b1] += 1

status = [[-1]*i for i in range(N)] 
def has_cycle(v):
    a0,b0 = v
    status[a0][b0] = 0
    for a1,b1 in es[a0][b0]:
        if status[a1][b1] == 0: return True
        if status[a1][b1] == -1:
            if has_cycle((a1,b1)): return True
    status[a0][b0] = 1
    return False

for i in range(N):
    for j in range(i):
        if status[i][j] != -1: continue
        if has_cycle((i,j)):
            print(-1)
            exit()

from collections import deque
q = deque()
for i in range(N):
    for j in range(i):
        if indeg[i][j] == 0:
            q.append((i,j,1))

ans = -1
while q:
    a0,b0,d = q.popleft()
    ans = max(ans,d)
    for a1,b1 in es[a0][b0]:
        indeg[a1][b1] -= 1
        if indeg[a1][b1] == 0:
            q.append((a1,b1,d+1))
print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=[]
    inf=10**6
    for _ in range(N):
        a=LI()+[inf]
        for j in range(N-1):
            a[j]-=1
        A.append(a)
        
        
    cur=[0]*N
    
    st=[]
    nxt=[]
    
    
    for i in range(N):
        for j in range(i+1,N):
            if A[i][0]==j and A[j][0]==i:
                cur[i]=1
                cur[j]=1
                st.append(i)
                st.append(j)
    day=1
    
    while st:
        used=[0]*N
        day+=1
        
        while st:
            i=st.pop()
            j=A[i][cur[i]]
            
            if used[i]==0 and used[j]==0:
                if A[j][cur[j]]==i:
                    cur[i]+=1
                    cur[j]+=1
                    nxt.append(i)
                    nxt.append(j)
                    used[i]=1
                    used[j]=1
               
        while nxt:
            a=nxt.pop()
            if cur[a]!=N-1:
                st.append(a)
        
    if sum(cur)==N*(N-1):
        print(day)
    else:
        print(-1)
        
            
        
        
    

main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = [[0]*(n) for i in range(n)]
ind = 0
from collections import defaultdict
ns = [[] for _ in range(N)]
for i in range(n):
    for j in range(i+1,n):
        index[i][j] = ind
        index[j][i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i][a[i][j]]
        v = index[i][a[i][j+1]]
        ns[u].append(v)

seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    
                    return True
        else:
            u = ~u
            done[u] = True
            
            val = 0
            for v in ns[u]:
                
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = [[0]*(n) for i in range(n)]
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i][j] = ind
        index[j][i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i][a[i][j]]
        v = index[i][a[i][j+1]]
        ns[u].append(v)

seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    
                    return True
        else:
            u = ~u
            done[u] = True
            
            val = 0
            for v in ns[u]:
                
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)

seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    
                    return True
        else:
            u = ~u
            done[u] = True
            
            val = 0
            for v in ns[u]:
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)

seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    
                    return True
        else:
            u = ~u
            done[u] = True
            
            val = 0
            for v in ns[u]:
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)

seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    
    seen[u] = True
    ans = 0
    for v in ns[u]:
        if done[v]:
            ans = max(ans, vals[v]+1)
            continue
        elif seen[v]:
            
            return 1
        else:
            pos = dfs(v)
            if pos>=0:
                return 1
            ans = max(ans, vals[v]+1)
    done[u] = True
    vals[u] = ans
    return -1
ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos>=0:
        print(-1)
        break
else:
    print(max(vals)+1)

Solution (Python):
from collections import deque
def f(s,t):
  if s>t:
    a=s
    s=t
    t=a
  return n*(s-1)-s*(s-1)//2+t-s-1
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
E=[[] for i in range(n*(n-1)//2)]
EE=[[] for i in range(n*(n-1)//2)]
B=[0]*(n*(n-1)//2)
for i in range(n):
  for j in range(n-2):
    u=f(i+1,A[i][j])
    v=f(i+1,A[i][j+1])
    EE[u].append(v)
    E[v].append(u)
    B[v]+=1
D=deque([])
V=[0]*(n*(n-1)//2)
F=[10**9]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
  if B[i]==0:
    D.append(i)
    V[i]=1
    F[i]=1
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(EE[x])):
    B[EE[x][i]]-=1
    if B[EE[x][i]]==0:
      D.append(EE[x][i])
      F[EE[x][i]]=F[x]+1
      V[EE[x][i]]=1
ans=-1
for i in range(n*(n-1)//2):
  if F[i]>ans:
    ans=F[i]
if ans==10**9:
  print(-1)
else:
  print(ans)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
    
q=deque()
P=[0]*M
for i in range(M):
  if len(F[i])==0:
    q.append((i,0))

r=[]
while q:
  v1,cnt=q.popleft()
  r.append((v1,cnt))
  for v2 in D[v1]:
    P[v2]+=1
    if P[v2]==len(F[v2]):
      q.append((v2,cnt+1))

if len(r)!=M:
  print(-1)
else:
  print(r[-1][-1]+1)

Solution (Python):
def main():
	from collections import deque
	n=int(input())
	battle=n*(n-1)//2
	lis=[[] for i in range(battle)]
	num=[-1]*(n**2)
	cnt=-1
	for x in range(n**2):
		if x//n<x%n:
			cnt+=1
			num[x]=cnt
	for i in range(n):
		a=list(map(int,input().split()))
		for j in range(n-2):
			x=a[j]-1
			y=a[j+1]-1
			px=num[min(i*n+x,x*n+i)]
			py=num[min(i*n+y,y*n+i)]
			lis[px].append(py)
	node_in=[0]*(battle)
	for i in range(battle):
		for x in lis[i]:
			node_in[x]+=1
	zero=deque([])
	days=[10**9]*(battle)
	for i in range(battle):
		if node_in[i]==0:
			zero.append(i)
			days[i]=1
	while zero:
		r=zero.popleft()
		for x in lis[r]:
			node_in[x]-=1
			if node_in[x]==0:
				zero.append(x)
				days[x]=days[r]+1
	if 10**9 in days:
		print(-1)
	else:
		print(max(days))
if __name__ == '__main__':
	main()

Solution (Python):
from collections import deque
 
N = int(input())
As = [deque([])]
for _ in range(N):
  As.append(deque(list(map(int, input().split()))))

cnt = 0
cset = set([i for i in range(1,N+1)])
while len(cset) > 0:
  cnt += 1
  fset = set()
  nex = set([])
  f = 1
  for i in cset:
    if i not in fset:
      if As[As[i][0]][0] == i and As[i][0] not in fset:
        vis = As[i].popleft()
        fset.add(vis)
        fset.add(As[vis].popleft())
        if len(As[i]) > 0:
          nex.add(i)
        if len(As[vis]) > 0:
          nex.add(vis)
        f = 0
  cset = nex
  if f == 1:
    print('-1')
    exit()
      
print(cnt)

Solution (Python):
from collections import deque
 
N = int(input())
As = [[]]
iset = [0]*(N+1)
for _ in range(N):
  As.append(list(map(int, input().split())))

cnt = 0
cset = set([i for i in range(1,N+1)])
while len(cset) > 0:
  cnt += 1
  fset = set()
  nex = set()
  f = 1
  for i in cset:
    if i not in fset:
      vis = As[i][iset[i]]
      if As[vis][iset[vis]] == i and vis not in fset:
        iset[i] += 1
        iset[vis] += 1
        fset.add(i)
        fset.add(vis)
        if iset[i] < N-1:
          nex.add(i)
        if iset[vis] < N-1:
          nex.add(vis)
        f = 0
  cset = nex
  if f == 1:
    print('-1')
    exit()
    
print(cnt)

Solution (Python):

min2 = lambda x,y: x if x < y else y

N = int(input())

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

q = set()
for i,l in enumerate(queues):
    if i < l[-1] and queues[l[-1]][-1] == i:
        q.add(i)

d = 0
while q:
    possible = set()
    for v in q:
        u = queues[v].pop()
        queues[u].pop()
        possible.add(v)
        possible.add(u)

    q.clear()
    for v in possible:
        try:
            u = queues[v][-1]
            if queues[u][-1] == v:
                q.add(min2(u,v))
        except IndexError:
            pass
    d += 1

print(-1 if any(l for l in queues) else d)

Solution (Python):
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    if not stacks[a]:
      return -1
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())

Solution (Python):
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    while not stacks[a]:
      now = (now+1)%N
      a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==2*N:
      return -1
  ans = max(lis)
  return ans
print(solve())

Solution (Python):
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    while not stacks[a]:
      now = (now+1)%N
      a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())

Solution (Python):
from collections import deque

N = int(input())
A = [ deque() for _ in range(N) ]

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

def check(i):
  if len(A[i])==0: return
  j = A[i][0]
  if len(A[j])==0: return

  if A[j][0] == i:
    if j<i: i,j = j,i
    q.add((i,j))

q = set()
for i in range(N):
  check(i)

ans = 0
while q:
  ans += 1

  prevq = q
  q = set()
  for p in prevq:
    i,j = p
    A[i].popleft()
    A[j].popleft()

  for p in prevq:
    i,j = p
    check(i)
    check(j)

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

print(ans)

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


def max2(x,y):
    return x if x > y else y

class DiGraph:
    def __init__(self, n, decrement=True, edges=[]):
        """
        incs[p]: 頂点 p に流入するリンク数
        """
        self.n = n
        self.decrement = decrement
        self.edges = [set() for _ in range(self.n)]
        self.incs = [0]*self.n
        for _from, _to in edges:
            self.add_edge(_from,_to)

    def add_edge(self, _from, _to):
        if self.decrement:
            _from -= 1
            _to -= 1
        self.edges[_from].add(_to)
        self.incs[_to] += 1

    def topological_sort_depth(self):
        """
        :return 各作業に１日かかると仮定したときに、最短で何日かかるかを返す
        """
        next_set = {p for p, inc in enumerate(self.incs) if inc == 0}
        res = []
        depth = [1]*self.n
        while next_set:
            p = next_set.pop()
            d = depth[p] + 1
            res.append(p+self.decrement)
            for q in self.edges[p]:
                self.incs[q] -= 1
                depth[q] = max2(d, depth[q])
                if self.incs[q] == 0:
                    next_set.add(q)
        if len(res) == self.n:
            return max(depth)
        else:
            return -1

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.DiGraph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()



N = int(input())
graph = DiGraph(N*N, decrement=True)
visited = set()
for i in range(1,N+1):
    p0 = -1
    for j in map(int, input().split()):
        p = i*N + j if j > i else j*N + i
        if p0 != -1:
            graph.add_edge(p0, p)
        p0 = p
print(graph.topological_sort_depth())

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = []
    match = defaultdict(lambda : -1)
    for i in range(N):
        a = deque(map(lambda x: int(x)-1, input().split()))
        match[i] = a[0]
        A.append(a)
    

    ans = 0
    players = deque(range(N))

    matched = True
    while matched and len(players) > 0:
        matched = False
        next_players = deque()
        next_match = defaultdict(lambda : -1)

        for i in players:
            if match[i] == -1:
                continue
            a = A[i]
            j = a[0]
            b = A[j]

            if match[j] == i:
                a.popleft()
                b.popleft()
                matched = True
                match[i] = -1
                match[j] = -1
                if len(a) > 0:
                    next_match[i] = a[0]
                    next_players.append(i)

                if len(b) > 0:
                    next_match[j] = b[0]
                    next_players.append(j)

        players = next_players
        match.update(next_match)
        ans += 1


        
    print(ans if matched and len(next_players)==0 else -1)








    

    ans = 0

    

    
   
main()

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = []
    match = defaultdict(lambda : -1)
    for i in range(N):
        a = deque(map(lambda x: int(x)-1, input().split()))
        match[i] = a[0]
        A.append(a)
    

    ans = 0
    players = deque(range(N))

    matched = True
    while matched and len(players) > 0:
        matched = False
        next_players = deque()
        next_match = defaultdict(lambda : -1)

        for i in players:
            if match[i] == -1:
                continue
            a = A[i]
            j = a[0]
            b = A[j]

            if match[j] == i and match[i] == j:
                a.popleft()
                b.popleft()
                matched = True
                match[i] = -1
                match[j] = -1
                if len(a) > 0:
                    next_match[i] = a[0]
                    next_players.append(i)

                if len(b) > 0:
                    next_match[j] = b[0]
                    next_players.append(j)


            else:
                next_match[i] = a[0]

        players = next_players
        match.update(next_match)
        ans += 1


        
    print(ans if matched and len(next_players)==0 else -1)








    

    ans = 0

    

    
   
main()