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 collections

def topological():
    """トポロジカルソート (有向グラフ) O(V+E)

    Vars:
        n (int):     頂点数
        edge (list): 辺に関するリスト (edge[i]: iを始点に持つ辺の終点のリスト)
    
    Returns:
        list/bool: トポロジカル順序 (閉路が存在する場合はFalse)
    """
    in_degree = [0] * n
    for i in range(n):
        for v in edge[i]:
            in_degree[v] += 1
    
    nodelist = collections.deque()
    for i in range(n):
        if in_degree[i] == 0:
            nodelist.append(i)
    
    res = []
    while nodelist:
        p = nodelist.popleft()
        for q in edge[p]:
            in_degree[q] -= 1
            depth[q] = max(depth[q], depth[p] + 1)
            if in_degree[q] == 0:
                nodelist.append(q)
        
        res.append(p)
    
    if len(res) == n:
        return res
    else:
        return False


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

n = m * (m - 1) // 2

num = 0
table = [[-1] * m for _ in range(m)]
for i in range(m):
    for j in range(i+1, m):
        table[i][j] = num
        table[j][i] = num
        num += 1

edge = [[] for _ in range(n)]
for i in range(m):
    for j in range(m-2):
        edge[table[i][a[i][j]-1]].append(table[i][a[i][j+1]-1])

depth = [0] * n
l = topological()

if not l:
    print(-1)
else:
    print(max(depth) + 1)

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

l = [i for i in range(n)]
pos = [0] * n
res = 0
cnt = 0
while True:
    res += 1
    flag = True
    tmp = l.copy()
    l = []
    used = [False] * n
    for v in tmp:
        if used[v] or pos[v] == n - 1:
            continue

        opp = a[v][pos[v]] - 1

        if used[opp] or pos[opp] == n - 1:
            continue

        if a[opp][pos[opp]] - 1 == v:
            pos[v] += 1
            pos[opp] += 1
            l.append(v)
            l.append(opp)
            used[v] = True
            used[opp] = True
            flag = False
            if pos[v] == n - 1:
                cnt += 1
            if pos[opp] == n - 1:
                cnt += 1

    if flag:
        print(-1)
        break

    if cnt == n:
        print(res)
        break

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(1000000)

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

    
    AR = [[]]
    for i in range(1,N+1):
        AR.append([0]*(N+1))
        for j in range(1,N):
            b = A[i][j]
            AR[i][b] = j

    edges =[[[] for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            jForI = AR[i][j]
            if jForI < N-1:
                nxForI = A[i][jForI+1]
                edges[i][j].append((min(i,nxForI),max(i,nxForI)))
            iForJ = AR[j][i]
            if iForJ < N-1:
                nxForJ = A[j][iForJ+1]
                edges[i][j].append((min(j,nxForJ),max(j,nxForJ)))
    del A
    del AR

    steps = {}
    def dfs(i,j):
        
        if (i,j) not in steps:
            steps[(i,j)] = 0
            res = 1
            for a,b in edges[i][j]:
                res = max(res,dfs(a,b)+1)
            steps[(i,j)] = res
        elif steps[(i,j)] == 0:
            print(-1)
            exit()
        return steps[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j))
    print(ans)
main()

Solution (Python):
import sys
import bisect
import math
import itertools
from collections import deque
import copy


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


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

    L = [[] for _ in range(N + 1)]

    for j in range(N):
        a = list(map(int, input().split()))
        L[j + 1] = deque(a)


    k =0

    current_revise =set(range(N+1))
    while k<50000000: 

        pre_revise =copy.copy(current_revise)
        current_revise =set()

        for i in pre_revise: 
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and i not in current_revise and can not in current_revise:
                L[i].popleft()
                L[can].popleft()

                current_revise.add(i)
                current_revise.add(can)
        k += 1

        if len(current_revise)==0:
            break


    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n = int(input())
graph = [[[] for _ in range(n+1)] for _ in range(n+1)]
indeg = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    a = tuple(map(int, input().split()))
    for j, v in enumerate(a):
        if j == n-2:
            continue
        tmp = (min(i, a[j+1]), max(i, a[j+1]))
        indeg[tmp[0]][tmp[1]] += 1
        if i < v:
            graph[i][v].append(tmp)
        else:
            graph[v][i].append(tmp)

cnt = n * (n-1)//2
q = deque([])
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if indeg[i][j] == 0:
            q.append((i, j, 1))
            cnt -= 1

ans = -1
while q:
    x, y, day = q.popleft()
    
    ans = max(ans, day)
    for p, r in graph[x][y]:
        if indeg[p][r] == 0:
            continue
        indeg[p][r] -= 1
        if indeg[p][r] == 0:
            q.append((p, r, day+1))
            cnt -= 1

if cnt == 0:
    print(ans)
else:
    print(-1)

Solution (Python):
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    
    reverseMemo = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if (i,j) not in stepMemo:
                ans = max(ans,dfs(i,j,set()))
    print(ans)
main()

Solution (Python):

from collections import Counter, defaultdict


import sys


readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = Counter()

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v] += 1
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = len(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                rg[v] -= 1
                if rg[v] == 0:
                    ns.append(v)
                    done += 1
        s = ns

    if done != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):

from collections import Counter, defaultdict


import sys

readline = sys.stdin.buffer.readline


INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = Counter()

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v] += 1
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = len(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                rg[v] -= 1
                if rg[v] == 0:
                    ns.append(v)
                    done += 1
        s = ns

    if done != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

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

MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
to = [[] for _ in range(MAXV)] 
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)] 
def toId(i,j): 
    if i > j: 
        i,j = j,i
    return id[i][j]

visited = [False]*MAXV
calculated = [False]*MAXV
dp = [1]*MAXV 

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

def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1 
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1 
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i,a[i][j]) 
        for j in range(n-2): 
            to[a[i][j+1]].append(a[i][j])
    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1') 
            return
        ans = max(ans, res)
    print(ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):

from collections import Counter, defaultdict


import sys

readline = sys.stdin.buffer.readline


INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = defaultdict(set)

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v].add(u)
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = len(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                
                
                rg[v].remove(u)
                if len(rg[v]) == 0:
                    ns.append(v)
                    done += 1
        s = ns

    if done != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

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

n=int(input())
a=[[0]*(n-1) for i in range(n)]
id=[[-1]*(n) for i in range(n)]
MAXV=n*(n-1)//2
to=[[]*(n) for i in range(MAXV)]
  
def toId(i,j):
  if (i>j):
    i,j=j,i
  return id[i][j]


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


def main():
  for i in range(n):
    a[i]=list(map(lambda x:int(x)-1,input().split()))
  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)
      exit(0)
    ans=max(ans, res)

  print(ans)
  
  
  
if __name__=='__main__':
  main()

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

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


cnt = [0] * N

recent = [0] * N


Q = deque(range(N))

while Q:
    
    p1 = Q.popleft()
    
    
    if cnt[p1] < N - 1:
        p2 = A[p1][cnt[p1]]
        
        if cnt[p2] < N - 1:
            
            if A[p2][cnt[p2]] == p1:
                
                day = max(recent[p1], recent[p2]) + 1
                recent[p1] = day
                recent[p2] = day
                cnt[p1] += 1
                cnt[p2] += 1
                Q.append(p1)
                Q.append(p2)

if min(cnt) != N - 1:
    print(-1)
else:
    print(max(recent))

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

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


cnt = [0] * N

recent = [0] * N


Q = deque(range(N))

while Q:
    
    p1 = Q.popleft()
    
    
    if cnt[p1] < N - 1:
        p2 = A[p1][cnt[p1]]
        
        if cnt[p2] < N - 1:
            
            if A[p2][cnt[p2]] == p1:
                
                day = max(recent[p1], recent[p2]) + 1
                recent[p1] = day
                recent[p2] = day
                cnt[p1] += 1
                cnt[p2] += 1
                Q.append(p1)
                Q.append(p2)

if min(cnt) != N - 1:
    print(-1)
else:
    print(max(recent))

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

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


cnt = [0] * N

recent = [0] * N


Q = deque(range(N))

while Q:
    
    p1 = Q.popleft()
    
    
    if cnt[p1] < N - 1:
        p2 = A[p1][cnt[p1]]
        
        if cnt[p2] < N - 1:
            
            if A[p2][cnt[p2]] == p1:
                
                day = max(recent[p1], recent[p2]) + 1
                recent[p1] = day
                recent[p2] = day
                cnt[p1] += 1
                cnt[p2] += 1
                Q.append(p1)
                Q.append(p2)

if min(cnt) != N - 1:
    print(-1)
else:
    print(max(recent))

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

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


cnt = [0] * N

recent = [0] * N


Q = deque(range(N))

while Q:
    
    p1 = Q.popleft()
    
    
    if cnt[p1] < N - 1:
        p2 = A[p1][cnt[p1]]
        
        if cnt[p2] < N - 1:
            
            if A[p2][cnt[p2]] == p1:
                
                day = max(recent[p1], recent[p2]) + 1
                recent[p1] = day
                recent[p2] = day
                cnt[p1] += 1
                cnt[p2] += 1
                Q.append(p1)
                Q.append(p2)

if min(cnt) != N - 1:
    print(-1)
else:
    print(max(recent))

Solution (Python):
from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  tmp=set()
  for p1,p in enumerate(a):
    p2=p[0]
    if p1==a[p2][0]:
      tmp.add(p1)
      tmp.add(p2)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  day=0
  while True:
    day+=1
    tmp=set()
    while q:
      p1=q.popleft()
      if len(a[p1])==0: continue;
      p2=a[p1][0]
      if p1==a[p2][0]:
        tmp.add(p1)
        tmp.add(p2)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    tmp=set()
    if len(q)==0: break;
    
  for i in a:
    if i:
      print(-1)
      exit()
  print(day)


if __name__=='__main__':
  main()

Solution (Python):
from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  q=deque([])
  tmp=set()
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      tmp.add(x)
      tmp.add(y)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  
  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    tmp=set()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if x == a[y][0]:
        tmp.add(x)
        tmp.add(y)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    if len(q)==0: break;

  for i in range(n):
    if len(a[i])!=0:
      print(-1)
      exit()
  print(day)


if __name__=='__main__':
  main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [[int(s) - 1 for s in reversed(readline().split())] for _ in range(N)]

    M = N * (N - 1) // 2
    games = 0
    players = set(range(N))

    for d in range(1, M + 1):
        players, players_prev = set(), players
        for i in players_prev:
            if not A[i] or i in players:
                continue
            j = A[i][-1]
            if j not in players and i == A[j][-1]:
                players.add(i)
                players.add(j)
                A[i].pop()
                A[j].pop()
                games += 1

        if games == M:
            print(d)
            break

        if not players:
            print(-1)
            break

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [[int(s) - 1 for s in reversed(readline().split())] for _ in range(N)]

    M = N * (N - 1) // 2
    games = 0
    players = set(range(N))

    for d in range(1, M + 1):
        players, players_prev = set(), players
        for i in players_prev:
            if not A[i] or i in players:
                continue
            j = A[i][-1]
            if j not in players and i == A[j][-1]:
                players.add(i)
                players.add(j)
                A[i].pop()
                A[j].pop()
                games += 1

        if games == M:
            print(d)
            break

        if not players:
            print(-1)
            break

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(100000)

input = sys.stdin.readline
N = int(input())


def get_id(i, j):
    if j < i:
        i, j = j, i
    return i * N + j


g = [[] for _ in range(N * N)]
S = []
for i in range(N):
    pre = None
    for j in map(int, input().split()):
        j -= 1
        id_ = get_id(i, j)
        if pre is None:
            S.append(id_)
        else:
            g[pre].append(id_)
        pre = id_


dp = [-1] * (N * N)
visited = [False] * (N * N)


def dfs(v):
    visited[v] = True
    if dp[v] != -1:
        return dp[v]
    for u in g[v]:
        if dp[u] != -1:
            res = dp[u]
        else:
            if visited[u]:
                raise ValueError('find loop!')
            res = dfs(u)
        dp[v] = max(dp[v], res + 1)
    if len(g[v]) == 0:
        dp[v] = 1
    return dp[v]


ans = 0
try:
    for s in S:
        ans = max(ans, dfs(s))
    print(ans)
except ValueError:
    print(-1)

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

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
    i2 = a[i - 1][0]
    if a[i2 - 1][0] == i:
        if i not in temp:
            queue.append([i, i2])
            temp.add(i)
            temp.add(i2)
if not queue:
    flag = False
while queue:
    temp = []
    while queue:
        test = queue.popleft()
        match += 1
        num1, num2 = test[0], test[1]
        nums[num1 - 1] += 1
        nums[num2 - 1] += 1
        temp.append(num1)
        temp.append(num2)
    flag2 = False
    temp2 = set()
    for i in temp:
        if nums[i - 1] <= n - 2:
            new_num = a[i - 1][nums[i - 1]]
            if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
                if i not in temp2:
                    queue.append([i, new_num])
                    flag2 = True
                    temp2.add(i)
                    temp2.add(new_num)
    if flag2 == False and match < n * (n - 1) // 2:
        flag = False
        break
    day += 1

if flag == True:
    print(day)
else:
    print(-1)

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

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
    i2 = a[i - 1][0]
    if a[i2 - 1][0] == i:
        if i not in temp:
            queue.append([i, i2])
            temp.add(i)
            temp.add(i2)
if not queue:
    flag = False
while queue:
    temp = []
    while queue:
        test = queue.popleft()
        match += 1
        num1, num2 = test[0], test[1]
        nums[num1 - 1] += 1
        nums[num2 - 1] += 1
        temp.append(num1)
        temp.append(num2)
    flag2 = False
    temp2 = set()
    for i in temp:
        if nums[i - 1] <= n - 2:
            new_num = a[i - 1][nums[i - 1]]
            if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
                if i not in temp2:
                    queue.append([i, new_num])
                    flag2 = True
                    temp2.add(i)
                    temp2.add(new_num)
    if flag2 == False and match < n * (n - 1) // 2:
        flag = False
        break
    day += 1

if flag == True:
    print(day)
else:
    print(-1)

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


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
    flag = True
    Done = [False] * N
    L = set()
    for i in Last:
        if len(A[i]) == 0:
            continue
        if Done[i]:
            continue
        x = A[i][-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            L.add(i)
            L.add(x)
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = L
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)

Solution (Python):
import sys



N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
    flag = True
    Done = [False] * N
    L = set()
    for i in Last:
        if len(A[i]) == 0:
            continue
        if Done[i]:
            continue
        x = A[i][-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            L.add(i)
            L.add(x)
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = L
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)

Solution (Python):
from sys import setrecursionlimit


def encode(i, j):
    if i < j:
        i, j = j, i
    return i * (i - 1) // 2 + j + 1


def dfs(v):
    if visited[v] == 2:
        return dp[v]
    visited[v] = 1
    for nv in g[v]:
        if visited[nv] == 1:
            print(-1)
            exit()
        dp[v] = max(dp[v], dfs(nv) + 1)
    visited[v] = 2
    return dp[v]


setrecursionlimit(10 ** 6)
N = int(input())
GAMES_CNT = N * (N - 1) // 2
g = [[] for _ in range(GAMES_CNT + 1)]
for i in range(N):
    orig = 0
    for j in map(lambda x: int(x) - 1, input().split()):
        dest = encode(i, j)
        g[orig].append(dest)
        orig = dest
dp = [0] * (GAMES_CNT + 1)
visited = [0] * (GAMES_CNT + 1)
print(dfs(0))

Solution (Python):
from sys import setrecursionlimit


def encode(i, j):
    if i < j:
        i, j = j, i
    return i * (i - 1) // 2 + j + 1


def dfs(v):
    if visited[v] == 2:
        return dp[v]
    visited[v] = 1
    for nv in g[v]:
        if visited[nv] == 1:
            print(-1)
            exit()
        dp[v] = max(dp[v], dfs(nv) + 1)
    visited[v] = 2
    return dp[v]


setrecursionlimit(10 ** 6)
N = int(input())
GAMES_CNT = N * (N - 1) // 2
g = [[] for _ in range(GAMES_CNT + 1)]
for i in range(N):
    orig = 0
    for j in map(lambda x: int(x) - 1, input().split()):
        dest = encode(i, j)
        g[orig].append(dest)
        orig = dest
dp = [0] * (GAMES_CNT + 1)
visited = [0] * (GAMES_CNT + 1)
print(dfs(0))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=day[now]
  if vis[now]:
    if res==-1:return -1
    else:return res
  res=1
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
v=0
si=[[0]*n for _ in range(n)]
for i in range(n):
  for j in range(i+1,n):
    si[i][j]=v
    v+=1
d=[[] for _ in range(v)]
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=si[i][a[0]-1]
  else:b=si[a[0]-1][i]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[si[i][j]]
      b=si[i][j]
    else:
      d[b]+=[si[j][i]]
      b=si[j][i]
vis=[0]*v
day=[-1]*v
ans=0
for i in range(v):
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)

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


def main():
    n = int(read())
    V = 1000000

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

    for i in range(n):
        a = list(map(lambda x: int(x) - 1, read().rstrip().split()))
        for j in range(n - 1):
            v1 = min(i, a[j]) * 1000 + max(i, a[j])
            vlist.add(v1)
            if j == n - 2:
                break
            v2 = min(i, a[j + 1]) * 1000 + max(i, a[j + 1])
            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)


if __name__ == '__main__':
    main()