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 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()

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 ls[ps] < n - 1 and fq[ps] and fq[nw]:
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
                fq[ps] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0:
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
for i in range(N):
    for j in range(N):
        N[i]
finished=[]
day=0
while True:
    flag = 0
    for i in range(1,N+1):
        if L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                finished.append(i)
                flag = 1
    for i in range(len(finished)): 
        del L[finished[i]][0]
    finished=[]
    if flag == 0:
        for i in range(1,N+1):
            if L[i] != []:
                day=-1
        break
    day+=1
print(day)

Submission status: Runtime Error

Solution code:
import itertools
import sys
import numpy as np
#0-indexed
N = int(input())
A = np.array(sys.stdin.buffer.read().split(), dtype=int).reshape((N, N - 1))
A -= 1
R = np.arange(N)
ans = 0
while True:
    I = (A[A[:, 0]][:, 0] == R) * (A[:, 0] != -1)
    if not I.any():
        break
    ans += 1
    A[I, :-1] = A[I, 1:]
    A[I, -1] = -1
if (A == -1).all():
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import copy
def f(x):
    return int(x) - 1

def g(s):
    s_set = set(s)
    s_list = list(s_set)
    t = set()
    for i in s_list: #リストはforループの最中に要素を削除してもいい。削除するとその削除された要素は無視される。
        j = A[i][0]
        if i == A[j][0]:
            #print(s_list)
            #print(j)
            s_list.remove(i)
            s_list.remove(j)
            s.remove(i)
            s.remove(j)
            A[i].pop(0)
            A[j].pop(0)
            if A[i][0] != - 1:
                s.append(A[i][0])
            if A[j][0] != - 1:
                s.append(A[j][0])
    return s

N = int(input())

A = [list(map(f, input().split())) + [- 1] for i in range(N)]

day = 0

s = [A[i][0] for i in range(N)]

while len(s) > 0:
    t = copy.copy(s)
    g(s)
    if t == s:
        day = - 1
        break
    day += 1
print(day)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())

A = np.zeros((N, N - 1), dtype = 'int')
for i in range(N):
    A[i] = np.array(list(map(int, input().split())))
A -= 1

game = [0]*N# game[i] = 選手iが何試合目まで終了したか

#success_flag = [N - 1]*N
S = set(A[:, 0])

day = 0
while len(S) > 0:
    
    daygame_finish_flag = [False]*N
    game_over = True
    T = set() # Sから削除するもの
    U = set() # Sに追加するもの
    for i in S:
        j = A[i][game[i]]
        if daygame_finish_flag[i] or daygame_finish_flag[j]: #or game[i] == N - 1: #iがすでにその日試合をしていた場合もしくは全試合終わっている場合
            continue
        if i == A[j][game[j]]:
            T |= set([i, j])
            game_over = False
            daygame_finish_flag[i] = True
            daygame_finish_flag[j] = True
            game[i] += 1
            game[j] += 1
            if game[i] < N - 1:
                U.add(A[i][game[i]])
            if game[j] < N - 1:
                U.add(A[j][game[j]])
    if game_over:
        day = - 1
        break
    day += 1
    S = (S - T) | U 
print(day)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
import time
t=time.time()


def main():
    N = int(input().strip())
    A = [[0]] * (N+1)
    for idx in range(1, N+1):
        A[idx] = list(reversed([int(x) for x in input().strip().split()]))

    ans = 0
    end_count = 0
    proc_count = 0
    while True:
        end_count = 0
        proc_count = 0
        for idx in range(1, N+1):
            if len(A[idx]) == 0:
                end_count += 1
                continue
            if A[A[idx][-1]][-1] == idx:
                A[A[idx][-1]][-1] = 0
                A[idx][-1] = 0
                proc_count += 1
        if end_count == N:
            print(ans)
            return
        if proc_count == 0:
            print(-1)
            return
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            return
        for idx in range(1, N+1):
            if len(A[idx]) != 0:
                if A[idx][-1] == 0:
                    A[idx].pop()
        ans += 1


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in range(n)]

    c=0
    while any(map(len,d)):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip.copy():
                #if d[i]:
                if d[i][0] in skip:
                    continue
                elif i==d[d[i][0]][0]:
                    oppo=d[i].popleft()
                    d[oppo].popleft()
                    skip.add(oppo)
                    skip.add(i)
                    f=1
                        
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
import time

#A
def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return

#B
def B():
    a, b = LI()
    ans = 0
    b -= 1
    while b > 0:
        b -= a - 1
        ans += 1
    print(ans)

    return

#C
def C():
    n = II()
    h = LI()
    i = 0
    ans = 0
    while i < n:
        down = i+1
        while down < n:
            if h[down - 1] >= h[down]:
                down += 1
            else:
                break
        ans = max(ans, down - i - 1)
        i = down
    print(ans)
    return

#D
def D():
    n = II()
    print(n * (n - 1) // 2)
    return

#E
def E():
    start = time.time()
    n = II()
    a = LIR_(n)
    ans = 0
    tern = [0] * n
    while 1:
        ans += 1
        f = True
        c = defaultdict(int)
        for i in range(n):
            if c[i]:
                continue
            if tern[i] == n - 1:
                continue
            rival = a[i][tern[i]]
            if c[rival]:
                continue
            if tern[rival] == n - 1:
                continue
            if a[rival][tern[rival]] == i:
                c[i] += 1
                c[rival] += 1
                tern[rival] += 1
                tern[i] += 1
                f = False
        if time.time - start >= 1.8:
            print(n * (n - 1) // 2)
            return
        if f:
            if tern == [n - 1] * n:
                print(ans-1)
                return
            else:
                print(-1)
                return
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return

#B
def B():
    a, b = LI()
    ans = 0
    b -= 1
    while b > 0:
        b -= a - 1
        ans += 1
    print(ans)

    return

#C
def C():
    n = II()
    h = LI()
    i = 0
    ans = 0
    while i < n:
        down = i+1
        while down < n:
            if h[down - 1] >= h[down]:
                down += 1
            else:
                break
        ans = max(ans, down - i - 1)
        i = down
    print(ans)
    return

#D
def D():
    n = II()
    print(n * (n - 1) // 2)
    return

#E
def E():
    n = II()
    a = LIR_(n)
    ans = 0
    tern = [0]*n
    while 1:
        ans += 1
        f = True
        c = [0]*n
        for i in range(n):
            if c[i]:
                continue
            if tern[i] == n - 1:
                continue
            rival = a[i][tern[i]]
            if c[rival]:
                continue
            if tern[rival] == n - 1:
                continue
            if a[rival][tern[rival]] == i:
                c[i] += 1
                c[rival] += 1
                tern[rival] += 1
                tern[i] += 1
                f = False
        if f:
            if list(set(tern.values())) == [n - 1]:
                print(ans-1)
                return
            else:
                print(-1)
                return
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=[[]]
rest_num=0
for i in range(n):
    ai=list(map(int,input().split()))
    a.append(ai)
    rest_num+=len(ai)
battled_i=[]
j=1
day=1
flag=False
while(rest_num>0):
    if(j>=n):
        if(not flag):
            print(-1)
            sys.exit()
        j=1
        day+=1
        battled_i=[]
    elif(j in battled_i):
        j+=1
    elif(j == a[a[j][0]][0]):
        battled_i.append(j)
        battled_i.append(a[j][0])
        del a[a[j][0]][0]
        del a[j][0]
        rest_num-=2
        j+=1
        flag=True
    else:
        j+=1
print(day+1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
l = []
r = set(list(range(n)))
N = n*(n-1) // 2
for _ in range(N)
    if l and not r:
        print(ans)
        break
    ne = set()
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    l = list(ne)
    for j in l:
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
l = []
r = set(list(range(n)))
N = n*(n-1) // 2
if _ in range(N)
    if l and not r:
        print(ans)
        break
    ne = set()
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    l = list(ne)
    for j in l:
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
r = set(list(range(n)))
while True:
    ne = set()
    if not r:
        print(ans)
        break
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in n:
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)
main()


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


def main():
    N = int(input())
    A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

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

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1 for _ in range(N * (N - 1) // 2)]
    print(max(dfs(n, edges, dp) for n in start_nodes))

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

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

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

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()

Submission status: Runtime Error

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

ans=0

C=[]
update = true

while update:
  for i in range(N):
    H=[]
    update = false
    if C[i] < N-1:
      r = A[i][C[i]]-1
      if C[r] < N-1 and i+1==A[R][C[r]] and r in H:
        H[r] = true
        H[i] = true
        C[r] += 1
        C[i] += 1
        update = true
    ans += 1
for i in range(N):
  if C[i] < N-1:
    ans=0

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0] * N
game = {}

for i in range(N-1):
    for j in range(i+1, N):
        game[(i+1, j+1)] = [0]*2
        game[(i+1, j+1)][0] = []
        game[(i+1, j+1)][1] = []



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

for i in range(N):
    game[(min(i+1, A[i][0]),max(i+1, A[i][0]))][1].append((min(i+1, A[i][1]),max(i+1, A[i][1])))
    if N-2 > 1:
        for j in range(1, N-2):
            game[(min(i+1, A[i][j]),max(i+1, A[i][j]))][0].append((min(i+1, A[i][j-1]),max(i+1, A[i][j-1])))
            game[(min(i+1, A[i][j]),max(i+1, A[i][j]))][1].append((min(i+1, A[i][j+1]),max(i+1, A[i][j+1])))
    game[(min(i+1, A[i][N-2]),max(i+1, A[i][N-2]))][0].append((min(i+1, A[i][N-3]),max(i+1, A[i][N-3])))

start = []
path = 0
paths = []

for key in game:
    if not game[key][0]:
        start.append(key)

def dfs(node,path):
    path += 1
    if node[1]:
        for item in node[1]:
            dfs(game[item],path)
    else:
        paths.append(path)

if start:
    for item in start:
        dfs(game[item],path)
    print(max(paths))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
N = int(input())
es = {(i,j):[] for i in range(N) for j in range(i+1,N)}
se = {(i,j):[] for i in range(N) for j in range(i+1,N)}
ins = {(i,j):0 for i in range(N) for j in range(i+1,N)}
dp = {(i,j):-1 for i in range(N) for j in range(i+1,N)}
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  if ins[res[-1]]!=0:
    return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    es[(x,y)] += [(nx,ny)]
    se[(nx,ny)] += [(x,y)]
    ins[(nx,ny)] += 1
start = [v1 for v1 in ins.keys() if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins):
  q = deque([int(v1) for v1 in range(len(ins)) if ins[v1]==0])
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
ls = TP_sort(es, ins.copy())
if ls==-1:
  print(-1)
else:
  for i in range(len(ins)):
    if ins[i]==0:
      dp[i] = 0
  print(dfs(ls[-1])+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins):
  q = deque([int(v1) for v1 in range(len(ins)) if ins[v1]==0])
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
ls = TP_sort(es, ins.copy())
if ls==-1:
  print(-1)
else:
  for i in range(len(ins)):
    if ins[i]==0:
      dp[i] = 0
  print(dfs(ls[-1])+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
indexes = [0 for i in range(N)]

day = 0
match = 0
while match!=N*(N-1)//2:
    checkes = [False for i in range(N)]
    check = False
    for n in range(N):
        jibun = n
        jibun_ind = indexes[jibun]
        if jibun_ind>=N-1:
            continue
        aite = A[jibun][jibun_ind] - 1
        aite_ind = indexes[aite]
        aite_no_aite = A[aite][aite_ind] - 1

        if not checkes[jibun] and not checkes[aite] and jibun == aite_no_aite:
            checkes[jibun] = True
            checkes[aite] = True
            indexes[jibun] += 1
            indexes[aite] += 1
            match += 1
            check = True
    if not check:
        day = -1
        break
    day += 1
print(day)

Submission status: Runtime Error

Solution code:
from sys import exit

N = int(input())
a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

id = [[0] * N for _ in range(N)]
def toId(i, j):
  if i > j:
    i, j = j, i
  return id[i][j]

visited = [False] * (N * (N - 1) // 2)
calculated = [False] * (N * (N - 1) // 2)
dp = [0] * (N * (N - 1) // 2)
to = [[] for _ in range(N * (N - 1) // 2)]

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]

v = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    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(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
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]

A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        cand1.add(A[n][-1])
    return len(can_use),cand1

answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x,cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0] * N
game = {}

for i in range(N-1):
    for j in range(i+1, N):
        game[(i+1, j+1)] = [0]*2
        game[(i+1, j+1)][0] = []
        game[(i+1, j+1)][1] = []



for i in range(N):
    A[i] = list(map(int,input().split()))
    game[(min(i+1, A[i][0]),max(i+1, A[i][0]))][1].append((min(i+1, A[i][1]),max(i+1, A[i][1])))
    if N-2 > 1:
        for j in range(1, N-2):
            game[(min(i+1, A[i][j]),max(i+1, A[i][j]))][0].append((min(i+1, A[i][j-1]),max(i+1, A[i][j-1])))
            game[(min(i+1, A[i][j]),max(i+1, A[i][j]))][1].append((min(i+1, A[i][j+1]),max(i+1, A[i][j+1])))
    game[(min(i+1, A[i][N-2]),max(i+1, A[i][N-2]))][0].append((min(i+1, A[i][N-3]),max(i+1, A[i][N-3])))

start = []
path = 0
paths = []

for key in game:
    if not game[key][0]:
        start.append(key)

def dfs(node,path):
    path += 1
    if node[1]:
        for item in node[1]:
            dfs(game[item],path)
    else:
        paths.append(path)

if start:
    for item in start:
        dfs(game[item],path)
    print(max(paths))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0] * N
game = {}

for i in range(N-1):
    for j in range(i+1, N):
        game[(i+1, j+1)] = [0]*2
        game[(i+1, j+1)][0] = []
        game[(i+1, j+1)][1] = []

for i in range(N):
    A[i] = list(map(int,input().split()))
    game[(min(i+1, A[i][0]),max(i+1, A[i][0]))][1].append((min(i+1, A[i][1]),max(i+1, A[i][1])))
    if N-2 > 1:
        for j in range(1, N-2):
            game[(min(i+1, A[i][j]),max(i+1, A[i][j]))][0].append((min(i+1, A[i][j-1]),max(i+1, A[i][j-1])))
            game[(min(i+1, A[i][j]),max(i+1, A[i][j]))][1].append((min(i+1, A[i][j+1]),max(i+1, A[i][j+1])))
    game[(min(i+1, A[i][N-2]),max(i+1, A[i][N-2]))][0].append((min(i+1, A[i][N-3]),max(i+1, A[i][N-3])))

start = []
path = 1
paths = []

for key in game:
    if not game[key][0]:
        start.append(key)

def dfs(node,path):
    if node[1]:
        path += 1
        for item in node[1]:
            dfs(game[item],path)
    else:
        paths.append(path)
        path = 0

if start:
    for item in start:
        dfs(game[item],path)
    print(max(paths))
else:
    print(-1)

Submission status: Runtime Error

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

N = int(input())

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



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

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

# 試合のリスト
M = []

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

# print(M)

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


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

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

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

# print(G)

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

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

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

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


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

		dp[v] = 0

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

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

		Calculated[v] = True
		# print(v)
		

		return dp[v]

ans = 0

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