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):
from sys import setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


def main():
    N = int(input())
    A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

    node_id_db = [[0] * N for _ in range(N)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1] * (N * (N - 1) // 2)
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(10 ** 6)
main()

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1

seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))

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

n = int(input())
U = n**2
G = [[] for _ in range(U)]
parent = [0]*U
for i in range(n):
  A = list(map(lambda x:int(x)-1, input().split()))
  for j in range(n-2):
    a = A[j]
    b = A[j+1]
    G[min(i, a)*n+max(i, a)].append(min(i, b)*n+max(i, b))
    parent[min(i, b)*n+max(i, b)] += 1

que = deque([(i*n+j, 1) for i in range(n-1) for j in range(i+1, n) if not parent[i*n+j]])
ans = 1
cnt = 0
while que:
  v, t = que.pop()
  ans = max(ans, t)
  cnt += 1
  for nv in G[v]:
    parent[nv] -= 1
    if not parent[nv]:
      que.appendleft((nv, t+1))
if cnt == n*(n-1)//2:
  print(ans)
else:
  print(-1)

Solution (Python):
from collections import defaultdict, deque
n=int(input())
v=n*(n-1)//2
es=[[] for _ in range(v)]

for i in range(n):
    *A,=map(int,input().split())
    for j in range(n-2):
        a=A[j]
        x,y=min(a-1,i),max(a-1,i)
        ith=((n-x)+(n-1))*x//2-1+(y-x)
        b=A[j+1]
        x,y=min(b-1,i),max(b-1,i)
        jth=((n-x)+(n-1))*x//2-1+(y-x)
        es[ith].append(jth)

outs = defaultdict(list)
ins = defaultdict(int)

for v1 in range(v):
    for v2 in es[v1]:
        outs[v1].append(v2)
        ins[v2] += 1

q = deque((v1,0) for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1,cnt = q.popleft()
    res.append((v1,cnt))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,cnt+1))
x=len(res)
if x!=v:
    print(-1)
else:
    print(res[-1][1]+1)

Solution (Python):
from collections import defaultdict, deque
n=int(input())
es=[]

for i in range(n):
    *A,=map(int,input().split())
    for j in range(n-2):
        a=A[j]
        x,y=min(a-1,i),max(a-1,i)
        ith=((n-x)+(n-1))*x//2-1+(y-x)
        b=A[j+1]
        x,y=min(b-1,i),max(b-1,i)
        jth=((n-x)+(n-1))*x//2-1+(y-x)
        es.append([ith, jth])

v=n*(n-1)//2
outs = defaultdict(list)
ins = defaultdict(int)
for i,j in es:
    outs[i].append(j)
    ins[j] += 1

q = deque((v1,0) for v1 in range(n*(n-1)//2) if ins[v1] == 0)
res = []
while q:
    v1,cnt = q.popleft()
    res.append((v1,cnt))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,cnt+1))

x=len(res)
if x!=n*(n-1)//2:
    print(-1)
else:
    print(res[-1][1]+1)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
import time


def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return


def B():
    a, b = LI()
    ans = 0
    b -= 1
    while b > 0:
        b -= a - 1
        ans += 1
    print(ans)

    return


def C():
    n = II()
    h = LI()
    i = 0
    ans = 0
    while i < n:
        down = i+1
        while down < n:
            if h[down - 1] >= h[down]:
                down += 1
            else:
                break
        ans = max(ans, down - i - 1)
        i = down
    print(ans)
    return


def D():
    n = II()
    print(n * (n - 1) // 2)
    return


def E():
    start = time.time()
    n = II()
    a = LIR_(n)
    ans = 0
    tern = [0] * n
    while 1:
        ans += 1
        f = True
        c = defaultdict(int)
        for i in range(n):
            if c[i]:
                continue
            if tern[i] == n - 1:
                continue
            rival = a[i][tern[i]]
            if c[rival]:
                continue
            if tern[rival] == n - 1:
                continue
            if a[rival][tern[rival]] == i:
                c[i] += 1
                c[rival] += 1
                tern[rival] += 1
                tern[i] += 1
                f = False
        if time.time() - start >= 1:
            print(n * (n - 1) // 2)
            return
        if f:
            if tern == [n - 1] * n:
                print(ans-1)
                return
            else:
                print(-1)
                return
    return


def F():
    return


if __name__ == '__main__':
    E()

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7


def dfs(u):
    if memo[u] == -2:
        print(-1)
        exit()
    if memo[u] != -1:
        return memo[u]
    memo[u] = -2
    res = 0
    for v in nodes[u]:
        res = max(res, dfs(v))
    memo[u] = res + 1
    return res + 1

N = INT()
NN = N * N
nodes = [set() for i in range(NN+1)]
for a in range(N):
    B = [b-1 for b in LIST()]
    for j in range(N-2):
        a1 = a2 = a
        b1 = B[j]
        b2 = B[j+1]
        if a1 > b1:
            a1, b1 = b1, a1
        if a2 > b2:
            a2, b2 = b2, a2
        nodes[a1*N+b1].add(a2*N+b2)
        if j == 0:
            nodes[NN].add(a1*N+b1)

memo = [-1] * (NN+1)
ans = dfs(NN) - 1
print(ans)

Solution (Python):

from collections import deque


def Topological_sorting(E):
    N = len(E)
    in_deg = [0]*N
    for i in range(N):        
        for to_ in E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  
        v = deq.popleft()
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != N:
        return False
    return ans


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

    
    MP = [[0]*N for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            MP[i][j] = cnt
            MP[j][i] = cnt
            cnt += 1

    out = [[] for _ in range(N*(N-1)//2)]
    
    for i in range(N):
        for j in range(N-2):
            out[MP[i][A[i][j]]].append(MP[i][A[i][j+1]])

    
    M = N*(N-1)//2

    order = Topological_sorting(out)
    if order is False:
        print(-1)
        return

    
    
    
    depth = [1]*M
    longest = 1
    for i in reversed(order):
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque

INF = float("inf")


def Topological_sorting(E):
    N = len(E)
    in_deg = [0]*N
    for i in range(N):        
        for to_ in E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  
        v = deq.popleft()
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != N:
        return False
    return ans


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

    def f(i, j):
        
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = [[] for _ in range(N*(N-1)//2)]
    
    for i in range(N):
        for j in range(N-2):
            out[f(i, A[i][j])].append(f(i, A[i][j+1]))

    
    M = (N*(N-1)//2)

    order = Topological_sorting(out)
    if order is False:
        print(-1)
        return

    
    
    depth = [-1]*M
    longest = -1
    for i in reversed(order):
        if depth[i] == -1:
            depth[i] = 1
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque
import heapq
INF = float("inf")


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

    
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        
        
        new_change = []
        ans += 1
        for c in change:
            
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                
                
                
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
  N=int(input())
  A=[deque(int(a)-1 for a in input().split()) for _ in range(N)]

  P,W=[0]*N,[-1]*N
  c=deque(range(N))

  while c:
    i=c.popleft()
    j=A[i].popleft()
    W[i]=j

    if W[j]==i:
      P[i]=P[j]=max(P[i],P[j])+1
      if A[i]:
        c.append(i)
      if A[j]:
        c.append(j)

  print(-1 if any(len(a) for a in A) else max(P))

main()

Solution (Python):
from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)

Solution (Python):




import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  

N = read_a_int()
A = read_matrix(N)
A = [mina(*a) for a in A]  


matchID = {}
cnt = 0
for i, j in combinations(range(N), r=2):
    matchID[i, j] = cnt
    matchID[j, i] = cnt  
    cnt += 1


for i, j in product(range(N), range(N - 1)):
    A[i][j] = matchID[i, A[i][j]]


graph = defaultdict(lambda: [])
indeg = [0] * cnt
for a in A:
    for i in range(N - 2):
        graph[a[i]].append(a[i + 1])
        indeg[a[i + 1]] += 1


day = [-1] * cnt  
is_visited = [False] * cnt
que = deque()  
for i in range(cnt):  
    if indeg[i] == 0:
        is_visited[i] = True
        que.append((i, 1))

while que:
    u, d = que.popleft()
    day[u] = d  
    for to in graph[u]:
        indeg[to] -= 1
        if indeg[to] or is_visited[to]:  
            continue
        que.append((to, d + 1))
        is_visited[to] = True

print(-1 if -1 in day else max(day))

Solution (Python):
from collections import defaultdict

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

adj = defaultdict(list)
in_deg = defaultdict(int)
for u, row in enumerate(a, 1):
    for v1, v2 in zip(row, row[1:]):
        uu1, vv1 = min(u, v1), max(u, v1)
        uu2, vv2 = min(u, v2), max(u, v2)
        match1 = uu1 + vv1 * 1000
        match2 = uu2 + vv2 * 1000
        adj[match1].append(match2)
        in_deg[match1]
        in_deg[match2] += 1

now = [key for key, val in in_deg.items() if val == 0]
day = 0
while now:
    day += 1
    nxt = []
    for u in now:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt.append(v)

    now = nxt

if max(in_deg.values()) > 0:
    day = -1

print(day)

Solution (Python):
from collections import deque
import sys


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


all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append((next_playerA,next_playerB))
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

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

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]


topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)


for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1)
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]        
        costs[direction_in_topological_sorted] = max(1+now_cost,costs[direction_in_topological_sorted])
        max_cost = max(max_cost,costs[direction_in_topological_sorted])
print(max_cost+1)

Solution (Python):





n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)



can={i for i in range(n)}
nxt=set()
cnt = 0
rem=n*(n-1)//2
while rem:
    cnt+=1
    for i in can:
        if i not in nxt and a[i]:
            p = a[i][-1]
            if p not in nxt:
                if a[p][-1]==i:
                    a[p].pop();a[i].pop()
                    nxt.add(i);nxt.add(p)
    rem-=len(nxt)//2

    can=nxt.copy()
    nxt=set()
    if not can:
        break
       
if rem:
    print(-1)
else:       
    print(cnt)

Solution (Python):
from collections import deque

N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [deque(list(map(lambda x :int(x)-1, input().split()))) for _ in range(N)]

day = 0
candidates = set(range(N))
while len(candidates)>0:
    day += 1
    nextday = set()
    checked = set()
    
    for candidate in candidates:
        if len(A[candidate]) == 0:
            continue
        if candidate in checked:
            continue
        opponent = A[candidate][0]
        if opponent in checked:
            continue
        if A[opponent][0] == candidate:
            A[opponent].popleft()
            A[candidate].popleft()
            nextday.add(candidate)
            nextday.add(opponent)
            checked.add(candidate)
            checked.add(opponent)
    candidates = nextday

for p in A:
    if len(p) > 0:
        print(-1)
        break
else:
    print(day-1)

Solution (Python):
import sys
from copy import deepcopy as copy

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [None]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
    
    index = [0]*n
    search = [int(x) for x in range(n)]
    ans = 0
    while True:
        already = set()
        judge = True
        sub = []
        for key in search:
            if index[key] == n-1:
                continue
            key2 = a[key][index[key]]
            if index[key2] == n-1:
                continue
            if key != a[key2][index[key2]]:
                continue
            if key in already or key2 in already:
                continue
            already.add(key)
            already.add(key2)
            index[key] += 1
            index[key2] += 1
            sub.append(key)
            sub.append(key2)
            judge = False
        if judge:
            break
        ans += 1
        search = copy(sub)
        
    for value in index:
        if value != n-1:
            print(-1)
            sys.exit()
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
g = [[] for _ in range(n ** 2)]
inv = [0] * (n ** 2)
for i in range(n):
    a = list(map(lambda x: int(x)-1, input().split()))
    for j in range(n - 2):
        p, q = min(i, a[j]), max(i, a[j])
        r, s = min(i, a[j + 1]), max(i, a[j + 1])
        g[p * n + q].append(r * n + s)
        inv[r * n + s] += 1
s = []
for i in range(n):
    for j in range(i + 1, n):
        if inv[i * n + j] == 0:
            s.append(i * n + j)
d = [0] * (n ** 2)
while s:
    p = s.pop()
    for node in g[p]:
        d[node] = max(d[node], d[p] + 1)
        inv[node] -= 1
        if inv[node] == 0:
            s.append(node)
for i in range(n):
    for j in range(i + 1, n):
        if inv[i * n + j] > 0:
            print(-1)
            exit(0)
print(max(d) + 1)

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

def main():
    N = int(input())
    memo = []
    base = 0
    for i in range(N-1):
        memo.append(base)
        base += N-i-1
    edge = [[] for _ in range((N*(N-1))//2)]
    IN = [0]*((N*(N-1))//2)
    
    for i in range(N):
        a = list(map(int,input().split()))
        b = []
        for j in a:
            j -= 1
            if i < j:
                b.append(memo[i]+j-i-1)
            else:
                b.append(memo[j]+i-j-1)
        for i in range(N-2):
            edge[b[i]].append(b[i+1])
            IN[b[i+1]] += 1

    def t_sort():
        que = deque([i for i,c in enumerate(IN) if c == 0])
        l = []
        while que:
            now = que.popleft()
            l.append(now)
            for fol in edge[now]:
                IN[fol] -= 1
                if IN[fol] == 0:
                    que.append(fol)
        if len(l) != (N*(N-1))//2:
            print(-1)
            exit()
        return l
    
    ts = t_sort()
    dp = [1]*((N*(N-1))//2)
    for now in ts:
        for fol in edge[now]:
            dp[fol] = max(dp[fol],dp[now]+1)
    
    print(max(dp))

if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    memo = []
    base = 0
    for i in range(N-1):
        memo.append(base)
        base += N-i-1
    edge = [[] for _ in range((N*(N-1))//2)]
    
    for i in range(N):
        a = list(map(int,input().split()))
        b = []
        for j in a:
            j -= 1
            if i < j:
                b.append(memo[i]+j-i-1)
            else:
                b.append(memo[j]+i-j-1)
        for i in range(N-2):
            edge[b[i+1]].append(b[i])

    go = [False]*((N*(N-1))//2)
    cul = [False]*((N*(N-1))//2)
    dp = [0]*((N*(N-1))//2)
    
    def dfs(v):
        if go[v]:
            if not cul[v]:
                return -1
            return dp[v]
        go[v] = True
        dp[v] = 1
        for u in edge[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v],ret+1)
        cul[v] = True
        return dp[v]
    
    ans = 0
    for i in range((N*(N-1))//2):
        ret = dfs(i)
        if ret == -1:
            print(-1)
            exit()
        ans = max(ans,ret)
        
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
previous=set()
for i in range(n):
  previous.add(i)
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in previous:
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  previous=set()
  for k in r:
    m[k].pop()
    previous.add(k)
    if m[k]:
      previous.add(m[k][-1]-1)
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

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

c = [0 for _ in range(N+1)]
p = []

for i in range(1, N+1):
    j = A[i][c[i]]
    if i==A[j][c[j]] and i<j:
        p.append((i,j))

ans = 0
while p:
    q = []
    for i,j in p:
        c[i] += 1
        c[j] += 1
        if c[i] < N-1:
            k = A[i][c[i]]
            if A[k][c[k]] == i:
                q.append((i,k))
        if c[j] < N-1:
            k = A[j][c[j]]
            if A[k][c[k]] == j:
                q.append((j,k))
    ans += 1
    p = q

ans = (ans if all(c[i]==N-1 for i in range(1, N+1)) else -1)
print(ans)

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


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

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].popleft()
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

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


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

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].popleft()
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

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


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

    

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].pop(0)
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Solution (Python):




import sys
readline = sys.stdin.readline

N = int(readline())
ALL = (N * (N - 1)) // 2 

from collections import deque
player = [None] * N
for i in range(N):
  player[i] = deque(list(map(lambda x:int(x) - 1,readline().split())))
  

q = set(range(N))

day = 0
while q:
  day += 1
  nextday = set()
  checked = set()
  for p in q:
    if p in checked:
      continue
    if len(player[p]) == 0:
      continue
    op = player[p][0] 
    if op in checked:
      continue
    if player[op][0] == p:
      
      player[p].popleft()
      player[op].popleft()
      checked.add(op)
      checked.add(p)
      if player[p]:
        nextday.add(p)
      if player[op]:
        nextday.add(op)
  q = nextday 

for p in player:
  if len(p) > 0:
    print(-1)
    break
else:
  print(day)