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.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Runtime Error

Solution code:
N = int(input())
import sys
input = sys.stdin.readline
A = [None] * N
for _ in range(N):
    a = list(map(int, input().split()))
    A[i] = a
    

def f():
    IDX = [0] * N
    day = 0
    end = 0
    while 1:
        NEXT_IDX = IDX[:]
        flag = True
        for player, i in enumerate(IDX):
            #print(player, i)
            if i > N-2:
                continue
            #print(player, i)
            enemy = A[player][i]

            if  A[enemy-1][IDX[enemy-1]] == player+1:
                NEXT_IDX[player] += 1
                flag = False
                #print(player, NEXT_IDX)
                if NEXT_IDX[player] == N-1:
                    end += 1
        if flag:
            #print(end, NEXT_IDX)
            return(-1)
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX[:]
print(f())

Submission status: Runtime Error

Solution code:
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if candidate == 0:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    count += 1

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:
N=int(input())

d={}
cnt=0
for i in range(1,N):
	for j in range(i+1, N+1):
		d[(i,j)]=cnt
		d[(j,i)]=cnt
		cnt+=1

graph=[[] for i in range(cnt)]

for i in range(1, N+1):
	t=list(map(int,input().split()))
	for j in range(N-2):
		graph[d[(i,t[j])]].append(d[(i,t[j+1])])


start=[0]*cnt
for g in graph:
	for i in g:
		start[i]=1

graph.append([i for i in range(len(start)) if start[i]==0])

seen=[False]*(cnt+1)
ne=[graph[-1]]

finished=[False]*(cnt+1)

t=False
depth=0
def dfs(x,p,d):
	global depth,t
	seen[x]=True
	depth=max(depth,d)
	for i in graph[x]:
		if i!=p:
			if seen[i]==True and not(finished[i]):
				t=True
				return
			else:
				dfs(i,x,d+1)
	finished[x]=True

if graph[cnt]==[]:
	print(-1)
else:
	dfs(cnt, -1, 0)
	if t==True:
		print(-1)
	else:
		print(depth)

Submission status: Runtime Error

Solution code:
N=int(input())

d={}
cnt=0
for i in range(1,N):
	for j in range(i+1, N+1):
		d[(i,j)]=cnt
		d[(j,i)]=cnt
		cnt+=1

graph=[[] for i in range(cnt)]

for i in range(1, N+1):
	t=list(map(int,input().split()))
	for j in range(N-2):
		graph[d[(i,t[j])]].append(d[(i,t[j+1])])


start=[0]*cnt
for g in graph:
	for i in g:
		start[i]=1

graph.append([i for i in range(len(start)) if start[i]==0])

seen=[False]*(cnt+1)
seen[-1]=True
ne=[graph[-1]]

t=False
depth=0
def dfs(x,p,d):
	global seen, graph,depth
	depth=max(depth,d)
	for i in graph[x]:
		if i!=p:
			if seen[i]==True:
				t=True
			else:
				seen[i]=True
				dfs(i,x,d+1)

if graph[cnt]==[]:
	print(-1)
else:
	dfs(cnt, -1, 0)
print(depth)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
# （１行読み込み→splitしてlist化→各要素に対して-1する）←を逆順にする（[::-1]）をN回繰り返す
A = [[x-1 for x in list(map(int, input().split()))][::-1] for i in range(N)]

def can_match(i, A, next_set):
    if not A[i]: # A[i]が空の場合
        return
    j = A[i][-1] # j = iさんの次の対戦相手

    if A[j][-1] == i: # jさんの次の対戦相手がiさんの場合（＝相思相愛の場合）
        if i < j: # 常に(小, 大)で格納する
            next_set.add((i,j))
        else: # 常に(小, 大)で格納する
            next_set.add((j,i))

# next_setの初期化
next_set = set() # setは集合を表す
for i in range(N):
    can_match(i, A, next_set)

# 試合できるか？何日かかるか？を判別する
day = 0
battle = 0
while next_set:
    day += 1
    current_set, next_set = next_set, set()
    for match in current_set:
        battle += 1
        del A[match[0]][-1]
        can_match(match[0], A, next_set)
        del A[1][-1]
        can_match(match[1], A, next_set)

if battle == N*(N-1)//2:
    print(day)
else:
    print(-1)

Submission status: Runtime Error

Solution code:


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

def can_match(i, A, next_set):
    if not A[i]:
        return
    j = A[i][-1]

    if A[j][-1] == i:
        if i < j:
            next_set.add((i,j))
        else:
            next_set.add((j,i))

next_set = set()
for i in range(N):
    can_match(i, A, next_set)

# 試合できるか？何日かかるか？を判別する
day = 0
battle = 0
while next_set:
    day += 1
    current_set, next_set = next_set, set()
    for match in current_set:
        battle += 1
        del A[match[0]][-1]
        can_match(match[0], A, next_set)
        del A[1][-1]
        can_match(match[1], A, next_set)

if battle == N*(N-1)//2:
    print(day)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
# （１行読み込み→splitしてlist化→各要素に対して-1する）←を逆順にする（[::-1]）をN回繰り返す
A = [[x-1 for x in list(map(int, input().split()))][::-1] for i in range(N)]

def can_match(i, A, next_set):
    if not A[i]: # A[i]が空の場合
        return
    j = A[i][-1] # j = iさんの次の対戦相手

    if A[j][-1] == i: # jさんの次の対戦相手がiさんの場合（＝相思相愛の場合）
        if i < j: # 常に(小, 大)で格納する
            next_set.add((i,j))
        else: # 常に(小, 大)で格納する
            next_set.add((j,i))

# next_setの初期化
next_set = set() # setは集合を表す
for i in range(N):
    can_match(i, A, next_set)

# 試合できるか？何日かかるか？を判別する
day = 0
battle = 0
while next_set:
    day += 1
    current_set, next_set = next_set, set()
    for match in current_set:
        battle += 1
        del A[match[0]][-1]
        can_match(match[0], A, next_set)
        del A[1][-1]
        can_match(match[1], A, next_set)

if battle == N*(N-1)//2:
    print(day)
else:
    print(-1)

Submission status: Runtime Error

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

def can_match(i, A, next_set):
  if not A[i]:
    return
  if A[A[i][-1]][-1] == i:
    if i < j:
      next_set.add((i,j))
    else:
      next_set.add((j,i))
      
next_set = set()
for i in range(N):
  can_match(i, A, next_set)
  
day = 0
battle = 0
while next_set:
  day += 1
  current_set, next_set = next_set, set()
  for match in current_set:
    battle += 1
    del A[match[0]][-1]
    can_match(match[0], A, next_set)
    del A[match[1]][-1]
    can_match(match[1], A, next_set)
    
if battle == N*(N-1)//2:
  print(day)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
int_sub = lambda x: int(x)-1
A = [list(map(int_sub,input().split())) for i in range(N)]
stack = [0 for _ in range(N)]
start = [0 for _ in range(N)]

query_nodes = {i for i in range(N)}
while sum(start) != int(N*(N-1)):
  skip_node = set()
  end = True
  for i in query_nodes:
    if i in skip_node:
      continue
    j = A[i][start[i]]
    if A[j][start[j]] == i and j not in skip_node:
      #print(stack,skip_node,i,start)
      skip_node |= {i,j}
      
      max_end = max(stack[i],stack[j])+1
      stack[i] = max_end
      stack[j] = max_end
      
      start[i] +=1
      start[j] +=1
      if start[i] == N:
        query_nodes -= {i}
      if start[j] == N:
        query_nodes -= {j}
      end = False
  if end:
    print(-1)
    quit()
print(max(stack))

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = deque()

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

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

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = Q.copy()
    qcheck = defaultdict(int)
    Q3 = []
    Q = deque()
    for q in Q2:
        key = str(q[0]) + "-" + str(q[1])
        if qcheck[key] == 0:
            A[q[0]].popleft()
            A[q[1]].popleft()
            qcheck[key] += 1
            Q3.append(q)
    for q in Q3:
        check(q[0])
        check(q[1])

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

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
orders = [] #試合順

for i in range(N):
    orders.append([int(j) for j in input().split()])

next_index = []
for i in range(N):
    next_index.append([0, False])
remains = []
for i in range(N):
    remains.append(i+1)
days = 0
is_possible = True
finished = 0

while len(remains) > 0:
    #1day process
    trued_i = []
    for i, e in enumerate(remains):
        #相手の相手が自分であり、1日の処理をまだしていない場合、対戦処理
        opponent = orders[e-1][next_index[e-1][0]]
        oppo_oppo = orders[opponent-1][next_index[opponent-1][0]]
        if oppo_oppo == e:
            if not (next_index[e-1][1] or next_index[opponent-1][1]):
                ni_e_0 = next_index[e-1][0]
                ni_o_0 = next_index[opponent-1][0]
                ni_e_0 += 1
                ni_o_0 += 1
                next_index.pop(e-1)
                next_index.insert(e-1,[ni_e_0, True])
                next_index.pop(opponent-1)
                next_index.insert(opponent-1, [ni_o_0, True])
                trued_i.append(e)
                trued_i.append(opponent)
                #カンストしたか
                if ni_e_0 >= N-1:
                    remains.remove(e)
                if ni_o_0 >= N-1:
                    remains.remove(opponent)
    days += 1
    #TrueをFalseに
    for i, e in enumerate(trued_i):
        ni_e_0 = next_index[e-1][0]
        next_index.pop(e-1)
        next_index.insert(e-1,ni_e_0)

    if days > N * (N-1) // 2:
        is_possible = False
        break

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

Submission status: Runtime Error

Solution code:
n = int(input())
INF = 10 ** 8
a = []

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

nex = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n-2):
        nex[i][a[i][j]] = a[i][j+1] 

memo = [{} for _ in range(n)]

def search(p,q,visited):
    if [p,q] in visited:
        return (-1) * INF
    visited.append([p,q])
    visited.append([q,p])
    if q in memo[p]:
        return memo[p][q]
    if a[p][-1] == q and a[q][-1] == p:
        ret = 1
    elif a[p][-1] == q:
        ret = search(nex[q][p],q,visited) + 1
    elif a[q][-1] == p:
        ret = search(p,nex[p][q],visited) + 1
    else:
        ret = max(search(p,nex[p][q],visited),search(nex[q][p],q,visited)) +1 
    memo[p][q] = ret
    memo[q][p] = ret
    return ret

can = []
det = 0
for i in range(n):
    sea = search(i,a[i][0],[])
    if sea < 0:
        det = -1
        break
    else:
        can.append(sea)
    #print(can)

#print(a)
if det == -1:
    print(-1)
else:
    print(max(can))

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

N = int(input())

A = []
for _ in range(N):
    A.append(deque(map(int,input().split())))
A = np.array(A)

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

q = []
a_tmp = []
flag = 0
day = 0
checker = set()
while match_num != 0:
    for i in range(N):
        if i in checker:
            continue
        if bool(A[i]) == False:
            continue
        a = A[i][0]-1
        if a in checker:
            continue
        if A[a][0]-1== i:
            A[i].popleft()
            A[a].popleft()
            checker.add(a)
            checker.add(i)
            match_num-=1
            flag += 1

    day +=1
    if flag == 0:
        print(-1)       
        exit()

    checker = set()
    flag = 0

print(day)

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep="\n") if type(a)!=type("a") else print(a)
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    """
    #この試合はこの試合のあとでないといけない、という条件がいくつもあるので
    #クリティカルパスを求めるイメージ(トポロジカルソート)
    #もしDAGでなければ無理なので-1
    N = I()
    A = LLIN_(N)
    #M = 0 #試合数
    edge = defaultdict(list)
    matches = set()
    for i,a in enumerate(A):
        for j,rival in enumerate(a):
            p1,p2 = sorted([i,rival])
            match = (p1,p2)
            matches.add(match)
            if j != N-2:
                p1,p2 = sorted([i,a[j+1]])
                next_match = (p1,p2)
                edge[match].append(next_match)

    dp = {}
    visited = set()
    def dfs(match):
        #print("dfs",match,visited,sep="\n")
        if match in visited:
            #print(match,dp)
            if match in dp:
                return dp[match]
            else:
                print(-1)
                exit()
        visited.add(match)
        dp[match] = 0
        for next_match in edge[match]:
            dp[match] = max(dp[match], dfs(next_match)+1)

        #print(match,dp[match])
        return dp[match]

    ans = 0
    for match in matches:
        #print(match)
        res = dfs(match) + 1
        ans = max(ans,res)
    print(ans)"""




    #O(試合数)
    N = I()
    A = []
    #消化した試合は削除していく
    for _ in range(N):
        *a, = reversed(LI_())
        A.append(a)
    #pprint("A",A)
    
    match = set()
    for i,a in enumerate(A):
        rival = a[-1]
        rival_of_rival = A[rival][-1]
        if rival_of_rival == i:
            match.add(i)
            match.add(rival)

    
    day = 0
    while match:
        day += 1
        last_match = set()
        last_match,match = match,last_match

        for i in last_match:
            A[i].pop()
        
        for i in last_match:
            if A[i]:
                rival = A[i][-1]
                rival_of_rival = A[rival][-1]
                if rival_of_rival == i:
                    match.add(i)
                    match.add(rival)
    for a in A:
        if a:
            raise Exception
            print(-1)
            exit()

    print(day)

    """ O(N^3)
    N = I()
    A = LLIN_(N)
    indexes = [0] * N
    cnt = 0
    match = set()
    for i in range(N*N):
        update = False
        today_players = set()
        for k in range(N):
            index = indexes[k]
            if index >= N-1: #全試合done
                continue
            rival = A[k][index]
            if (k,rival) in match: #前回の希望相手との試合がまだ
                continue
            if (rival,k) in match :
                if not {k,rival} & today_players:
                    cnt += 1
                    update = True
                    match.remove((rival,k))
                    today_players.add(k)
                    today_players.add(rival)
                    indexes[k] += 1
                    indexes[rival] += 1
            else:
                match.add((k,rival))


            
        if not update:
            if cnt != (N*(N-1))//2:
                print(-1)
                exit()
            else:
                print(i)
                exit()"""

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
maxmatch=n*(n-1)
day=0
q=[i for i in range(n)]
nq=[]
match=[0]*(n+1)
check=[0]*(n+1)
while q:
  day+=1
  for i in q:
    if match[i]=n-1 or check[i]==day:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=day
        check[vs]=day
        check[n]=day
        nq.append(i)
        nq.append(vs)
      
    if i==q[-1]:
      if check[n]!=day:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
  q=nq[:]
        
print(day)

Submission status: Runtime Error

Solution code:
#E
from collections import deque
n = int(input())
matches = [list(a -1 for a in map(int,input().split()))
     for _ in range(N)]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    ma = matches[a]
    if not ma:
        continue
    # gyaku kara kanngaeteru
    b = ma.pop()
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a],depth[b]) +1
        q.append(a)
        q.append(b)
    else:
        waiting[a] = b
if any(matches):
    print(-1)
else:
    print(max(depth))

Submission status: Runtime Error

Solution code:
from collections import deque

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

def d(i,loop):
    if len(A[i])>0:
        j=A[i][0]-1
        if i==A[j][0]-1:
            A[i].popleft()
            A[j].popleft()
            if i in memo or j in memo:
                ans.append(1)
                memo.clear()
                memo.append(i)
                memo.append(j)

            else:
                memo.append(i)
                memo.append(j)
            return
        
        else:
            if loop<=N:
                loop+=1
                return d(j,loop)
            else:
                return
    
    elif loop==N-1:
        return 
    else:
        loop+=1
        return d(i+1,loop)
      
memo=[i for i in range(N)]
ans=[]
    
for ii in range(N*(N-1)//2):
    d(0,0)

check=0
for a in A:
    check+=len(a)
if check==0:
    print(sum(ans))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
import copy
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

day=0

match=[0 for i in range(n)]
jyunban=[i for i in range(n)]

while True:
  jyunban_n=[]
  day+=1
  check=[True for i in range(n)]
  for i in jyunban:
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
        jyunban_n.push(i)
        jyunban_n.push(vs)
      
    if i==jyunban[-1]:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and max(match)==n-1:
    break
  jyunban=copy.copy(jyunban_n)
        
print(day)

Submission status: Runtime Error

Solution code:
def func(x, y):
    if x > y:
        return func(y, x)
    return (x, y)

N = int(input())
A = [None]
A += [[0] + list(map(int, input().split())) for _ in range(N)]
v = [[[] for _ in range(N+1)] for _ in range(N+1)]
cnt = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N):
        if j == 1:
            continue
        pre = func(i, A[i][j-1])
        to = func(i, A[i][j])
        v[pre[0]][pre[1]].append(to)
        cnt[to[0]][to[1]] += 1

vis = [[0]*(N+1) for _ in range(N+1)]

def dfs(x, y):
    ok = True
    vis[x][y] = -1
    for s, t in v[x][y]:
        if vis[s][t] == 0:
            ok = ok and dfs(s, t)
        elif vis[s][t] == -1:
            return False
    vis[x][y] = 1
    return ok

for i in range(1, N+1):
    for j in range(1, N):
        if not dfs(i, j):
            print(-1)
            exit()

vis2 = [[0]*(N+1) for _ in range(N+1)]
stack = []

def dfs2(x, y):
    vis2[x][y] = 1
    for s, t in v[x][y]:
        if vis2[s][t] == 0:
            dfs2(s, t)
    stack.append((x, y))

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

dp = [[0]*(N+1) for _ in range(N+1)]
while stack:
    x, y = stack.pop()
    for s, t in v[x][y]:
        dp[s][t] = max(dp[s][t], dp[x][y] + 1)

ans = 0
for i in range(1, N+1):
    ans = max(ans, max(dp[i]))

print(ans + 1)

Submission status: Runtime Error

Solution code:
def func(x, y):
    if x > y:
        return func(y, x)
    return (x, y)

N = int(input())
A = [None]
A += [[0] + list(map(int, input().split())) for _ in range(N)]
v = [[[] for _ in range(N+1)] for _ in range(N+1)]
cnt = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N):
        if j == 1:
            continue
        pre = func(i, A[i][j-1])
        to = func(i, A[i][j])
        v[pre[0]][pre[1]].append(to)
        cnt[to[0]][to[1]] += 1

vis = [[0]*(N+1) for _ in range(N+1)]

def dfs(x, y):
    ok = True
    vis[x][y] = -1
    for s, t in v[x][y]:
        if vis[s][t] == 0:
            ok &= dfs(s, t)
        elif vis[s][t] == -1:
            return False
    vis[x][y] = 1
    return ok

for i in range(1, N+1):
    for j in range(1, N):
        if not dfs(i, j):
            print(-1)
            exit()

vis = [[0]*(N+1) for _ in range(N+1)]
stack = []

def dfs2(x, y):
    vis[x][y] = 1
    for s, t in v[x][y]:
        if vis[s][t] == 0:
            dfs2(s, t)
    stack.append((x, y))

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

dp = [[0]*(N+1) for _ in range(N+1)]
while stack:
    x, y = stack.pop()
    for s, t in v[x][y]:
        dp[s][t] = max(dp[s][t], dp[x][y] + 1)

ans = 0
for i in range(1, N+1):
    ans = max(ans, max(dp[i]))

print(ans + 1)

Submission status: Runtime Error

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	ggl=lambda : list(map(int, input().split()))
	aal=[ggl() for _ in range(n)]
	
	match_list=[al[0] for al in aal]
	finised_num=[0]*n
	last_match_day=[0]*n
	
	ttn=0
	
	dd=0
	while ttn < n*(n-1):
		dd+=1
		pttn = ttn
		
		for i, nm in enumerate(match_list):
			if nm == -1:
				ml_next[i]=match_list[i]
			elif last_match_day[i]==d:
				pass
			elif match_list[nm-1]==i+1:
				pp=nm-1
				if finised_num[i] >= n-2:
					ml_next[i]=-1
				else:
					ml_next[i]=aal[i][finised_num[i]+1]
					
				if finised_num[pp] >= n-2:
					ml_next[pp]=-1
				else:
					ml_next[pp]=aal[pp][finised_num[pp]+1]
					
				finised_num[i]+=1
				finised_num[pp]+=1
				last_match_day[i]=dd
				last_match_day[pp]=dd
				ttn+=2
		
		if pttn==ttn:
			return -1
			
	return dd
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
import sys

n = int(input())

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

f = True
day = 1
while(f):
  done = []
  nokori_games = []
  
  for m in range(n):
    nokori_games[m] = len(a[m])
    if m in done:
      pass
    elif nokori_games[m]:
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
        nokori_games[m] -= 1
  if not sum(nokori_games):
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<vector<int>> spam(n, vector<int>(n));

    for(int i = 0;i<n;i++){
        for(int j = 0;j<n-1;j++){
            cin >> spam.at(i).at(j);
            spam.at(i).at(j) -= 1;
        }
    }
    int index[n]={0};
    int emptyCnt=0;
    int ans = 0;
    while (1){
        bool find = false;
        bool used[n]={false};
        for(int i = 0;i<n;i++){
            if(used[i]) continue;
            if(index[i]>=n-1) continue;
            int tmp = spam.at(i).at(index[i]);
            if(used[tmp]) continue; 
            // cout << "i:" << i << "tmp:" << tmp<<endl;
            if(spam.at(tmp).at(index[tmp])==i){
                find = true;
                used[i]=true;
                used[tmp]=true;
                
                index[i] +=1;
                index[tmp] +=1;
                emptyCnt += (index[i]>=n-1);
                emptyCnt += (index[tmp]>=n-1);
            }
        }
        if(find) ans++;
        else{
            cout << -1 << endl;
            return 0;
        }
        if(emptyCnt >= n){break;}
    }
    cout << ans << endl;
    
    // for(int i = 0;i<n;i++){
    //     for(int j = 0;j<n-1;j++){
    //         cout << spam.at(i).at(j);
    //     }
    //     cout << endl;
    // }
}

Submission status: Runtime Error

Solution code:
import sys

n = int(input())

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

f = True
day = 1
while(f):
  done = []
  nokori = False
  for m in range(n):
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
      	if not nokori and len(a[m]):
          nokori = True
  if not nokori:
    for m in range(n):
      if len(a[m]):
        print(-1)
        sys.exit()
    print(day)
    sys.exit()
  day += 1

Submission status: Runtime Error

Solution code:
import os

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


MAXV = N*(N-1)//2
id = [[-1 for _ in range(N)]for _ in range(N)]
to = [[] for _ in range(MAXV)]

def to_id(i, j):
    if i > j:
        j, i = i, j
    return id[i][j]


visited = [False for _ in range(MAXV)]
calculated = [False for _ in range(MAXV)]
dp = [-1 for _ in range(MAXV)]
def dfs(i):
    if visited[i]:
        if not calculated[i]:
            return -1
        else:
            return dp[i]
    visited[i] = True
    dp[i] = 1
    for u in to[i]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[i] = max(dp[i], res+1)
    calculated[i] = True
    return dp[i]

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] = to_id(i, a[i][j]-1)
    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)
        os.sys.exit()
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
import os

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


MAXN = 1001
MAXV = MAXN*(MAXN-1)//2
id = [[0 for _ in range(MAXN)]for _ in range(MAXN)]
to = [[] for _ in range(MAXV)]

def to_id(i, j):
    if i > j:
        j, i = i, j
    return id[i][j]


visited = [False for _ in range(MAXV)]
calculated = [False for _ in range(MAXV)]
dp = [-1 for _ in range(MAXV)]
def dfs(i):
    if visited[i]:
        if not calculated[i]:
            return -1
        else:
            return dp[i]
    visited[i] = True
    dp[i] = 1
    for u in to[i]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[i] = max(dp[i], res+1)
    calculated[i] = True
    return dp[i]

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] = to_id(i, a[i][j]-1)
    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)
        os.sys.exit()
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
import os

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


MAXN = 1001
MAXV = MAXN*(MAXN-1)//2
id = [[0 for _ in range(MAXN)]for _ in range(MAXN)]
to = [[] for _ in range(MAXV)]

def to_id(i, j):
    if i > j:
        j, i = i, j
    return id[i][j]


visited = [False for _ in range(MAXV)]
calculated = [False for _ in range(MAXV)]
dp = [-1 for _ in range(MAXV)]
def dfs(i):
    if visited[i]:
        if not calculated[i]:
            return -1
        else:
            return dp[i]
    visited[i] = True
    dp[i] = 1
    for u in to[i]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[i] = max(dp[i], res+1)
    calculated[i] = True
    return dp[i]

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

for i in range(N):
    for j in range(N-1):
        a[i][j] = to_id(i, a[i][j]-1)
    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)
        os.sys.exit()
    ans = max(ans, res)
print(ans)