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

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] 


stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if done[game]: 
      print(-1)
      exit(0)
    done[game] = True
    for child in G[game]: 
      indegree[child] -= 1
      if indegree[child] == 0: 
        nextday.append(child)
  stack = nextday

if sum(done) != ((N * (N - 1)) // 2):
  print(-1)
  exit(0)
print(day)

Solution (Python):

import sys
input = sys.stdin.readline




from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        if len(self.nodes) == self.n:
            return self.nodes
        else:
            return []
    
    def get_depth(self):
        if len(self.depth) == self.n:
            return self.depth
        else:
            return []




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


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



G = [[] for _ in range((N*(N-1)//2))]

In = [0]*(N*(N-1)//2)

for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) == 0:
    print(-1)
else:
    print(max(depth) + 1)

Solution (Python):

import sys
input = sys.stdin.readline




from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        if len(self.nodes) == self.n:
            return self.nodes
        else:
            return []
    
    def get_depth(self):
        return self.depth




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


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



G = [[] for _ in range((N*(N-1)//2))]

In = [0]*(N*(N-1)//2)

for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) == 0:
    print(-1)
else:
    print(max(depth) + 1)

Solution (Python):

import sys
input = sys.stdin.readline




from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        return self.nodes
    
    def get_depth(self):
        return self.depth




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


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



G = [[] for _ in range((N*(N-1)//2))]

In = [0]*(N*(N-1)//2)

for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) != len(In):
    print(-1)
else:
    print(max(depth) + 1)

Solution (Python):
import sys
N = int(input())
T = []
for i in range(N):
    a = [i-1 for i in map(int,input().split())]
    T.append(a)

update = list(range(N))
ans = 0
L = [N-1]*N
while(True):
    K = []
    M = [0]*N
    for i in update:
        if L[i] != 0 and M[i] == 0:
            s = T[i][0]
            if L[s] != 0:
                if T[s][0] == i and M[s] == 0:
                    K.append(i)
                    K.append(s)
                    M[i] = 1
                    M[s] = 1
    for j in K:
        del T[j][0]
        L[j] -= 1
    if len(K) == 0:
        break
    ans += 1
    update = K

for i in range(N):
    if L[i] != 0:
        print(-1)
        sys.exit()
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    A[i] = [i-1 for i in map(int, input().split())]


def pair(x,y):
    if x<y:
        return (x,y)
    else:
        return (y,x)

to_index = dict()
to_pair = dict()
idx = 0
for i in range(N):
    for j in range(i+1,N):
        to_index[(i,j)] = idx
        to_pair[idx] = (i,j)
        idx += 1
    
MAX_N = idx

in_count = [0]*MAX_N
edge = [[] for _ in range(MAX_N)]

for i in range(N):
    for j in range(N-2):
        vnum = to_index[pair(i,A[i][j+1])]
        pvnum = to_index[pair(i, A[i][j])]
        edge[pvnum].append(vnum)

for i in range(MAX_N):
    for v in edge[i]:
        in_count[v] += 1

S = []
L = [] 
index = [0]*MAX_N 
ans = 0

for i in range(MAX_N):
    if in_count[i]==0: S.append(i)

while S:
    ans += 1
    new = []
    for _ in range(len(S)):
        v = S.pop()
        index[v] = len(L)
        L.append(v)
        for nv in edge[v]:
            in_count[nv] -= 1
            if in_count[nv]==0:
                new.append(nv)
    S = []
    for n in new:
        S.append(n)


if len(L) != MAX_N:
    print(-1)
    exit()
print(ans)

Solution (Python):
def opp(i):  
    return a[i][nex[i]]

from sys import stdin

readline=stdin.readline
n=int(readline())
m=n*(n-1)//2
a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

nex=[0]*n
before=set(range(n))
day=0
for day in range(1,m+1):
    now=set()
    while len(before)>0:
        p=before.pop()
        q=opp(p)
        if opp(q)==p and p not in now and q not in now:
            nex[p]+=1
            nex[q]+=1
            if nex[p]<n-1:
                now.add(p)
            if nex[q]<n-1:
                now.add(q)
            if q in before:
                before.remove(q)
    before=now
    if len(before)==0:
        break

if min(nex)==n-1:
    print(day)
else:
    print(-1)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = []
for _ in range(n):
    tmp = inpl()
    tmp = [x-1 for x in tmp] + [-1]
    
    a.append(deque(tmp))
md = [0] * n
nx = [-1] * n
for i in range(n):
    nx[i] = a[i].popleft()
q = deque(range(n))

while q:
    x = q.popleft()
    y = nx[x]
    if nx[y] == x:
        d = max(md[x], md[y])
        md[x] = md[y] = d+1
        nx[x] = a[x].popleft()
        nx[y] = a[y].popleft()
        q.append(x); q.append(y)
if any(x for x in a):
    print(-1)
else:
    print(max(md))

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

n = int(readline())
a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
q = list(range(n))
for cnt in range(1, n ** 2):
    qq = set()
    for x in q:
        if a[a[x][0]][0] == x:
            qq.add(x)
            qq.add(a[x][0])
    if qq:
        q = []
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        break
    if not q:
        print(cnt)
        break

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

n = int(readline())
a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
q = list(range(n))
cnt = 0
while q:
    cnt += 1
    qq = set()
    while q:
        x = q.pop()
        if a[a[x][0]][0] == x:
            qq.add(x)
            qq.add(a[x][0])
    if qq:
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        exit()
print(cnt)

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

n = int(readline())
a = [list(map(int, readline().split())) for _ in range(n)]
q = list(range(n))
for cnt in range(1, n ** 2 + 2):
    qq = set()
    while q:
        x = q.pop()
        if a[a[x][0] - 1][0] == x + 1:
            qq.add(x)
            qq.add(a[x][0] - 1)
    if qq:
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        break
    if not q:
        print(cnt)
        break

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = [None] * n
    for i in range(n):
        tmp = list(map(lambda x:int(x) - 1, input().split()))
        tmp.reverse()
        A[i] = tmp

    now = set()
    for i in range(n):
        j = A[i][-1]
        if i == A[j][-1]:
            now.add((min(i, j), max(i, j)))

    cnt = 0
    while now:
        next = set()
        for i, j in now:
            A[i].pop()
            A[j].pop()

        for i0, i1 in now:
            for i in (i0, i1):
                if not A[i]:
                    continue
                j = A[i][-1]
                if not A[j]:
                    continue
                if i == A[j][-1]:
                    next.add((min(i, j), max(i, j)))

        now = next
        cnt += 1

    if any(row for row in A):
        print(-1)
        return
    print(cnt)
resolve()

Solution (Python):
from collections import deque

n = int(input())
AA = [deque(list(map(int, input().split()))) for _ in range(n)]

graph = [[] for _ in range(n * n)]


def calc(i, j):
    if j > i:
        i, j = j, i
    return i * n + j


to = [0] * (n * n)
for i in range(n):
    for j in range(n - 2):
        u = calc(i, AA[i][j] - 1)
        v = calc(i, AA[i][j + 1] - 1)
        graph[u].append(v)
        to[v] += 1
start = []
for i in range(n * n):
    if to[i] == 0:
        start.append(i)


def topological_sort(edge_num, graph, start, to):
    topo = []
    cnt = 0
    stack = deque(start)
    while stack:
        v = stack.popleft()
        topo.append(v)
        cnt += 1
        for u in graph[v]:
            to[u] -= 1
            if to[u] == 0:
                stack.append(u)
    return topo, cnt


topo, cnt = topological_sort(n * n, graph, start, to)
if cnt != n * n:
    print(-1)
    exit()
day = [1] * (n * n)
for i in topo:
    for j in graph[i]:
        day[j] = day[i] + 1
print(max(day))

Solution (Python):
from collections import deque, defaultdict

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

D = [0] * N
Nx = [-1] * N
que = deque(range(N))

while que:
    i = que.popleft()
    j = A[i].popleft()
    Nx[i] = j

    if Nx[j] == i:
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print(max(D))
else:
    print(-1)

Solution (Python):
from collections import deque, defaultdict

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

D = [0] * N
canBattle = defaultdict(lambda: False)
que = deque(range(N))

while que:
    i = que.popleft()
    j = A[i].popleft()
    canBattle[(i, j)] = True

    if canBattle[(j, i)]:
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print(max(D))
else:
    print(-1)

Solution (Python):
from collections import deque, defaultdict

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

D = [0] * N
canBattle = defaultdict(lambda: False)
que = deque(range(N))

while que:
    i = que.popleft()
    j = A[i][0]
    canBattle[(i, j)] = True

    if canBattle[(j, i)]:
        A[i].popleft()
        A[j].popleft()
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print(max(D))
else:
    print(-1)

Solution (Python):
from collections import deque, defaultdict
from time import time
S = time()

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

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1.700:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)

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

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
serial = [[0]*N for _ in range(N)]
c = 0

for i in range(N):
    for j in range(i+1, N):
        serial[i][j] = c
        serial[j][i] = c
        c += 1

ins = [0]*c
outs = defaultdict(list)

for i in range(N):
    for j in range(N-2):
        s = serial[i][A[i][j]-1]
        t = serial[i][A[i][j+1]-1]
        ins[t] += 1
        outs[s].append(t)

q = deque([v for v in range(c) if ins[v]==0])
ans = 0

while True:
    nq = deque([])
    
    while q:
        v = q.popleft()
    
        for nv in outs[v]:
            ins[nv] -= 1
        
            if ins[nv]==0:
                nq.append(nv)

    ans += 1
    
    if len(nq)==0:
        break
    
    q = nq

if ins==[0]*c:
    print(ans)
else:
    print(-1)

Solution (Python):
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
calc=lambda u,v:min(u,v)*n+max(u,v)
edge=[[]for _ in range(n*n)]
for i in range(n):
  for j in range(1,n-1):
    u,v=calc(a[i][j-1]-1,i),calc(a[i][j]-1,i)
    edge[u].append(v)
from collections import deque
def find_loop(n,e):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  return t
d=find_loop(n*n,edge)
if len(d)!=n*n:exit(print(-1))
c=[1]*n*n
for i in d:
  for j in edge[i]:
    c[j]=c[i]+1
print(max(c))

Solution (Python):
from collections import deque
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
q = deque([])


def check(i, q):
  if len(A[i]) == 0:
    return
  j = A[i][-1]
  if len(A[j]) == 0:
    return
  if A[j][-1] == i:
    if i > j:
      i, j = j, i
    q.append((i, j))
  return 

for i in range(N):
  check(i, q)

day = 0
while q:
  day += 1
  q = set(sorted(q))
  prev = deque([])
  prev, q = q, prev
  for i, j in prev:
    A[i].pop(-1)
    A[j].pop(-1)
  for i, j in prev:
    check(i, q)
    check(j, q)
  
for i in range(N):
  if len(A[i]) != 0:
    print(-1)
    exit()

print(day)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    dq = [LI() for _ in range(N)]
    p = [0] * N
    cnt = 0
    c = [0] * N
    while cnt < N*(N-1)//2:
        ud = False
        for i in range(N):

            while p[i] < N-1:
                j = dq[i][p[i]]-1
                if dq[j][p[j]]-1 == i:
                    c[i] = c[j] = max(c[i],c[j]) + 1
                    p[i] += 1; p[j] += 1
                    cnt += 1
                    ud = True
                else:
                    break
        if ud:
            continue
        else:
            print(-1)
            return
    print(max(c))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools

import time

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
start = time.time()

N = int(readline())
A = [[int(x) - 1 for x in row.split()] for row in readlines()]


ids = [[0 for j in range(1005)] for i in range(1005)]
V = 0
for i in range(N):
    for j in range(i, N):
        ids[i][j] = V
        V += 1

MAXV = 1005 * 1005 // 2

visited = [False for i in range(MAXV)]
calculated = [False for i in range(MAXV)]
dp = [0 for i in range(MAXV)]

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            print(-1)
            exit()

        return dp[v]

    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        dp[v] = max(dp[v], dfs(u) + 1)

    calculated[v] = True
    return dp[v]

to = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(N - 1):
        a = i
        b = A[i][j]
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
    for j in range(N - 2):
        to[A[i][j + 1]].append(A[i][j])

ans = 0
for i in range(V):
    ans = max(ans, dfs(i))

print(ans)
elapsed_time = time.time() - start

Solution (Python):
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[-1] + [int(x) - 1 for x in row.split()][::-1] for row in readlines()]



def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1

answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x, cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)

Solution (Python):
"""
愚直に考えると、
・今XXX日目です
・試合できる人は試合をします。
・その日一回でも試合があれば次の日に進んで、なかったらおわり
をやる。愚直にやろうとすると、
・各選手について、次に試合する相手
・各選手がその日に試合したかどうか（１日に同じ人が複数回試合できないので）
・現在XXX日目
などの情報を持つ必要があり、また、その日の終わりに、各選手が試合したかどうかなどから、その日１回でも試合があったか判定をしたり、処理がめんどくさい。

ちょっとひねった方法で考えると、
・各選手が順番に、自分が次に試合するべき相手を一人指名して場にカードを出す。
・マッチングが成立する（a->b, b->a のカードが両方場に出される）と、その試合が実施され、試合した二人の選手について、次に試合したい選手がいれば、またカードを場に出す
・aとbが試合した時の最短の日にちは、max(aが最後に試合した日, bが最後に試合した日)+1 で表される
・各選手がカードを出したにも関わらず、マッチングが成立しない場合は、与えられた順番で試合ができない。

の形で管理すると、今日は何日で～とか、その日一回でも試合があったか～とかを管理しなくてよい。
"""

from collections import deque

N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]


q = deque()
for i in range(N):
    q.append(i)

next_game_with = [-1] * N
end_by = [0] * N
while q:
    a = q.popleft()
    opponent = A[a].popleft() - 1
    if next_game_with[opponent] == a:
        end_by[a] = end_by[opponent] = max(end_by[a], end_by[opponent]) + 1
        if A[a]:
            q.append(a)
        if A[opponent]:
            q.append(opponent)
    else:
        next_game_with[a] = opponent

finished = True
for i in range(N):
    if A[i]:
        finished = False
        break
if finished:
    print(max(end_by))
else:
    print(-1)

Solution (Python):
from collections import deque
def tsort():
    que=deque([i for i,c in enumerate(In) if c==0])
    l=[]
    while que:
        v=que.popleft()
        l.append(v)
        for nv in G[v]:
            In[nv]-=1
            if In[nv]==0:
                que.append(nv)
    if len(l)!=P:
        print(-1)
        exit()
    return l
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
In=[0]*P
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
        In[A[i][j+1]]+=1
srted=tsort()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

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

MAXN = 1005
MAXV = MAXN*(MAXN-1)//2

to = [[] for _ in range(MAXV)]

id = [[0 for _ in range(MAXN)] for _ in range(MAXN)]
def toID(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]


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


visited = [False for _ in range(MAXV)]
calculated = [False for _ in range(MAXV)] 
dp = [0 for _ in range(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]

ans = 0
ok = True
for i in range(V):
    res = dfs(i)
    if res == -1:
        ok = False
        break
    ans = max(ans, res)
if ok:
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(input())
edges = [[] for _ in range(n * 1001)]
memo = []
start = set()
for i in range(n):
    A = list(map(int, input().split()))
    for j in range(n-1):
        if i < A[j] - 1:
            A[j] = i * 1000 + A[j] - 1
        else:
            A[j] = (A[j] - 1) * 1000 + i

    for j in range(n-2):
        edges[A[j]].append(A[j+1])
    memo.append(A[0])

memo = Counter(memo).most_common()
for x, t in memo:
    if t > 1:
        start.add(x)


d = [-1 for _ in range(1001 * n)]
def dfs(v):
    d[v] = -2
    l = 0
    for to in edges[v]:
        if d[to] == -2:
            print(-1)
            exit()
        if d[to] == -1:
            dfs(to)
        l = max(l, d[to] + 1)
    d[v] = l

if len(start) == 0:
    print(-1)
    exit()
for i in start:
    dfs(i)
print(max(d) + 1)

Solution (Python):
import sys
sys.setrecursionlimit(4100000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
g = [[]*(n*(n-1)//2) for _ in range(n*(n-1)//2)]
chk = set([])
cnt = 0
d = {}
st = set([])

for i in range(n):
  a = [int(i) for i in readline().split()]
  for j in range(n-2):
    A,b = min(a[j],i+1),max(a[j],i+1)
    p,q = min(a[j+1],i+1),max(a[j+1],i+1)    
    if not b*1000+A in chk:
      d[b*1000+A] = cnt
      cnt += 1
      chk.add(b*1000+A)
    if not q*1000+p in chk:
      d[q*1000+p] = cnt
      cnt += 1
      chk.add(q*1000+p)
    g[d[b*1000+A]].append(d[q*1000+p])
    if j == 0:
      st.add(d[b*1000+A])



dp=[-1]*(n*(n-1)//2)

def dfs(v):
    
    dp[v]=-2
    length=0
    for nv in g[v]:
        if(dp[nv]==-2):
            print(-1)
            exit()
        if(dp[nv]==-1):
            dfs(nv)
        length=max(length,dp[nv]+1)
    dp[v]=length
            
st = list(st)
a = []
pp = 0
for i in st:dfs(i)
print(max(dp)+1)

Solution (Python):
from collections import deque

def solve():
    INF = float('inf')

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

    adjL = [[] for _ in range(N*N)]
    indegs = [0] * (N*N)
    for i, As in enumerate(Ass):
        x, y = i, As[0]
        if x > y:
            x, y = y, x
        vPrev = x*N + y
        for A in As[1:]:
            x, y = i, A
            if x > y:
                x, y = y, x
            v = x*N + y
            adjL[vPrev].append(v)
            indegs[v] += 1
            vPrev = v

    def getMaxCostsDAG(adjList, indegs, INF):
        numV = len(adjList)
        vs = [v for v in range(numV) if indegs[v] == 0]
        costs = [INF] * numV
        for v in vs:
            costs[v] = 0
        Q = deque(vs)
        while Q:
            vNow = Q.popleft()
            cost = costs[vNow]
            for v2 in adjList[vNow]:
                indegs[v2] -= 1
                if indegs[v2] == 0:
                    costs[v2] = cost + 1
                    Q.append(v2)
        return costs

    costs = getMaxCostsDAG(adjL, indegs, INF)

    ans = max(costs)
    if ans == INF:
        print(-1)
    else:
        print(ans+1)


solve()

Solution (Python):
def resolve():
    n = int(input())
    a = []

    for i in range(n):
        row = list(map(lambda x: int(x) - 1, input().split()))
        row.reverse()
        a.append(row)

    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if i == a[j][-1]:
            p = (i, j) if i < j else (j, i)
            q.add(p)

    for i in range(n):
        check(i)

    day = 0
    while len(q) > 0:
        day += 1
        prev_q, q = q, set()

        for p in prev_q:
            (i, j) = p
            a[i].pop()
            a[j].pop()

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

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

Solution (Python):
def solve():
    N = int(input())
    Ass = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

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

solve()