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
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 = [[int(x) - 1 for x in row.split()] for row in readlines()]


ids = [[0 for j in range(N)] for i in range(N)]
V = 0
for i in range(N):
    for j in range(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)

Submission status: Runtime Error

Solution code:
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 = [[int(x) - 1 for x in row.split()] for row in readlines()]


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

MAXV = 1000 * 1000 // 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)

Submission status: Runtime Error

Solution code:
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 = list(map(lambda x: x.split(), read().decode().split('\n')))

l = defaultdict(list)
visited = {}
dp = {}

# make topological tree
key = ''
for i in range(n):

    if i + 1 < int(A[i][0]):
        key = '{}-{}'.format(i + 1, A[i][0])
    else:
        key = '{}-{}'.format(A[i][0], i + 1)
    
    visited[key] = False 
    dp[key] = 0 
    prev_key = key

    for j in range(1, n - 1):
        if i + 1 < int(A[i][j]):
            key = '{}-{}'.format(i + 1, A[i][j])
        else:
            key = '{}-{}'.format(A[i][j], i + 1)

        l[prev_key].append(key)
        prev_key = key
        # init visited
        visited[key] = False 
        dp[key] = 0


topo = []
# dp = [0 for i in range(n + 1)]
def dfs(start):
    if visited[start]:
        return dp[start]

    visited[start] = True    
    dp[start] = 0
    for node in l[start]:
        dp[start] = max(dp[start], dfs(node) + 1)

    return dp[start]

ans = 0
for key in list(l):
    ans = max(dfs(key), ans)

print(ans + 1)

# print(l)
# print(topo)
# for node in reversed(topo):


# for noe in topo:

Submission status: Runtime Error

Solution code:
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 = list(map(lambda x: x.split(), read().decode().split('\n')))

l = defaultdict(list)
visited = {}
passed = {}

# make topological tree
key = ''
for i in range(n):

    if i + 1 < int(A[i][0]):
        key = f'{i + 1}-{A[i][0]}'
    else:
        key = f'{A[i][0]}-{i + 1}'
    
    visited[key] = False 
    passed[key] = False 
    prev_key = key

    for j in range(1, n - 1):
        if i + 1 < int(A[i][j]):
            key = f'{i + 1}-{A[i][j]}'
        else:
            key = f'{A[i][j]}-{i + 1}'

        l[prev_key].append(key)
        prev_key = key
        # init visited
        visited[key] = False 
        passed[key] = False 


topo = []
def dfs(start):
    passed[start] = True
    if not l[start]:
        visited[start] = True
        topo.append(start)
        return
    
    for node in l[start]:
        if visited[node]:
            continue
        
        if passed[node]:
            print(-1)
            exit()
        dfs(node)

    visited[start] = True
    topo.append(start)

for key in list(l):
    if visited[key]:
        continue
    dfs(key)

res = 0
check = [False for i in range(n + 1)]
for node in topo:
    a, b = map(int, node.split('-'))
    if check[a] or check[b]:
        check = [False for i in range(n + 1)]
        res += 1

    check[a] = True
    check[b] = True

if any(check):
    res += 1
print(res)

Submission status: Runtime Error

Solution code:
from collections import Counter
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)

Submission status: Runtime Error

Solution code:
n = int(input())
edges = [[] for _ in range(n * 1001)]
memo = []
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])

seen = [False for _ in range(1001 * n)]
def dfs(start, frm, cur, flg):
    for to in edges[cur]:
        if to == frm:
            continue
        if to == start:
            return False
        else:
            d[to] = max(d[cur] + 1, d[to])
            flg = dfs(start, cur, to, flg)

    return flg


flg = True
ans = []
for x in memo:
    d = [0 for _ in range(n * 1001)]
    d[x] = 1
    if dfs(x, -1, x, True):
        ans.append(max(d))
    else:
        flg = False

if flg:
    print(max(ans))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[]
for i in range(n):
	a.append(list(map(int,input().split())))
d=[[]for _ in range(n**2//2+2)]
start=[0]*(n**2)
for i in range(n):
	for j in range(n-2):
		p=[i,a[i][j]-1];q=[i,a[i][j+1]-1]
		if i>a[i][j]-1:
			p=[a[i][j]-1,i]
		if i>a[i][j+1]-1:
			q=[a[i][j+1]-1,i]
		start[p[0]*n+p[1]]+=1
		start[q[0]*n+q[1]]=-10**7
		d[p[0]*n+p[1]].append(q[0]*n+q[1])
st=-1
for i in range(n**2):
	if start[i]>0:
		st=i
		break
if st==-1:
	print(-1)
	exit()
stack=[st]
deep=[1]*(n**2//2+2)
while stack:
	p=stack.pop()
	for x in d[p]:
		stack.append(x)
		deep[x]=deep[p]+1
print(max(deep))

Submission status: Runtime Error

Solution code:
import math

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

test_case = []
for x in (-1, 0, 1):
    for y in (-1, 0, 1):
        test_case.append((x, y))
for i in range(n):
    x1, y1 = xy[i]
    test_case.append((x1, y1))
    test_case.append((-x1, -y1))
    test_case.append((y1, -x1))
    test_case.append((-y1, x1))

ret = 0
for x1, y1 in test_case:
    sx, sy, tx, ty = 0, 0, 0, 0
    for j in range(n):
        x2, y2 = xy[j]
        if x1 * x2 + y1 * y2 > 0 or (x1 * x2 + y1 * y2 == 0 and -y1 * x2 + x1 * y2 >= 0):
            sx += x2
            sy += y2
        else:
            tx += x2
            ty += y2
    ret = max(ret, math.hypot(sx, sy), math.hypot(tx, ty))
print(ret)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500000)

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
vs = n * (n - 1) // 2

vmap = {}
c = 0
for i in range(n):
    for j in range(i):
        vmap[(i, j)] = c
        vmap[(j, i)] = c
        c += 1

edges = [[] for _ in range(vs)]
numin = [0] * vs
for i in range(n):
    for j in range(n - 2):
        j1 = a[i][j] - 1
	j2 = a[i][j + 1] - 1
	edges[vmap[(i, j1)]].append(vmap[(i, j2)])
	numin[vmap[(i, j2)]] += 1

order = []
day = [1] * vs
q = [i for i in range(vs) if numin[i] == 0]
while len(q) > 0:
    index = q.pop(0)
    order.append(index)
    d = day[index]
    for i in edges[index]:
	numin[i] -= 1
	if numin[i] == 0:
            q.append(i)
            day[i] = max(day[i], d + 1)

print(max(day) if len(order) == vs else -1)

Submission status: Runtime Error

Solution code:
import sys
# from collections import deque
input = sys.stdin.readline

def main():
    n = int(input())
    v = n*(n-1)//2
    A = [list(map(int,input().split())) for _ in range(n)]

    # 頂点と i vs j との対応は (i < j)
    # (n-j+i)(n-j+i-1)//2 + i

    path = [set() for _ in range(v)]

    def vertex(vs1,vs2):
        m,M = sorted([vs1,vs2])
        return (n-M+m)*(n-M+m-1)//2 + m

    parent = set(range(v))

    for i in range(n):
        for j in range(1,n-1):
            vs = vertex(i,A[i][j] - 1)
            vsp= vertex(i,A[i][j-1] - 1)
            path[vs].add(vsp)
            if vsp in parent:
                parent.remove(vsp)

    def dfs(start):
        if memo[start] != -1:
            return memo[start]
        # que = deque([(start,1)])
        # ret = 0
        # while que:
        #     p,d = que.pop()
        #     for nxt in path[p]:
        #         ret = max(ret,d+1)
        #         que.append((nxt,d+1))
        ret = 1
        for nxt in path[start]:
            ret = max(ret,dfs(nxt) + 1)
        memo[start] = ret
        return ret

    ans = -1
    memo = [-1]*v
    for i in parent:
        ans  = max(ans, dfs(i))
    print(ans)

main()

Submission status: Runtime Error

Solution code:
n=int(input())
a=[list(map(int,input().split()))[::-1] for _ in range(n)]
tcnt,ans=0,0
while tcnt<n*(n-1)//2:
  cnt=0
  chk=[]
  for i in range(n-1):
    if i in chk:
      continue
    else:
      if a[i]:
        b=a[i][-1]-1
        if b in chk:
          continue
        else:
          if b>i and a[b][-1]-1==i:
            chk.append(a[i].pop()-1,a[b].pop()-1)
            cnt+=1
  tcnt+=cnt
  ans+=1
  if cnt==0:
    ans=-1
    break
print(ans)

Submission status: Runtime Error

Solution code:
def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*(N-1)//2
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[] for _ in range(n * n)]
v = [0] * (n * n)
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n - 2):
        p, q = min(i, a[j] - 1), max(i, a[j] - 1)
        s, t = min(i, a[j + 1] - 1), max(i, a[j + 1] - 1)
        g[p * n + q].append(s * n + t)
        v[s * n + t] += 1
s = []
vs = [1] * (n * n)
l = []
for i in range(n):
    for j in range(i + 1, n):
        if v[i * n + j] == 0:
            s.append(i * n + j)
            vs[i * n + j] = 0
ans = 0
while s:
    p = s.pop()
    l.append(p)
    vs[p] = 0
    for node in g[p]:
        if vs[node]:
            v[node] -= 1
            if v[node] == 0:
                s.append(node)
if len(l) * 2 != n * (n - 1):
    print(-1)
    exit(1)
d = [0] * (n * n)
for x in l:
    for node in g[x]:
        d[node] = d[x] + 1
print(d[l[-1]] + 1)

Submission status: Runtime Error

Solution code:
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
v = n*(n-1)//2
E = [[] for i in range(v)]
dic = {}
c = 0
for i in range(n):
    for j in range(n-1):
        a,b = i,l[i][j]-1
        if a > b:
            a,b = b,a
        if (a,b) in dic:
            l[i][j] = dic[(a,b)]
        else:
            dic[(a,b)] = c
            l[i][j] = dic[(a,b)]
            c += 1
    for j in range(n-2):
        E[l[i][j]].append(l[i][j+1])

def dfs(i):
    if visit[i]:
        if dis[i] == -1:
            return -1
        else:
            return dis[i]
    visit[i] = True
    d = 1
    for nex in E[i]:
        res = dfs(nex)
        if res == -1:
            return -1
        d = max(d,res+1)

    dis[i] = d
    return d

visit = [False]*v
dis = [-1]*v
print(dfs(l[0][0]))

Submission status: Runtime Error

Solution code:
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
v = n*(n-1)//2
E = [[] for i in range(v)]
dic = {}
c = 0
for i in range(n):
    for j in range(n-1):
        a,b = i,l[i][j]-1
        if a > b:
            a,b = b,a
        if (a,b) in dic:
            l[i][j] = dic[(a,b)]
        else:
            dic[(a,b)] = c
            l[i][j] = dic[(a,b)]
            c += 1
    for j in range(n-2):
        E[l[i][j]].append(l[i][j+1])

def dfs(i):
    if visit[i]:
        if dis[i] == -1:
            return -1
        else:
            return dis[i]
    visit[i] = True
    d = 1
    for nex in E[i]:
        res = dfs(nex)
        if res == -1:
            return -1
        d = max(d,res+1)

    dis[i] = d
    return d
ans = 0
done = []
for i in range(n):
    if l[i][0] in done:
        continue
    visit = [False]*v
    dis = [-1]*v
    count = dfs(l[i][0])
    if count == -1:
        print(-1)
        exit()
    else:
        ans = max(ans,count)
    done.append(l[i][0])
print(ans)

Submission status: Runtime Error

Solution code:
import sys,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}

for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
q=set([])
flag={n:0 for n in node}
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.add(key)
sub=set([])
while q:
    while q:
        x=q.pop()
        for n in _to[x]:
            flag[n]+=1
            if flag[n]==len(_from[n]):
                sub.add(n)
        if not q:
            q=sub
            sub=set([])
            day+=1
            break
able=True
for n in node:
    if flag[n]!=len(_from[n]):
        able=False
if able:
    print(day)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}


for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1-1])].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
conduct=set([])
q=[]
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.append(key)
sub=[]
heapq.heapify(q)
heapq.heapify(sub)
while q:
    while q:
        x=heapq.heappop(q)
        for n in _to[x]:
            if conduct>=_from[n]:
                conduct.add(n)
                heapq.heappush(sub,n)
        if not q:
            q=sub
            sub=[]
            heapq.heapify(sub)
            day+=1
            break

if conduct==set(node):
    print(day)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

n = int(input())
pair = []
for i in range(n):
    for j in range(i + 1,n):
        pair.append((i,j))

G = {i:set() for i in pair}
inedge = {i:0 for i in pair}
for i in range(n):
    a = [int(i) - 1 for i in input().split()]
    for j in range(n - 2):
        if i <= a[j] and i <= a[j + 1]:
            G[(i,a[j])].add((i,a[j + 1]))
            inedge[(i,a[j + 1])] += 1
        elif i <= a[j] and i > a[j + 1]:
            G[(i,a[j])].add((a[j + 1],i))
            inedge[(a[j + 1],i)] += 1
        elif i > a[j] and i <= a[j + 1]:
            G[(a[j],i)].add((i,a[j + 1]))
            inedge[(i,a[j + 1])] += 1
        else:
            G[(a[j],i)].add((a[j + 1],i))
            inedge[(a[j + 1],i)] += 1
    
visited = {i:0 for i in pair}
finished = {i:0 for i in pair}
print(G)

flag = 1
def dfs(node): #サイクルの検出用
    global flag
    visited[i] = 1
    for e in G[node]:
        if finished[node]:
            continue
        if visited[node] and finished[node] == 0:
            flag = 0
            return
        dfs(e)
    if flag == 0:
        return
    finished[node] = 1

dfs((0,1))
    
if flag == 1:
    st = deque()
    dist = {i:-1 for i in pair}
    for i in pair:
        if inedge[i] == 0:
            st.append(i)
            dist[i] = 1
        
    while len(st):
        node = st.pop()
        for e in G[node]:
            dist[e] = max(dist[e],dist[node] + 1)
            inedge[e] -= 1
            if inedge[e] == 0:
                st.append(e)  
    print(dist) 
    print(max(dist.values()))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())

A = [0]*n
for i in range(n):
    a = list(map(int, input().split()))
    a = [a_-1 for a_ in a]
    A[i] = a

g = [[] for i in range(n*(n-1)//2)]
id = [[[-1] for i in range(n)] for j in range(n)]

temp = 0
for i in range(n-1):
    for j in range(i+1, n):
        id[i][j] = temp
        id[j][i] = temp
        temp += 1

for i in range(n):
    for j in range(n-2):
        g[id[i][A[i][j]]].append(id[i][A[i][j+1]])

visit = [-1]*(n*(n-1)*2)
clc = [-1]*(n*(n-1)*2)
dp = [1]*(n*(n-1)*2)
def dfs(v):
    if visit[v] != -1:
        if clc[v] == -1:
            return -1
        return dp[v]
    visit[v] = 0
    for u in g[v]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res+1)
    clc[v] = 0
    return dp[v]

ans = 0
for i in range(n*(n-1)//2):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def dfs(node, EdgeTo, Visited):
    if node not in EdgeTo:
        Visited[node] = 1
        return 1
    else:
        if Visited[node] > -1: return Visited[node]
        else:
            maxLength = 0
            for nn in EdgeTo[node]: maxLength = max(maxLength, dfs(nn, EdgeTo, Visited))
            Visited[node] = maxLength + 1
            return maxLength + 1

def dfsPassed(node, EdgeTo, Passed):
    if node not in EdgeTo: return True
    nPassed = Passed | {node}
    for nn in EdgeTo[node]:
        if dfsPassed(nn, EdgeTo, nPassed) and nn not in Passed: continue
        else: return False
    return True

def solve():
    input = sys.stdin.readline
    N = int(input())
    EdgeTo = dict()
    Start = []
    Visited = dict()
    for i in range(N):
        a = [int(j) for j in input().split()]
        Start.append((min(i, a[0] - 1), max(i, a[0] - 1)))
        now = (min(i, a[0] - 1), max(i, a[0] - 1))
        for j in range(N - 2):
            if now in EdgeTo: EdgeTo[now].append((min(i, a[j + 1] - 1), max(i, a[j + 1] - 1)))
            else: 
                EdgeTo[now] = [(min(i, a[j + 1] - 1), max(i, a[j + 1] - 1))]
                Visited[now] = -1
            now = (min(i, a[j + 1] - 1), max(i, a[j + 1] - 1))
        if now not in Visited: Visited[now] = -1

    Ans = 0
    for node in Start:
        try:
            dfsPassed(node, EdgeTo, set())
            Ans = max(Ans, dfs(node, EdgeTo, Visited))
        except RecursionError: 
            print(-1)
            break
    else: print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

children = [[] for _ in range(N)]
for x, y in xys:
    children[x-1].append(y-1)

has_no_parent = [True] * N
has_no_child = [True] * N
for x, y in xys:
    has_no_child[x-1] = False
    has_no_parent[y-1] = False

lp = [None] * N
for node in range(N):
    if has_no_child[node]:
        lp[node] = 0

def dp(node):
    if lp[node] is not None:
        return lp[node]
    result = max([dp(child) + 1 for child in children[node]])
    lp[node] = result
    return result

for node in range(N):
    if lp[node] is None:
        dp(node)

print(max(lp))

Submission status: Runtime Error

Solution code:
import numpy as np

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


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

adj = [[] for _ in range(match_sm)]
in_deg = np.zeros(match_sm, dtype=np.int16)
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [i for i, e in enumerate(in_deg) if e == 0]
day = 0
while cnd:
    in_deg[cnd] -= 1
    for u in cnd:
        in_deg[adj[u]] -= 1

    cnd = np.where(in_deg == 0)[0]
    day += 1

if not in_deg.all(0):
    day = -1

print(day)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [[[] for i in range(n)] for i in range(n)]
c = 0
day = 0
for i in range(n):
    ap = [i,a[i][0]-1]
    ap.sort()
    for j in range(1,n-1):
        p = [i,a[i][j]-1]
        p.sort()
        l[ap[0]][ap[1]].append(p)
        ap = p
rl = [[[0,0] for i in range(n)] for i in range(n)]
d = deque()
for i in range(n):
    for j in range(n):
        if i < j:
            if len(l[i][j]) > 0:
                for k in l[i][j]:
                    rl[k[0]][k[1]][0] += 1
#print(rl)
for i in range(n):
    for j in range(n):
        if i < j:
            if rl[i][j][0] == 0:
                d.append([[i,j],0])
al = []
key = 0
#print(l)
if len(d) == 0:
    key = 1
while len(d):
    #print(d)
    now,day = d.pop()
    day += 1
    if len(l[now[0]][now[1]]) == 0:
        al.append(day)
    else:
        for i in l[now[0]][now[1]]:
            if rl[i[0]][i[1]][0] == 1:
                rl[i[0]][i[1]][0] -= 1
                d.append([i,max(day,rl[i[0]][i[1]][1])])
            else:
                rl[i[0]][i[1]][0] -= 1
                rl[i[0]][i[1]][1] = max(day,rl[i[0]][i[1]][1])
    if day > n*(n-1)//2:
        key = 1
        break
md = 0
for i in range(n):
    md += sum(rl[i][0])
if key == 1 or md > 0:
    print(-1)
else:
    print(max(al))

Submission status: Runtime Error

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

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

ans = 0
match = N*(N-1)//2
player = set(range(N))
seen = [False]*N

while True:
    update = False
    checked = seen.copy()
    ans += 1

    for x in player:
        if checked[x] or not A[x]:
            continue
        y = A[x][-1] - 1
        if A[y][-1]-1 == x and not checked[y]:
            A[x].pop()
            A[y].pop()
            checked[x] = True
            checked[y] = True
            update = True
            match -= 1

    if match <= 0:
        break

    if not update:
        ans = -1
        break

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1
    if ans>1000:
    	flag=False
        semi=True
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
  	print(-1)
  else:
    print(499500)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
num = N*(N-1)//2

def ctn(i,j):###combination to number
    if i<j:
        return i + j*(j-1)//2
    else:
        return j + i*(i-1)//2

data = [[] for i in range(num)]

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

search = [0] * num###各点を始点とする最長パス長を記録
visit = [0] * num###閉路検出のため, すでに訪れた頂点を記録

def dfs(i):
    if visit[i] == 1 and search[i] == 0:
        ###すでに来たのに最大パス長が求まっていないのは
        ###閉路があるから
        print(-1)
        sys.exit()
    elif data[i] == []:
        ret = 1
        visit[i] = 1
        search[i] = 1
    else:
        visit[i] = 1
        ret =  max([dfs(j) for j in data[i]]) + 1
        search[i] = ret
    
    return ret

for i in range(num):###点iを始点とする最長パス長を調べる
    if search[i] > 0:
        continue
    else:
        d = dfs(i)
        search[i] = dfs(i)

if d == -1:
    print(-1)
else:
    print(max(search))

Submission status: Runtime Error

Solution code:
import sys

N = int(input())
num = N*(N-1)//2

def ctn(i,j):###combination to number
    if i<j:
        return i + j*(j-1)//2
    else:
        return j + i*(i-1)//2

data = [[] for i in range(num)]

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

search = [0] * num###各点を始点とする最長パス長を記録
visit = [0] * num###閉路検出のため, すでに訪れた頂点を記録

def dfs(i):
    if visit[i] == 1 and search[i] == 0:
        ###すでに来たのに最大パス長が求まっていないのは
        ###閉路があるから
        print(-1)
        sys.exit()
    elif data[i] == []:
        ret = 1
        visit[i] = 1
        search[i] = 1
    #elif search[i] >= 0:
    #    ret = search[i]
    else:
        visit[i] = 1
        ret =  max([dfs(j) for j in data[i]]) + 1
        search[i] = ret
    
    #print(search)
    #print(visit)
    return ret

det = 0
for i in range(num):###点iを始点とする最長パス長を調べる
    if search[i] > 0:
        continue
    else:
        d = dfs(i)
        if d == -1:
            break
        else:
            search[i] = dfs(i)

if d == -1:
    print(-1)
else:
    print(max(search))