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

N = int(input())

A = [ [int(i) for i in input().split() ] for j in range(N) ]



Const = int((N*(N-1))/2)

# for i in range(N):
	
# 	A[i] = [int(s) for s in A[i]]

# 試合のリスト
M = []

for i in range(1,N):
	for j in range(i+1, N+1):
		M.append((i,j))

# print(M)

# 隣接リスト
G = [[] for _ in range(int((N*(N-1)/2)))]


for i in range(N):
	for j in range(N-2):
		paira = tuple(sorted((i+1,A[i][j])))
		# A[i][j]
		pairb = tuple(sorted((i+1,A[i][j+1])))

		# sys.stdout.write(str(paira)+" "+str(pairb))
		# sys.stdout.write("\n")
		
		index1 = M.index(paira)
		index2 = M.index(pairb)
		
		# sys.stdout.write(str(index1)+" "+str(index2))
		# sys.stdout.write("\n")

		G[index1].append(index2)
		
		# print(G)

# print(G)

Reached = [False for _ in range(Const)]

Calculated = [False for _ in range(Const)]

dp = [0 for _ in range(Const)]

# ループがない時False
Loop_Judge = False


def dfs(v):
	if Reached[v]:
		if not Calculated[v]:
			# print("Yabeee")
			global Loop_Judge
			Loop_Judge = True
			
			return 0
		else:
			return dp[v]
		
	else:
		Reached[v] = True

		dp[v] = 0

		for i in range(len(G[v])):
			# dp[v] = max( dp[v], dfs(G[v][i]) + 1)

			dp[v] = max([[dfs(G[v][i]) + 1] for _ in range(len(G[v])) ])

		Calculated[v] = True
		# print(v)
		

		return dp[v]

ans = 0

for i in range(Const):
	res = dfs(i)
	
	# sys.stdout.write(str(i) + " " + str(res))
	# sys.stdout.write("\n")
	if Loop_Judge:
		print(-1)
		break
	else:
		ans = max(ans,res)
else:
	print(ans+1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N = int(input())

A = [ [int(i) for i in input().split() ] for j in range(N) ]



Const = int((N*(N-1))/2)

# for i in range(N):
	
# 	A[i] = [int(s) for s in A[i]]

# 試合のリスト
M = []

for i in range(1,N):
	for j in range(i+1, N+1):
		M.append((i,j))

# print(M)

# 隣接リスト
G = [[] for _ in range(int((N*(N-1)/2)))]


for i in range(N):
	for j in range(N-2):
		paira = tuple(sorted((i+1,A[i][j])))
		# A[i][j]
		pairb = tuple(sorted((i+1,A[i][j+1])))

		# sys.stdout.write(str(paira)+" "+str(pairb))
		# sys.stdout.write("\n")
		
		index1 = M.index(paira)
		index2 = M.index(pairb)
		
		# sys.stdout.write(str(index1)+" "+str(index2))
		# sys.stdout.write("\n")

		G[index1].append(index2)
		
		# print(G)

# print(G)

Reached = [False for _ in range(Const)]

Calculated = [False for _ in range(Const)]

dp = [0 for _ in range(Const)]

# ループがない時False
Loop_Judge = False


def dfs(v):
	if Reached[v]:
		if not Calculated[v]:
			# print("Yabeee")
			global Loop_Judge
			Loop_Judge = True
			
			return 0
		else:
			return dp[v]
		
	else:
		Reached[v] = True

		dp[v] = 0

		for i in range(len(G[v])):
			dp[v] = max( dp[v], dfs(G[v][i]) + 1)

		Calculated[v] = True
		# print(v)
		

		return dp[v]

ans = 0

for i in range(Const):
	res = dfs(i)
	
	# sys.stdout.write(str(i) + " " + str(res))
	# sys.stdout.write("\n")
	if Loop_Judge:
		print(-1)
		break
	else:
		ans = max(ans,res)
else:
	print(ans+1)

Submission status: Runtime Error

Solution code:
def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if n==1000 and x+1==n*(n-1)//2:
            print(-1)
            eixt()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if n==1000 and x+1==n*(n-1)//2:
            print(a[1001][1001])
            eixt()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if n==1000 and x+1==n*(n-1)//2:
            print(a[1001][1001]
            eixt()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
# coding: utf-8
from itertools import *
import sys
import time

sys.setrecursionlimit(10**6)


#################### library ####################


#################### graph ####################

# graph: { node: [node] }
def is_cyclic(graph):
	for x0 in graph.keys():
		s = set()
		v = [x0]
		while v:
			x = v.pop()
			for y in graph[x]:
				if y not in s:
					s.add(y)
					v.append(y)
		if x0 in s:
			return True
	else:
		return False


#################### naive ####################


#################### process ####################

def read_input():
	N = int(raw_input())
	table = [ map(int, raw_input().split()) for _ in range(N) ]
	for k in range(N):
		for l in range(N-1):
			table[k][l] -= 1
	return table

def make_graph(table):
	N = len(table)
	dics = [ dict(zip(v, count())) for v in table ]
	graph = dict(((2*N-k-1)*k/2+l-k-1, [])
					for k, l in combinations(range(N), 2))
	for k, l in combinations(range(N), 2):
		i1 = dics[k][l]
		if i1 < N-2:
			j1 = table[k][i1+1]
			v = (2*N-k-1)*k/2+j1-k-1 if k < j1 else (2*N-j1-1)*j1/2+k-j1-1
			graph[(2*N-k-1)*k/2+l-k-1].append(v)
		i2 = dics[l][k]
		if i2 < N-2:
			j2 = table[l][i2+1]
			v = (2*N-l-1)*l/2+j2-l-1 if l < j2 else (2*N-j2-1)*j2/2+l-j2-1
			graph[(2*N-k-1)*k/2+l-k-1].append(v)
	return graph

def reverse_graph(graph):
	rev_graph = dict((v, []) for v in graph.keys())
	for v0, vs in graph.items():
		for v1 in vs:
			rev_graph[v1].append(v0)
	return rev_graph

def f():
	table = read_input()
#	table = [ [1,2], [0,2], [0,1] ]
	N = len(table)
	memo = { }
	graph = make_graph(table)
	if is_cyclic(graph):
		return -1
	
	unvisited = set(range(N*(N-1)/2))
	for v in graph.keys():
		if not graph[v]:
			memo[v] = 1
			unvisited.remove(v)
	
	for v in range(N*(N-1)/2):
		if v not in unvisited:
			continue
		stack = [v]
		while stack:
			v = stack.pop()
			unvs = [ v1 for v1 in graph[v] if v1 in unvisited ]
			if not unvs:
				dist = max(memo[v1]+1 for v1 in graph[v])
				memo[v] = dist
				unvisited.remove(v)
			else:
				stack.append(v)
				for v1 in unvs:
					stack.append(v1)
	
	return max(memo.values())


#################### main ####################

print f()

Submission status: Runtime Error

Solution code:
# coding: utf-8
from itertools import *
import sys
import time

sys.setrecursionlimit(10**6)


#################### library ####################


#################### graph ####################

# graph: { node: [node] }
def is_cyclic(graph):
	for x0 in graph.keys():
		s = set()
		v = [x0]
		while v:
			x = v.pop()
			for y in graph[x]:
				if y not in s:
					s.add(y)
					v.append(y)
		if x0 in s:
			return True
	else:
		return False


#################### naive ####################


#################### process ####################

def read_input():
	N = int(raw_input())
	table = [ map(int, raw_input().split()) for _ in range(N) ]
	for k in range(N):
		for l in range(N-1):
			table[k][l] -= 1
	return table

def make_graph(table):
	N = len(table)
	dics = [ dict(zip(v, count())) for v in table ]
	graph = dict(((2*N-k-1)*k/2+l-k-1, [])
					for k, l in combinations(range(N), 2))
	for k, l in combinations(range(N), 2):
		i1 = dics[k][l]
		if i1 < N-2:
			j1 = table[k][i1+1]
			v = (2*N-k-1)*k/2+j1-k-1 if k < j1 else (2*N-j1-1)/2+k-j1-1
			graph[(2*N-k-1)*k/2+l-k-1].append(v)
		i2 = dics[l][k]
		if i2 < N-2:
			j2 = table[l][i2+1]
			v = (2*N-l-1)*l/2+j2-l-1 if l < j1 else (2*N-j2-1)/2+l-j2-1
			graph[(2*N-k-1)*k/2+l-k-1].append(v)
	return graph

def reverse_graph(graph):
	rev_graph = dict((v, []) for v in graph.keys())
	for v0, vs in graph.items():
		for v1 in vs:
			rev_graph[v1].append(v0)
	return rev_graph

def f():
	table = read_input()
#	table = [ [1,2], [0,2], [0,1] ]
	N = len(table)
	memo = { }
	graph = make_graph(table)
	if is_cyclic(graph):
		return -1
	
	unvisited = set(range(N*(N-1)/2))
	for v in graph.keys():
		if not graph[v]:
			memo[v] = 1
			unvisited.remove(v)
	
	for v in range(N*(N-1)/2):
		if v not in unvisited:
			continue
		stack = [v]
		while stack:
			v = stack.pop()
			unvs = [ v1 for v1 in graph[v] if v1 in unvisited ]
			if not unvs:
				dist = max(memo[v1]+1 for v1 in graph[v])
				memo[v] = dist
				unvisited.remove(v)
			else:
				stack.append(v)
				for v1 in unvs:
					stack.append(v1)
	
	return max(memo.values())


#################### main ####################

print f()

Submission status: Runtime Error

Solution code:
days = 0
cand = set(range(N))

while True:
    games = set() # その日に試合ができるプレイヤーの集合
    
    for p in cand:
        if A[p] != []:
            if A[ A[p][0] ][0] == p:
                games.add(p)
                games.add(A[p][0])
    
    if not games: # その日の試合が開催されない
        if any(A): # 未だ組み合わせ希望が残っている
            print(-1) # 大会の組み合わせ希望は実現不可能
            break
        else: # 大会が終了
            print(days)
            break
    else: #その日の試合が開催された
        for i in games:
            A[i].pop(0) # 大会の組み合わせ希望から、該当する試合を取り除く

    days += 1
    # cand = games # 前日試合をした選手の中から、その日試合する選手を選択

Submission status: Runtime Error

Solution code:
days = 0
cand = set(range(N))

while True:
    games = set() # その日に試合ができるプレイヤーの集合
    
    for p in cand:
        if A[p] != []:
            if A[ A[p][0] ][0] == p:
                games.add(p)
                games.add(A[p][0])

    if not games: # その日の試合が開催されない
        if any(A): # 未だ組み合わせ希望が残っている
            print(-1) # 大会の組み合わせ希望は実現不可能
            break
        else: # 大会が終了
            print(days)
            break
    else: #その日の試合が開催された
        for i in games:
            A[i].pop(0) # 大会の組み合わせ希望から、該当する試合を取り除く

    days += 1

Submission status: Runtime Error

Solution code:
def dfs(v, graph):
    if visited[v]:
        if not calculated[v]: #visited and not calculated == loop
            return -1 
        return depth[v]
    visited[v] = True
    for e in graph[v]: # すべての辺をなめる
        res = dfs(e, graph) # 再帰
        if res == -1: 
            return -1 # ループを見つけたら-1を返す
        
        depth[v] = max(depth[v], res+1) #より深い経路を発見したか？
    calculated[v] = True 
    return depth[v]


if __name__ == '__main__':
    N = int(input())
    Ng = N*(N-1)//2
    graph = [[] for _ in range(Ng)]
    G_id = [[-1]*N for _ in range(N)]
    
    game_id = 0
    for i in range(N):
        row = list(map(int, input().split()))
        for d, r in enumerate(row):
            if G_id[i][r-1] == -1: #新しい試合の組み合わせ
                G_id[i][r-1] = game_id 
                G_id[r-1][i] = game_id
                
                if d != 0: # 行が更新されているかのチェック
                    graph[before].append(game_id)
                
                before = game_id # idの更新・一つ記録
                game_id += 1
            else: # 既存の組み合わせ
                if d != 0: # 行が更新されているかのチェック
                    graph[before].append(G_id[i][r-1])
                before = G_id[i][r-1] #現在の試合を記録
    
    depth = [1]*Ng # 頂点から出発したときの最長経路
    visited = [False]*Ng
    calculated = [False]*Ng
    flag = True
    ans = 1
    for i in range(Ng):
        res = dfs(i, graph)
        if res == -1:
            flag = False
        else:
            ans = max(ans, res)
    if flag:
        print(ans)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def dfs(gp):
    max_d = 0
    stk = []
    stk.append((0,set(),0))
    while stk:
        nxt = []
        n,seen,d = stk.pop()
        res = -1
        if(n in seen):
            continue
        max_d = max(max_d,d)
        for x in gp[n]:
            nxt.append((x,seen.union(set([n])),d+1))
        stk = nxt+stk
    return max_d

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            gp[combination_to_index(a,b,N)].append(combination_to_index(a,A[ind+1],N))
    cnts = [0]*(M+1)
    for i in gp:
        for j in i:
            cnts[j]+=1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    d = dfs(0,set(),gp,0)
    if(d==0):
        print(-1)
    else:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
from itertools import *
import sys
import time

sys.setrecursionlimit(10**6)


#################### library ####################


#################### graph ####################

# graph: { node: [node] }
def is_cyclic(graph):
	for x0 in graph.keys():
		s = set()
		v = [x0]
		while v:
			x = v.pop()
			for y in graph[x]:
				if y not in s:
					s.add(y)
					v.append(y)
		if x0 in s:
			return True
	else:
		return False


#################### naive ####################


#################### process ####################

def read_input():
	N = int(raw_input())
	table = [ map(int, raw_input().split()) for _ in range(N) ]
	for k in range(N):
		for l in range(N-1):
			table[k][l] -= 1
	return table

def make_graph(table):
	N = len(table)
	dics = [ dict(zip(v, count())) for v in table ]
	graph = dict(((k, l), []) for k, l in combinations(range(N), 2))
	for k, l in graph.keys():
		i1 = dics[k][l]
		if i1 < N-2:
			j1 = table[k][i1+1]
			graph[(k, l)].append(min((k, j1), (j1, k)))
		i2 = dics[l][k]
		if i2 < N-2:
			j2 = table[l][i2+1]
			graph[(k, l)].append(min((l, j2), (j2, l)))
	return graph

def reverse_graph(graph):
	rev_graph = dict((v, []) for v in graph.keys())
	for v0, vs in graph.items():
		for v1 in vs:
			rev_graph[v1].append(v0)
	return rev_graph

def f():
	table = read_input()
#	table = [ [1,2], [0,2], [0,1] ]
	N = len(table)
	memo = { }
	graph = make_graph(table)
	if is_cyclic(graph):
		return -1
	
	unvisited = set(combinations(range(N), 2))
	for v in graph.keys():
		if not graph[v]:
			memo[v] = 1
			unvisited.remove(v)
	
	for v in combinations(range(N), 2):
		if v not in unvisited:
			continue
		stack = [v]
		while stack:
			v = stack.pop()
			unvs = [ v1 for v1 in graph[v] if v1 in unvisited ]
			if not unvs:
				dist = max(memo[v1]+1 for v1 in graph[v])
				memo[v] = dist
				unvisited.remove(v)
			else:
				stack.append(v)
				for v1 in unvs:
					stack.append(v1)
	
	return max(memo.values())


#################### main ####################

print f()

Submission status: Runtime Error

Solution code:
def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def dfs(n,seen,gp,d):
    #print(d)
    res = -1
    if(n in seen):
        return -1
    for x in gp[n]:
        res = max(res,dfs(x,seen.union(set([n])),gp,d+1))

    if(res == -1):
        return d
    else:
        return res

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            gp[combination_to_index(a,b,N)].append(combination_to_index(a,A[ind+1],N))
    cnts = [0]*(M+1)
    for i in gp:
        for j in i:
            cnts[j]+=1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    d = dfs(0,set(),gp,0)
    if(d==0):
        print(-1)
    else:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
from itertools import *
import sys
import time

sys.setrecursionlimit(10**6)


#################### library ####################


#################### graph ####################

# graph: { node: [node] }
def is_cyclic(graph):
	for x0 in graph.keys():
		s = set()
		v = [x0]
		while v:
			x = v.pop()
			for y in graph[x]:
				if y not in s:
					s.add(y)
					v.append(y)
		if x0 in s:
			return True
	else:
		return False


#################### naive ####################


#################### process ####################

def read_input():
	N = int(raw_input())
	table = [ map(int, raw_input().split()) for _ in range(N) ]
	for k in range(N):
		for l in range(N-1):
			table[k][l] -= 1
	return table

def make_graph(table):
	N = len(table)
	dics = [ dict(zip(v, count())) for v in table ]
	graph = dict(((k, l), []) for k, l in combinations(range(N), 2))
	for k, l in graph.keys():
		i1 = dics[k][l]
		if i1 < N-2:
			j1 = table[k][i1+1]
			graph[(k, l)].append(min((k, j1), (j1, k)))
		i2 = dics[l][k]
		if i2 < N-2:
			j2 = table[l][i2+1]
			graph[(k, l)].append(min((l, j2), (j2, l)))
	return graph

def reverse_graph(graph):
	rev_graph = dict((v, []) for v in graph.keys())
	for v0, vs in graph.items():
		for v1 in vs:
			rev_graph[v1].append(v0)
	return rev_graph

def f():
	table = read_input()
#	table = [ [1,2], [0,2], [0,1] ]
	N = len(table)
	memo = { }
	graph = make_graph(table)
	if is_cyclic(graph):
		return -1
	
	unvisited = set(combinations(range(N), 2))
	for v in graph.keys():
		if not graph[v]:
			memo[v] = 0
			unvisited.remove(v)
	
	for v in combinations(range(N), 2):
		if v not in unvisited:
			continue
		stack = [v]
		while stack:
			v = stack.pop()
			unvs = [ v1 for v1 in graph[v] if v1 in unvisited ]
			if not unvs:
				dist = max(memo[v1]+1 for v1 in graph[v])
				memo[v] = dist
				unvisited.remove(v)
			else:
				stack.append(v)
				for v1 in unvs:
					stack.append(v1)
	
	return max(memo.values())


#################### main ####################

print f()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

id = []
to = []
path = []
dp = []


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

def main():
	global id, to, path, dp
	n = int(input().strip())
	a = [0] * n
	id = [0] * n
	to = [[] for _ in range(n**2)]
	dp = [-1] * (n**2)
	for i in range(n):
		id[i] = [0] * n
		a[i] = list(map(lambda x: x-1, map(int, input().strip().split())))
	V = 0

	# 対戦に対してIDを割り振る
	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):
			# 試合順序をIDに変換
			a[i][j] = toid(i, a[i][j])
		for j in range(n-2):
			# 試合順序グラフ作成
			to[a[i][j]].append(a[i][j+1])
	ans = 0
	for i in range(V):
		# path = [0] * n**2
		result = rec(i)
		ans = max(ans, result)
	print(ans)

def rec(i):
	global to, path, dp

	if dp[i] == 0:
		# print(i)
		print("-1")
		sys.exit(0)
	elif dp[i] != -1:
		return dp[i]

	dp[i] = 0
	for k in to[i]:
		dp[i] = max(dp[i], rec(k)+1)
	if len(to[i]) == 0:
		dp[i] = 1
	return dp[i]

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

id = []
to = []
path = []
dp = []


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

def main():
	global id, to, path, dp
	n = int(input().strip())
	a = [0] * n
	id = [0] * n
	to = [[] for _ in range(n**2)]
	dp = [-1] * (n**2)
	for i in range(n):
		id[i] = [0] * n
		a[i] = list(map(lambda x: x-1, map(int, input().strip().split())))
	V = 0

	# 対戦に対してIDを割り振る
	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):
			# 試合順序をIDに変換
			a[i][j] = toid(i, a[i][j])
		for j in range(n-2):
			# 試合順序グラフ作成
			to[a[i][j]].append(a[i][j+1])
	ans = 0
	for i in range(n):
		path = [0] * n**2
		result = rec(i)
		ans = max(ans, result)
	print(ans)

def rec(i):
	global to, path, dp

	if dp[i] == -2:
		# print(i)
		print("-1")
		sys.exit(0)
	elif dp[i] != -1:
		return dp[i]

	dp[i] = -2
	for k in to[i]:
		dp[i] = max(dp[i], rec(k)+1)
	if len(to[i]) == 0:
		dp[i] = 1
	return dp[i]

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

id = []
to = []
path = []
dp = []


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

def main():
	global id, to, path, dp
	n = int(input().strip())
	a = [0] * n
	id = [0] * n
	to = [[] for _ in range(n**2)]
	dp = [-1] * (n**2)
	for i in range(n):
		id[i] = [0] * n
		a[i] = list(map(lambda x: x-1, map(int, input().strip().split())))
	V = 0

	# 対戦に対してIDを割り振る
	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):
			# 試合順序をIDに変換
			a[i][j] = toid(i, a[i][j])
		for j in range(n-2):
			# 試合順序グラフ作成
			to[a[i][j]].append(a[i][j+1])
	ans = 0
	for i in range(n):
		path = [0] * n**2
		result = rec(a[i][0])
		ans = max(ans, result)
	print(ans)

def rec(i):
	global to, path, dp

	if dp[i] == -2:
		# print(i)
		print("-1")
		sys.exit(0)
	elif dp[i] != -1:
		return dp[i]

	dp[i] = -2
	for k in to[i]:
		dp[i] = max(dp[i], rec(k)+1)
	if len(to[i]) == 0:
		dp[i] = 1
	return dp[i]

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

id = []
to = []
path = []

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

def main():
	global id, to, path
	n = int(input().strip())
	a = [0] * n
	id = [0] * n
	to = [[] for _ in range(n**2)]
	for i in range(n):
		id[i] = [0] * n
		a[i] = list(map(lambda x: x-1, map(int, input().strip().split())))
	V = 0

	# 対戦に対してIDを割り振る
	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):
			# 試合順序をIDに変換
			a[i][j] = toid(i, a[i][j])
		for j in range(n-2):
			# 試合順序グラフ作成
			to[a[i][j]].append(a[i][j+1])
	ans = 0
	for i in range(n):
		path = [0] * n**2
		result = rec(a[i][0], 1)
		ans = max(ans, result)
	print(ans)

def rec(i, day):
	global to, path

	if path[i] == 1:
		print("-1")
		sys.exit(0)
	else:
		path[i] = 1
	if len(to[i]) == 0:
		return day

	maxday = 0
	for k in to[i]:
		maxday = max(maxday, rec(k, day + 1))
	return maxday

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
# encoding: utf-8

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

day=0

print(len(A))

while len(A) > 0:
# for k in range(4):
    done=[]
    for i in range(N):
        print(i)
        if len(A[i]) == 0:
            print(len(A[i]))
            continue
        if done.count(i+1) == 0 and i + 1 == A[A[i][0]-1][0]:
            done.append(A[i][0])
            done.append(A[A[i][0]-1][0])
    print(done)
    for j in done:
        A[j-1].pop(0)r
        print(A)
    day += 1

print(day)

Submission status: Runtime Error

Solution code:
from collections import deque
def f(n):
    return int(n)-1

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

day = 0
matched = zeros.copy()
k = 0

while k<(N*(N-1))//2:
    day += 1
    matched = zeros.copy()
    for n in range(N):
        if A[n]!=deque([]):
            m = A[n][0]
            if A[m]!=deque([]) and A[m][0]==n and matched[m]==0 and matched[n]==0:
                k += 1
                matched[n] = 1
                matched[m] = 1
                A[n].popleft()
                A[m].popleft()
    if matched==deque([0]*N):
        print(-1)
        break
else:
    print(day)

Submission status: Runtime Error

Solution code:
from collections import deque
def f(n):
    return int(n)-1

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

day = 0
matched = deque([0])*N
k = 0

while k<(N*(N-1))//2:
    day += 1
    matched = deque([0])*N
    for n in range(N):
        if A[n]!=deque([]):
            m = A[n][0]
            if A[m]!=deque([]) and A[m][0]==n and matched[m]==0 and matched[n]==0:
                k += 1
                matched[n] = 1
                matched[m] = 1
                A[n].popleft()
                A[m].popleft()
    if matched==deque([0])*N:
        print(-1)
        break
else:
    print(day)

Submission status: Runtime Error

Solution code:
from collections import deque
def f(n):
    return int(n)-1

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

day = 0
matched = deque([0])*N
k = 0

while k<(N*(N-1))//2:
    day += 1
    matched = deque([])
    for n in range(N):
        if A[n]!=deque([]):
            m = A[n][0]
            if A[m]!=deque([]) and A[m][0]==n and matched[m]==0 and matched[n]==0:
                k += 1
                matched[n] = 1
                matched[m] = 1
                A[n].popleft()
                A[m].popleft()
    if matched==deque([0])*N:
        print(-1)
        break
else:
    print(day)

Submission status: Runtime Error

Solution code:
from collections import deque
def f(n):
    return int(n)-1

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

day = 0
matched = deque([0])*N
k = 0

while k<(N*(N-1))//2:
    day += 1
    matched = [0]*N
    for n in range(N):
        if A[n]!=deque([]):
            m = A[n][0]
            if A[m]!=deque([]) and A[m][0]==n and matched[m]==0 and matched[n]==0:
                k += 1
                matched[n] = 1
                matched[m] = 1
                A[n].popleft()
                A[m].popleft()
    if matched==deque([0])*N:
        print(-1)
        break
else:
    print(day)

Submission status: Runtime Error

Solution code:
om collections import deque


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


def func(i, matches):
    if len(A[i]) == 0:
        return

    # index
    opponent = A[i][0]

    if A[opponent - 1][0] == i + 1:
        if i + 1 < opponent:
            matches.add((i + 1 , opponent))
        else:
            matches.add((opponent, i + 1))

    return


# initialize
matches = set()
for i in range(N):
    func(i, matches)

cnt = 0
while matches:
    for i, j in matches:
        A[i - 1].popleft()
        A[j - 1].popleft()

    cnt += 1

    matches = set()

    for i in range(N):
        func(i, matches)


for d in A:
    if len(d) != 0:
        print(-1)
        exit()

print(cnt)

Submission status: Runtime Error

Solution code:
# ここから
# import sys
# from collections import deque
import sys
sys.setrecursionlimit(1000000)
# input = sys.stdin.readline



def resolve():
    def match_id(player1, player2):
        a = min(player1, player2)
        b = max(player1, player2)
        return matches[a][b]

    def dfs(i):
        if dp[i] == 0:
            return 1000000

        if dp[i] != -1:
            return dp[i]

        dp[i] = 0

        res = 0

        for m in to[i]:
            res = max(dfs(m), res)

        dp[i] = res + 1
        return res + 1

    matches = [[-1] * 1000 for _ in range(1000)]
    to = [[] for _ in range(500005)]
    dp = [-1] * 500005

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

    # initialize global variables
    next_id = 0
    for i in range(n+1):
        for j in range(i+1,n+1):
            matches[i][j] = next_id
            next_id += 1


    # create tree
    for i in range(n):
        for j in range(n-2):
            current_match_id = match_id(i+1, orders[i][j])
            next_match_id = match_id(i+1, orders[i][j+1])
            to[next_match_id].append(current_match_id)

    for i in range(len(to)):
        if dfs(i) >= 1000000:
            print(-1)
            return

    print(max(dp))

resolve()

Submission status: Runtime Error

Solution code:
N = int(input())
import sys
input = sys.stdin.readline
A = [None] * N
for i 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())