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:
from collections import deque
from typing import List, Optional, Tuple


def cycle_detectable_topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Tuple[Optional[List[int]], Optional[List[int]]]:
    """Topological sort that uses Kahn's algorithm and detects a loop (DAG or not).
    Returns:
        if the given graph is DAG, a list of sorted vertices and a list of depths of
        each vertex is returned.
        Otherwise, (None, None) is returned.
    """
    V = len(graph) + first_index
    order = []
    depths = [-1] * V  # depths[i] := the length of the longest path to V_i
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

    queue = deque(order)
    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = max(depths[v], cur_depth + 1)
                queue.append(v), order.append(v)
    return (order, depths) if len(order) + first_index == V else (None, None)


def abc139_e():
    N, *A = map(int, open(0).read().split())

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

    graph = [[] for _ in range(N * (N - 1) // 2)]
    in_degrees = [0] * (N * (N - 1) // 2)
    for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
        prev_id = -1
        for j in a:
            cur_id = ids[i][j]
            if prev_id != -1:
                graph[prev_id].append(cur_id)
                in_degrees[cur_id] += 1
            prev_id = cur_id

    _, depths = cycle_detectable_topological_sort(graph, in_degrees, 1)
    print(max(depths) + 1 if depths is not None else -1)


if __name__ == "__main__":
    abc139_e()

Submission status: Runtime Error

Solution code:

def toId(i, j):
    return id[min(i, j)][max(i, j)]


visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV


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


a = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    for j in range(N-1):
        a[i][j] -= 1
vid = 0
for i in range(N):
    for j in range(N):
        if i < j:
            id[i][j] = vid
            vid += 1

# プレイヤーiの試合の依存関係の情報をグラフ化
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(vid):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
to = [[]for _ in range(MAXV)]
id = [[0]*MAXN for _ in range(MAXN)]


def toId(i, j):
    return id[min(i, j)][max(i, j)]


visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV


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


a = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    for j in range(N-1):
        a[i][j] -= 1
vid = 0
for i in range(N):
    for j in range(N):
        if i < j:
            id[i][j] = vid
            vid += 1

# プレイヤーiの試合の依存関係の情報をグラフ化
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
print(vid)

for i in range(N):
    print(a[i])
for i in range(vid):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(vid)
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
m=(n*(n-1))//2
g=[[] for _ in range(m)]
for i in range(n):
  for j in range(n-2):
    if i+1>a[i][j]:
      t0=f((a[i][j],i+1))
    else:
      t0=f((i+1,a[i][j]))
    if i+1>a[i][j+1]:
      t1=f((a[i][j+1],i+1))
    else:
      t1=f((i+1,a[i][j+1]))
    g[t0].append(t1)

def dfs(t):
  if v[t]:
    if c[t]==0:
      return -1
    else:
      dp[t]
  v[t]=1
  for l in g[t]:
    ret=dfs(l)
    if ret==-1:return -1
    dp[t]=max(dp[t],ret+1)
  c[t]=1
  return dp[t]
ans=0
for i in range(m):
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  tmp=dfs(i)
  if tmp==-1:
    print(-1)
    exit()
  ans=max(ans,tmp)
print(ans+1)

Submission status: Runtime Error

Solution code:
class StronglyConnectedComponets:
    def __init__(self, n: int) -> None:
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.rev_edeges = [[] for _ in range(n)]
        self.vs = []
        self.cmp = [0] * n
        self.used = [False] * n

    def add_edge(self, from_v: int, to_v: int) -> None:
        self.edges[from_v].append(to_v)
        self.rev_edeges[to_v].append(from_v)

    def dfs(self, v) -> None:
        self.used[v] = True
        for child in self.edges[v]:
            if not self.used[child]:
                self.dfs(child)
        self.vs.append(v)

    def rdfs(self, v, k) -> None:
        self.used[v] = True
        self.cmp[v] = k
        for child in self.rev_edeges[v]:
            if not self.used[child]:
                self.rdfs(child, k)

    def run(self) -> int:
        self.used = [False] * self.n
        self.vs.clear()
        for v in range(self.n):
            if not self.used[v]:
                self.dfs(v)
        self.used = [False] * self.n
        k = 0
        for v in reversed(self.vs):
            if not self.used[v]:
                self.rdfs(v, k)
                k += 1
        return k

    def create_order(self) -> list:
        order = [0] * self.n
        for i, c in enumerate(self.cmp):
            order[c] = i
        return order


def main() -> None:
    N = int(input())
    map_dict = {}
    rev_map = []
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            map_dict[i, j] = map_dict[j, i] = cnt
            rev_map.append((i, j))
            cnt += 1
    scc = StronglyConnectedComponets(cnt)

    for i in range(N):
        orders = [int(x) - 1 for x in input().split()]
        for x, y in zip(orders[:-1], orders[1:]):
            match1 = map_dict[i, x]
            match2 = map_dict[i, y]
            scc.add_edge(match1, match2)
    n_cc = scc.run()
    if n_cc != cnt:
        print(-1)
        return

    order = scc.create_order()
    # print(order)
    dp = [1] * cnt
    for v in order:
        for c in scc.edges[v]:
            dp[c] = max(dp[c], dp[v] + 1)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def pair2index(i, j, N):
    return N * i + j


def main():
    N = int(input())
    adj = defaultdict(list)
    for i in range(N):
        A = list(map(lambda x: int(x) - 1, input().split(' ')))
        for j in range(1, N - 1):
            a = A[j - 1]
            from_index = pair2index(min(i, a), max(i, a), N)
            a = A[j]
            to_index = pair2index(min(i, a), max(i, a), N)
            adj[from_index].append(to_index)

    temp_visited = [0 for _ in range(N**2)]
    max_depth = [0 for _ in range(N**2)]

    def dfs(n):
        if temp_visited[n] == 1:
            # 閉路あり
            max_depth[n] = -1
            return -1
        elif max_depth[n] != 0:
            return max_depth[n]
        else:   # max_depth[n] == 0 (未探索)
            temp_visited[n] = 1
            max_d = 0
            for next_n in adj[n]:
                d = dfs(next_n)
                if d == -1:
                    return d
                max_d = max(max_d, d)
            temp_visited[n] = 0
            max_depth[n] = max_d + 1
            return max_d + 1

    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            node = pair2index(i, j, N)
            depth = dfs(node)
            if depth == -1:
                print(-1)
                return
            ans = max(ans, depth)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))

Submission status: Runtime Error

Solution code:
def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    loops = 0
    yest_players = set([i for i in range(N)])
    while loops < 10**5:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in yest_players:
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        yest_players = todays_players
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
        loops += 1
    assert loops < 10**5, "error"
    print(day)





if '__main__' == __name__:
    resolve()

Submission status: Runtime Error

Solution code:
def main():
 	import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    flag = [True]*N
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    if Lock[A[i][id[i]]-1] == i and i not in tmp:
                        Lock[A[i][id[i]]-1] = -1
                        id[A[i][id[i]]-1] += 1
                        tmp.add(A[i][id[i]]-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = []
for i in range(n):
    rs = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(rs)

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts, A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    days > 50000:
        print(-1)
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Runtime Error

Solution code:
# E - League
import sys
from collections import deque
from typing import Deque, List

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A: List[Deque[int]] = [deque()] + list(
        deque(map(int, line.split())) for line in readlines()
    )
    matched_games_cnt = 0
    next_games_opponent, last_games_day = [0] * (N + 1), [0] * (N + 1)
    queue = deque(list(range(1, N + 1)))
    while queue:
        player = queue.popleft()
        if not A[player]:  # The player has finished all games.
            continue
        opponent = A[player].popleft()

        # The opponent will have another game before playing against x.
        if next_games_opponent[opponent] != player:
            next_games_opponent[player] = opponent
            continue

        # The opponent's next game is against the player and vice versa.
        matched_games_cnt += 1
        last_games_day[player] = last_games_day[opponent] = (
            max(last_games_day[player], last_games_day[opponent]) + 1
        )
        # No next game is currently planned.
        next_games_opponent[player] = next_games_opponent[opponent] = 0
        queue.append(player), queue.append(opponent)

    print(max(last_games_day) if matched_games_cnt == N * (N - 1) // 2 else -1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from numba import njit

@njit('(i4,i4[:])',cache=True)
def solve(N,A):
    cur = np.zeros(N,np.int32)
    for i in range(N*(N-1)//2):
        already = np.zeros(N,np.int32)
        for j in range(N):
            if already[j]:
                continue
            k = A[j][cur[j]]-1
            if already[k]:
                continue
            if A[k][cur[k]]-1 == j:
                already[j] = 1
                already[k] = 1
                cur[j] += 1
                cur[k] += 1
        for j in range(N):
            if cur[j] != N-1:
                break
        else:
            return i+1
    return -1

N = int(readline())
A = np.zeros((N,N),np.int32)
for i in range(N):
    A[i][:-1] = np.array(readline().split(),np.int32)
    A[i][-1] = -1
print(solve(N,A))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def pre_order(E):
    # 有向グラフ上の深さ優先探索(DFS)
    # NlogNくらいありそう
    N = len(E)
    order = []
    parents = [-1]*N
    seen = [-1]*N
    looped = False
    q = [i for i in range(N) if len(E[i]) == 0]
    if not q:
        # これはループがあるケースだが
        q = [0]
        looped = True

    while q:
        v = q.pop()
        order.append(v)
        seen[v] = 1
        for u in E[v]:
            if seen[u] != -1:
                looped = True
                continue
            parents[u] = v
            q.append(u)
            seen[u] = 0
    return order, parents


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

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = [[] for _ in range(N*(N-1)//2)]
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            # fで書いていたけど遅いので、移す
            frm = f(i, A[i][j])
            to = f(i, A[i][j+1])
            out[frm].append(to)
    # print(out)

    # 閉路検出
    M = (N*(N-1)//2)

    order, parents, looped = pre_order(out)
    if looped:
        print(-1)
        return

    # 最長パスを得る
    # パスは自分より下位の情報が必要なので、post_orderで見る
    depth = [-1]*M
    longest = -1

    for i in reversed(order):
        if depth[i] == -1:
            depth[i] = 1
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())

def dfs(g,d,O):
  if d<N:
    m=-1
    if len(O[g])==0:
      return d+1
    for i in O[g]:
      m=max(m,dfs(i,d+1,O))
      if m>N:
        break
    return m
  else:
    return N+1

def main():
  I=[[] for i in range(N*~-N//2)]
  O=[[] for i in range(N*~-N//2)]

  for i in range(N):
    pv=-1
    for j in [int(x)-1 for x in input().split()]:
      v=j*~-j//2+i if i<j else i*~-i//2+j
      if pv!=-1:
        I[v].append(pv)
        O[pv].append(v)
      pv=v

  m=-1
  for s in range(N*~-N//2):
    if len(I[s])!=0:
      continue
    m=max(m,dfs(s,0,O))
    if m>N:
      print(-1)
      exit(0)
  print(m)

main()

Submission status: Runtime Error

Solution code:
#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意

n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)

##キューの管理のどこがおかしいかわからなかったがあきらめる

can={i for i in range(n)}
nxt=set()
Done = set()
cnt = 0
rem=n*(n-1)//2
while rem:
    cnt+=1
    for i in can:
        if i not in Done and a[i]:
            p = a[i][-1]
            if p not in Done:##この判定しないと1日に複数回試合することになる
                if a[p][-1]==i:
                    a[p].pop();a[i].pop()
                    Done.add(p);Done.add(i)
                    rem-=1
                    nxt.add(i);nxt.add(p)
            
    can=nxt;Done=set()
    if not can:
        break
       
if rem:
    print(-1)
else:       
    print(cnt)

Submission status: Runtime Error

Solution code:
#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意
from collections import deque
import sys

n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)

Q = deque()
for i in range(n):
    Q.append(i)

#nは番兵
Q.append(n)
Done = set()
cnt = 1
while len(Q)>1:
    i = Q.popleft()
    if i==n:
        cnt += 1
        Q.append(n)
        Done=set()###
    if i<n and a[i]:
        p = a[i].pop()
        if p not in Done:##この判定しないと1日に複数回試合することになる
            if a[p][-1]==i and i not in Done:###
                Q.append(i)
                Q.append(p)
                a[p].pop()
                Done.add(p)###
                Done.add(i)
            else:#戻す
                a[i].append(p)
        # else:
        #     Done.remove(p)
        
for i in range(n):
    if len(a[i])>0:
        print(-1)
        sys.exit()
        
print(cnt)

Submission status: Runtime Error

Solution code:
#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意
from collections import deque
import sys

n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)

Q = deque()
for i in range(n):
    Q.append(i)

#nは番兵
Q.append(n)
Done = set()
cnt = 1
while len(Q)>1:
    i = Q.popleft()
    if i==n:
        cnt += 1
        Q.append(n)
        Done=set()###
    if i<n and a[i]:
        p = a[i].pop()
        if p not in Done:##この判定しないと1日に複数回試合することになる
            if a[p][-1]==i and i not in Done:###
                Q.append(i)
                Q.append(p)
                a[p].pop()
                Done.add(p)###
                Done.add(i)
            else:#戻す
                a[i].append(p)
        else:
            Done.remove(p)
        
for i in range(n):
    if len(a[i])>0:
        print(-1)
        sys.exit()
        
print(cnt)

Submission status: Runtime Error

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

def main():
    N = int(input())
    memo = []
    base = 0
    for i in range(N-1):
        memo.append(base)
        base += N-i-1
    edge = [[] for _ in range((N*(N-1))//2)]
    
    for i in range(N):
        a = list(map(int,input().split()))
        b = []
        for j in a:
            j -= 1
            if i < j:
                b.append(memo[i]+j-i-1)
            else:
                b.append(memo[j]+i-j-1)
        for i in range(N-2):
            edge[b[i+1]].append(b[i])

    go = [False]*((N*(N-1))//2)
    cul = [False]*((N*(N-1))//2)
    dp = [0]*((N*(N-1))//2)
    
    def dfs(v):
        if go[v]:
            if not cul[v]:
                return -1
            return dp[v]
        go[v] = True
        dp[v] = 1
        for u in edge[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v],ret+1)
        cul[v] = True
        return dp[v]
    
    ans = 0
    for i in range((N*(N-1))//2):
        ret = dfs(i)
        if ret == -1:
            print(-1)
            exit()
        ans = max(ans,ret)
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
previous=set()
for i in range(n):
  previous.add(i)
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in previous:
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  previous=set()
  for k in r:
    m[k].pop()
    previous.add(k)
    if m[k]:
      previous.add(m[k][-1])
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
previous=set()
for i in range(n):
  previous.add(i)
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in previous:
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  previous=set()
  for k in r:
    m[k].pop()
    previous.add(k)
    previous.add(m[k][-1])
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
previous=set()
for i in range(n):
  previous.add(i)
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in previous:
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  previous=()
  for k in r:
    m[k].pop()
    previous.add(k)
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
adjacent_list = [[] for i in range((n + 2) * n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        pre = tmp[j] - 1
not_candidate = set([])
for i in range((n + 2) * n):
    if len(adjacent_list) == 0:
        not_candidate.add(i)
        continue
    for j in adjacent_list[j]:
        not_candidate.add(j)
#まず、閉路検
seen = [False for i in range((n + 2) * n)]
visited = [False for i in range((n + 2) * n)]
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in range((n + 2) * n):
    check(i)
finish = defaultdict(int)
for i in range((n + 2) * n):
    if i not in not_candidate :
        dfs_path(i)
print(max(finish.values(), 1))

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
from time import time

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

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

while True:
    isChanged = False
    i, a = A.popleft()
    if not a:
        continue
    A.append((i, a))
    j = a[0]
    canBattle[(i, j)] = True

    if canBattle[(j, i)]:
        isChanged = True
        A[i].popleft()
        A[j].popleft()
        d = max(D[i], D[j])
        D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
N=int(input())
table=[]
for i in range(N):
    d=deque()
    l=list(map(int,input().split()))
    for j in range(N-1):
        d.append(l[j]-1)
    table.append(d)
#print(table)
day=0
allnone=0
#print(1==None)
breakflag=0
flag=1
while breakflag==0:
    seen=[0]*N
    d1=deque()
    d2=deque()
    allnone=0
    breakflag = 1
    for i in range(N):
        t1 = None
        t2 = None
        d1=table[i]
        if len(d1)>0:
            t1=d1.popleft()
            d2=table[t1]
        if len(d2)>0:
            t2=d2.popleft()
        #print(i,t1,t2)
        if (i==t2):             #pairを作れる時
            if t1!=None:        #t1は値がある時
                if (seen[i]==0)and(seen[t1]==0):
                    seen[i]=1
                    seen[t1]=1
                    breakflag=0
                else:
                    if t1 != None:
                        table[i].appendleft(t1)
                    if t2 != None:
                        table[t1].appendleft(t2)
            else:
                if t1 != None:
                    table[i].appendleft(t1)
                if t2 != None:
                    table[t1].appendleft(t2)
        else:
            if t1!=None:
                table[i].appendleft(t1)
            if t2!=None:
                table[t1].appendleft(t2)
        #print(table,seen)
        #input()
    day=day+1
for i in range(N):
    if len(table[i])>0:
        flag=0
    break
if flag==0:
    print("-1")
else:
    print(day-1)

Submission status: Runtime Error

Solution code:
from collections import deque
N=int(input())
table=[]
for i in range(N):
    d=deque()
    l=list(map(int,input().split()))
    for j in range(N-1):
        d.append(l[j]-1)
    table.append(d)
#print(table)
day=0
allnone=0
#print(1==None)
breakflag=0
flag=1
while breakflag==0:
    seen=[0]*N
    d1=deque()
    d2=deque()
    allnone=0
    breakflag = 1
    for i in range(N):
        t1 = None
        t2 = None
        d1=table[i]
        if len(d1)>0:
            t1=d1.popleft()
            d2=table[t1]
        if len(d2)>0:
            t2=d2.popleft()
        #print(i,t1,t2)
        if (i==t2)and(seen[i]==0)and(seen[t1]==0):
            seen[i]=1
            seen[t1]=1
            breakflag=0
        else:
            if t1!=None:
                table[i].appendleft(t1)
            if t2!=None:
                table[t1].appendleft(t2)
        #print(table,seen)
        #input()
    day=day+1
for i in range(N):
    if len(table[i])>0:
        flag=0
    break
if flag==0:
    print("-1")
else:
    print(day-1)

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(1005)] for i in range(1005)]
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)