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:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        cur = 0
        while q and cur<n+1:
            cur += 1
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        if q:
            return []
        return res

    def dfs(n, e, edges):
        result = 0
        for i in edges[e]:
            t = dfs(n, i, edges)
            if t > result:
                result = t
        result += 1
        return result

    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    A = [LI() for _ in range(N)]
    D = defaultdict(int)
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[(i,j)] = cur
            D[(j,i)] = cur
            cur += 1
    ins = [0]*node
    for i in range(N):
        a = A[i]
        for j in range(N-2):
            fr = D[(i,a[j]-1)]
            to = D[(i,a[j+1]-1)]
            #print(fr,to)
            V[fr].append(to)
            ins[to] += 1
    #print(V)
    #print(ins)
    Order = topological_sort(node, V, ins)
    #print(Order)
    if not Order:
        print(-1)
        return
    start = Order.index(0)
    ans = dfs(node,start,V)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Runtime Error

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res

    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne]<nowW+1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    A = [LI() for _ in range(N)]
    D = defaultdict(int)
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[(i,j)] = cur
            D[(j,i)] = cur
            cur += 1
    ins = [0]*node
    for i in range(N):
        a = A[i]
        for j in range(N-2):
            fr = D[(i,a[j]-1)]
            to = D[(i,a[j+1]-1)]
            #print(fr,to)
            V[fr].append(to)
            ins[to] += 1
    #print(V)
    #print(ins)
    Order = topological_sort(node, V, ins)
    #print(Order)
    if not Order:
        print(-1)
        return
    start = Order.index(0)
    ans = max(bfs(node,start,V))+1
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Runtime Error

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    def dfs(n,s,edges):
        if not edges[s]:
            return 1
        now = 0
        for i in edges[s]:
            now = max(now,dfs(n,i,edges)+1)
        return now
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    A = [LI() for _ in range(N)]
    D = defaultdict(int)
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[(i,j)] = cur
            D[(j,i)] = cur
            cur += 1
    ins = [0]*node
    for i in range(N):
        a = A[i]
        for j in range(N-2):
            fr = D[(i,a[j]-1)]
            to = D[(i,a[j+1]-1)]
            #print(fr,to)
            V[fr].append(to)
            ins[to] += 1
    #print(V)
    #print(ins)
    Order = topological_sort(node, V, ins)
    #print(Order)
    if not Order:
        print(-1)
        return
    start = Order.index(0)
    ans = dfs(node,start,V)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Runtime Error

Solution code:
import sys
import copy
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

answer = 0
match = 0

candidate = list(range(N))
while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1            
            bool = True
            A[i].popleft()
            A[op].popleft()
            if A[i]: c.append(i)
            if A[op]: c.append(op)

    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque

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

Q = deque(range(N))

days = [0]*N  # 各選手の現在の日付
pairs = [0]*N  # 次の対戦相手を管理(wait的な)

while Q:
    x = Q.popleft()  # 試合する人
    if len(matches(x)) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x].pop(0)  # xの次の対戦相手
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        Q.append(x)
        Q.append(y)
    else:
        pairs[x] = y

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)

Submission status: Runtime Error

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


def topological_sort(V, E_in, E_from):
    '''
    # Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


E_in = defaultdict(lambda: set())
E_from = defaultdict(lambda: set())

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        E_from[make_hash(i, node_to)].add(make_hash(i, node_from))
        E_in[make_hash(i, node_from)].add(make_hash(i, node_to))

START = set()
END = set()
for i in range(N):
    for j in range(i+1, N):
        if len(E_in[i]) == 0:
            START.add(i)
        if len(E_from[i]) == 0:
            END.add(i)
if len(START) == 0 or len(END) == 0:
    print(-1)
else:
    top = topological_sort(N**2, E_from=E_from, E_in=E_in)
    dist = defaultdict(int)
    for t in top:
        for nex in E_from[t]:
            dist[nex] = max(dist[nex], dist[t]+1)
    print(max(dist.values())+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
#print("pointed", list([un_hash(key), val] for key, val in pointed.items()))
#print("pointing", list([un_hash(key), val] for key, val in pointing.items()))
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(i)
        if pointing_i == 0:
            DST.add(i)
if len(START) == 0 or len(DST) == 0:
    print(-1)
else:
    assert 1 == 2

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
for i in range(N):
    pointed_i = pointed[i]
    pointing_i = pointing[i]
    if pointed_i == 0:
        START.add(i)
    if pointing_i == 0:
        DST.add(i)
if len(START) == 0 or len(DST) == 0:
    print(-1)
else:
    print(ok)

Submission status: Runtime Error

Solution code:
 N = int(input())
A = [[]]
for i in range(N):
    a = list(map(int,input().split()))
    A.append(a)
ans = 0
n = 0
while n < ((N-1)*N)//2:
    f = []
    ans += 1
    t = 0
    for i in range(1,N+1):
        if i in f:
            continue
        if len(A[i]) > 0:
            a = A[i][0]
        else:
            continue
        if (A[a][0] == i):
            if a not in f:
                A[i].pop(0)
                A[a].pop(0)
                f.append(i)
                f.append(a)
                n += 1
                t = 1
    if t == 0:
        print(-1)
        quit()
print(ans)

Submission status: Runtime Error

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [rl().reverse() for _ in range(N)]
answer = 0
match = 0
while A:
    bool = False
    for i in range(N):
        op = A[i][-1] - 1
        if op > i and A[op] == i:
            match += 1
            bool = True
            A[i].pop()
            A[op].pop()
    if not bool:
        print(-1)
        exit()
    answer += 1
    if match == N * (N-1) // 2:
        break

print(answer)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
 
to = [[] for _ in range(MAXV)]
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)]
 
def toId(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]
visited = [False] * MAXV
calculated = [False] * MAXN
dp = [1] * MAXV
 
def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
 
    for u in to[v]:
        res = dfs(u)
        if res == -1: return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]
 
def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1
    
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n-2):
            to[a[i][j+1]].append(a[i][j])
    
    ans = 0
    
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1')
            return
        ans = max(ans, res)
    print(ans)
    return
  
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

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

def toId(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]
visited = [False] * MAXV
calculated = [False] * MAXN
dp = [1] * MAXV

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1

    for u in to [v]:
        res = dfs(u)
        if res == -1: return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n-2):
            to[a[i][j+1]].append(a[i][j])
    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1')
            return
        ans = max(ans, res)
    print(ans)
    return
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
MAXN=1005
MAXV=N*(N-1)//2

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

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

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

to=[[] for i in range(MAXV)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for 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]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(v):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

Submission status: Runtime Error

Solution code:
N=int(input())
MAXN=N+5
MAXV=N*(N-1)//2

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

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

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

to=[[] for i in range(MAXV)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for 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]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(v):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

Submission status: Runtime Error

Solution code:
N=int(input())
MAXN=N+5
MAXV=N*(N-1)//2

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

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

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

to=[[] for i in range(MAXV)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for 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]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(MAXV):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

Submission status: Runtime Error

Solution code:
N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

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

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

to=[[] for i in range(N*(N+1)//2)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for i in range(N*(N-1)//2)]
calculated=[False for i in range(N*(N-1)//2)]
dp=[0 for i in range(N*(N-1)//2)]

def dfs(v):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(N*(N-1)//2):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate

def main():
	input = sys.stdin.readline
	n = int(input())
	d = [list(accumulate(map(int, input().split()))) + [0] for _ in range(n)] + [[0] * (n + 1)]
	for j in range(n):
		for i in range(n - 1):
			d[i + 1][j] += d[i][j]

	def divisors(x):
		ret = []
		for i in range(1, x + 1):
			if i > n:break
			if x % i == 0 and x // i <= n:
				ret += [(i - 1, x // i - 1)]
		return ret

	ref = [0 if not divisors(z) else max(d[i + y][j + x] - d[i - 1][j + x] - d[i + y][j - 1] + d[i - 1][j - 1] for x, y in divisors(z) for i in range(n - y) for j in range(n - x)) for z in range(n * n + 1)]
	ref = list(accumulate(ref, max))
	print("\n".join(map(str, [ref[int(input())] for _ in range(int(input()))])))

if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

from collections import deque

n = int(input())

a = [[int(i) for i in input().split()] for j in range(n)]

check = [0]*n
used = [False]*n

d = deque()

for i in reversed(range(n)):
    if used[i] == True:
        continue
    if a[a[i][0]-1][0] == i+1:
        d.appendleft([i+1,a[i][0]])
        used[i] = True
        used[a[i][0]-1] = True
        check[i] = 1
        check[a[i][0]-1] = 1
        
ans = 0

if len(d) == 0:
    print(-1)
    exit()

#print(d)

while len(d) > 0:
    used = [False]*n
    ans += 1
    num = len(d)
    for i in range(num):
        tmp = d.popleft()
        for j in range(2):
            if check[tmp[j]-1] == n-1:
                continue
            psn = a[tmp[j]-1][check[tmp[j]-1]]-1
            mys = tmp[j]-1
            
            if check[mys] == n-1 or check[psn] == n-1:
                continue
            #print(tmp,psn,a[psn][check[psn]])
            #print(i,j,tmp,psn,check[mys],check[psn])
            if used[mys] == True or used[psn] == True:
                continue

            if a[psn][check[psn]] == mys+1:
                d.append([psn+1,mys+1])
                used[mys] = True
                used[psn] = True
                check[mys] += 1
                check[psn] += 1
    #print(d)
    
for i in range(n):
    if check[i] != n-1:
        print(-1)
        exit()

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[[] for i in range(N)]
Aflag=[N-1]*N
for i in range(N):
  A[i]=list(map(int,input().split()))
M=0
flag=0
while(1):
  M+=1
  bflag=[0]*N
  prAflag=Aflag.copy()
  for i in range(N-1):
    if Aflag[i]>0:
      k=A[i][N-1-Aflag[i]]-1
      l=A[k][N-1-Aflag[k]]-1
      if bflag[i]==0 and bflag[k]==0 and i==l:
        Aflag[i]-=1
        Aflag[k]-=1
        bflag[i]=1
        bflag[k]=1
  if sum(Aflag)==0:
    flag=1
    break
  if prAflag==Aflag:
    flag=0
    break
if flag==0:
  print(-1)
else:
  print(M)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())

match = [[-1] * (N) for _ in range(N)]
c = 0
for i in range(N):
    for j in range(i+1, N):
        match[i][j] = c
        c += 1


def get_id(i, j):
    if i > j:
        i, j = j, i
    return match[i][j]


start = []
G = {k: [] for k in range(c)}
for i in range(N):
    L = map(int, input().split())
    pid = -1
    for i, l in enumerate(L):
        id = get_id(i, l-1)
        if i == 0:
            start.append(id)
        else:
            G[pid].append(id)
        pid = id

visited = [False]*c
calculated = [False]*c
dp = [-1]*c


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nxt in G[v]:
        if visited[nxt] is True and calculated[nxt] is False:
            print(-1)
            exit()
        d = dfs(nxt)
        if d >= dp[v]:
            dp[v] = d+1
    calculated[v] = True
    return dp[v]


ans = 0
for i in start:
    res = dfs(i)
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
flag = 0
for i in range(N):
    A.append(list(map(int,input().split())))
A_cnt = [0 for i in range(N)]
A_cnt_copy = [0 for i in range(N)]
day = 0
def League():
    for i in range((N*(N-1))//2):
        for j in range(N):
            try:
                index = A[j][A_cnt[j]]-1
                if j<index and A[index][A_cnt[index]]-1==j:
                    A_cnt_copy[j]+=1
                    A_cnt_copy[index]+=1
                    flag = 1
            except:
                pass
        A_cnt = A_cnt_copy[:]
        if flag == 1:
            day+=1
            flag = 0

League()

if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
side = [[[]for _ in range(N)]for _ in range(N)] 
node = [[1]*N for i in range(N)]
for i in range(N):
    A = list(map(int,input().split()))
    for j in range(N-2):
        a,b = min(i,A[j]-1),max(i,A[j]-1)
        c,d = min(i,A[j+1]-1),max(i,A[j+1]-1)
        side[a][b].append([c,d])
        node[c][d] = 0
def DFS(x,y,l):
    if l > N**2:
        print(-1)
        exit()
    ret = l
    for i,j in side[x][y]:
        ret = max(ret, DFS(i,j,l+1))
    return ret


ans = 0
for i in range(N):
    for j in range(i+1,N):
        if node[i][j]:
            ans = max(DFS(i,j,1),ans)
if ans:
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = collections.defaultdict(list)
        while True:
            if len(ql) != 0:
                d, ps = ql.popleft()
                if d == i:
                    if ps not in fq:
                        nw = a[ps][ls[ps]]
                        if nw not in fq:
                            rw = a[nw][ls[nw]]
                            if ps == rw:
                                fq[ps]
                                fq[nw]
                                ls[ps] += 1
                                ls[nw] += 1
                                if ls[ps] < n - 1:
                                    ql.append([d+1, ps])
                                if ls[nw] < n - 1:
                                    ql.append([d+1, nw])
                else:
                    ql.appendleft([d, ps])
                    break
            else:sum(ls) == n * (n - 1):
                    print(i + 1)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if fq[ps]:
                    nw = a[ps][ls[ps]]
                    if fq[nw]:
                        rw = a[nw][ls[nw]]
                        if ps == rw:
                            ql.append([d+1, ps])
                            ql.append([d+1, nw])
                            if ls[ps] < n - 1:
                                ls[ps] += 1
                            if ls[nw] < n - 1:
                                ls[nw] += 1
                            fq[nw] = False
                            fq[ps] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()