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: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    A[i] = [i-1 for i in map(int, input().split())]


def pair(x,y):
    if x<y:
        return (x,y)
    else:
        return (y,x)

to_index = dict()
to_pair = dict()
idx = 0
for i in range(N):
    for j in range(i+1,N):
        to_index[(i,j)] = idx
        to_pair[idx] = (i,j)
        idx += 1
    
MAX_N = idx
# DAG TopoSort
in_count = [0]*MAX_N
edge = [[] for _ in range(MAX_N)]

for i in range(N):
    for j in range(N-2):
        vnum = to_index[pair(i,A[i][j+1])]
        pvnum = to_index[pair(i, A[i][j])]
        edge[pvnum].append(vnum)

for i in range(MAX_N):
    for v in edge[i]:
        in_count[v] += 1

S = []
L = [] #Sort結果
index = [0]*MAX_N # 頂点vのLにおけるインデックスindex[v]
for i in range(MAX_N):
    if in_count[i]==0: S.append(i)
while S:
    v = S.pop()
    index[v] = len(L)
    L.append(v)
    for nv in edge[v]:
        in_count[nv] -= 1
        if in_count[nv]==0:
            S.append(nv)

if len(L) != MAX_N:
    print(-1)
    exit()

used_set = set()
ans = 1
for i,v in enumerate(L):
    xy = to_pair[v]
    if (xy[0] in used_set) or (xy[1] in used_set):
        ans += 1
        used_set = set()
    used_set.add(xy[0])
    used_set.add(xy[1])

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    m=n*(n-1)//2
    a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]
    d=dict()
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            d[(j,i)]=cnt
            cnt+=1

    G1=[[] for _ in range(m)]
    G2=[set() for _ in range(m)]
    for i in range(n):
        for j in range(n-1-1):
            k=d[(i,a[i][j])]
            l=d[(i,a[i][j+1])]
            G1[k].append(l)
            G2[l].add(k)

    now=[]
    for i in range(m):
        if len(G2[i])==0:
            now.append(i)

    if len(now)==0:
        print(-1)
    else:
        #トポロジカルソート
        t=[]
        nex=deque(now)
        while len(nex)>0:
            now=nex.popleft()
            t.append(now)
            li=G1[now]
            for i in li:
                G2[i].remove(now)
                if len(G2[i])==0:
                    nex.append(i)

        if len(t)!=m:
            print(-1)
        else:
            dp=[0]*m
            dp[t[0]]=1
            for i in t:
                for j in G1[i]:
                    dp[j]=max(dp[j],dp[i]+1)

            print(max(dp))

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    m=n*(n-1)//2
    a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]
    d=dict()
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            d[(j,i)]=cnt
            cnt+=1

    G1=[[] for _ in range(m)]
    G2=[set() for _ in range(m)]
    for i in range(n):
        for j in range(n-1-1):
            k=d[(i,a[i][j])]
            l=d[(i,a[i][j+1])]
            G1[k].append(l)
            G2[l].add(k)

    now=[]
    for i in range(m):
        if len(G2[i])==0:
            now.append(i)

    if len(now)==0:
        print(-1)
    else:
        #トポロジカルソート
        t=[]
        nex=deque(now)
        while len(nex)>0:
            now=nex.popleft()
            t.append(now)
            li=G1[now]
            for i in li:
                G2[i].remove(now)
                if len(G2[i])==0:
                    nex.append(i)

        if len(t)!=m:
            print(-1)
        else:
            dp=[0]*m
            dp[t[0]]=1
            for i in t:
                for j in G1[i]:
                    dp[j]=max(dp[j],dp[i]+1)

            print(dp[t[-1]])

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = [list(map(int, readline().split())) for _ in range(n)]
q = list(range(n))
for cnt in range(2, n ** 2 + 2):
    qq = []
    while q:
        x = q.pop()
        if a[a[x][0] - 1][0] == x + 1:
            qq.append(x)
    if qq:
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        break
    if not q:
        print(cnt)
        break

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = list(deque(map(int, input().split())) for _ in range(N))
for i in range(N):
    A[i] = deque(map(lambda x: x - 1, A[i]))
# print(A)
ans = 0
change = True
# while True:
for _ in range(N * 10):
    change = False
    work = [-1] * N
    for i in range(N):
        if not A[i]:
            continue
        enemy = A[i][0]
        work[i] = enemy
        if work[enemy] == i:
            A[i].popleft()
            A[enemy].popleft()
            change = True
    if not change:
        break
    ans += 1


empty = True
for row in A:
    if row:
        empty = False
if not empty:
    print('-1')
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = list(deque(map(int, input().split())) for _ in range(N))
for i in range(N):
    A[i] = deque(map(lambda x: x - 1, A[i]))
# print(A)
ans = 0
change = True
# while True:
for _ in range(N):
    change = False
    work = [-1] * N
    for i in range(N):
        if not A[i]:
            continue
        enemy = A[i][0]
        work[i] = enemy
        if work[enemy] == i:
            A[i].popleft()
            A[enemy].popleft()
            change = True
    if not change:
        break
    ans += 1


empty = True
for row in A:
    if row:
        empty = False
if not empty:
    print('-1')
else:
    print(ans)

Submission status: Wrong Answer

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

def main():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    for i in range(n):
        X = A[i]
        X = [x-1 for x in X]
        A[i] = X
    #print(A)

    d = {}
    id = 0
    for i in range(n):
        for j in A[i]:
            a = min(i, j)
            b = max(i, j)
            if (a, b) not in d:
                d[(a, b)] = id
                id += 1

    g = [[] for _ in range(len(d))]
    for i in range(n):
        for j in range(n-2):
            a1 = min(i, A[i][j])
            b1 = max(i, A[i][j])
            a2 = min(i, A[i][j+1])
            b2 = max(i, A[i][j+1])
            k1 = d[(a1, b1)]
            k2 = d[(a2, b2)]
            g[k1].append(k2)
    #print(g)

    m = len(g)

    s = []
    s.append(0)
    dp = [-1]*m
    dp[0] = 0
    while s:
        v = s.pop()
        for u in g[v]:
            dp[u] = max(dp[u], dp[v]+1)
            if dp[u]+1 > n*(n-1)//2:
                print(-1)
                exit()
            s.append(u)
    print(max(dp)+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
G = {(i,j):[] for i in range(1,N) for j in range(i+1,N+1)}
C = {(i,j):0 for i in range(1,N) for j in range(i+1,N+1)}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    for k in range(1,N-1):
        i0 = i
        j0 = A[k-1]
        if i0>j0:
            i0,j0 = j0,i0
        i1 = i
        j1 = A[k]
        if i1>j1:
            i1,j1=j1,i1
        G[(i0,j0)].append((i1,j1))
        C[(i1,j1)] += 1
heap = []
for i in range(1,N):
    for j in range(i+1,N+1):
        if C[(i,j)]==0:
            heap.append((i,j))
cnt = 0
while heap:
    cnt += 1
    A = []
    for x in heap:
        for y in G[x]:
            C[y] -= 1
            if C[y]==0:
                A.append(y)
    heap = A[:]
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
from time import time
S = time()

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

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

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        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 time() - S >= 1.500:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
ans = 0
#for i in range(N-1):
while True:
  tmp = {i:[] for i in range(1, N+1)}
  for j in range(N):
    #print(tmp)
    if len(tmp[j+1]) != 0 and A[j][0] in tmp[j+1]: # すでに対戦相手が出ていて、一致
      A[A[j][0]-1].popleft()
      A[j].popleft()
    if len(tmp[j+1]) == 0:
      if len(A[j]) > 0:
        tmp[A[j][0]] += [j+1]
  
  ans += 1
  # 終了条件
  flag = True
  for i in range(N):
    if len(A[i]) != 0:
      flag = False
  if flag:
    break

  if ans > N*(N-1)//2:
    print(-1)
    exit()

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[int(x) - 1 for x in row.split()] for row in readlines()]


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

MAXV = N * (N - 1) // 2

visited = [0 for i in range(MAXV)]
calculated = [0 for i in range(MAXV)]
dp = [0 for i in range(MAXV)]
def dfs(v):
    if visited[v]:
        if not calculated[v]:
            print(-1)
            exit()
        return dp[v]

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

to = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(N - 1):
        a = i
        b = A[i][j]
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
    for j in range(N - 2):
        to[A[i][j + 1]].append(A[i][j])

ans = 0
for i in range(V):
    ans = max(ans, dfs(i))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

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

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

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

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

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


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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

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

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

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

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

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


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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

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

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

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

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

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


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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for i in range (n)]

for i in range(1,n*(n-1)//2+1):
  ecnt=0
  seen=[0]*n
  ng=True
  for j in range(n):
    if not a[j]:
      ecnt+=1
      continue
    if seen[j]:
      continue
    seen[j]=1
    p=a[j][0]-1
    if seen[p]:
      continue
    if a[p][0]==j+1:
      ng=False
      a[p].popleft()
      a[j].popleft()
      seen[p]=1
  if ecnt==n:
      print(i-1)
      exit()
  if ng:
      print(-1)
      exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for i in range (n)]

for i in range(1,n**2+1):
  seen=[0]*n
  ng=True
  ecnt=0
  for j in range(n):
    if not a[j]:
      ecnt+=1
      continue
    if seen[j]:
      continue
    seen[j]=1
    p=a[j][0]-1
    if seen[p]:
      continue
    if a[p][0]==j+1:
      ng=False
      a[p].popleft()
      a[j].popleft()
      seen[p]=1
    if ecnt==n:
      print(i-1)
      exit()
    if ng:
      print(-1)
      exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for i in range (n)]

for i in range(1,n**2+1):
  seen=[0]*n
  ng=True
  ecnt=0
  for j in range(n):
    if not a[j]:
      ecnt+=1
      continue
    if seen[j]:
      continue
    seen[j]=1
    p=a[j][0]-1
    if seen[p]:
      continue
    if a[p][0]==j+1:
      ng=False
      a[p].popleft()
      a[j].popleft()
      seen[p]=1
    if ecnt==n:
      print(i)
      exit()
    if ng:
      print(-1)
      exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for i in range (n)]

for i in range(1,n**2+1):
  seen=[0]*n
  ok=True
  ng=True
  for j in range(n):
    if not a[j]:
      continue
    if seen[j]:
      continue
    seen[j]=1
    p=a[j][0]-1
    if seen[p]:
      continue
    if a[p][0]==j+1:
      ng=False
      a[p].popleft()
      a[j].popleft()
      seen[p]=1
    if a[j] or a[p]:
      ok=False
    if ng:
      print(-1)
      exit()
    if ok:
      print(i)
      exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
"""
League
"""
n = int(input())
dp = [0] * n #必要な最小日数をもっておく
dpm = [[0]*n for i in range(n)]
dp2 = [[0]*n for i in range(n)]


mij = []
for i in range(n):
    As = list(map(int, input().split()))
    mij.append([a-1 for a in As])
# j番目において
for j in range(n-1):
    for i in range(n):
        me = i
        enemy = mij[i][j]
        mn = min(me, enemy)
        mx = max(me, enemy)
        dpm[mn][mx] += 1
        # マッチが成立したら
        if dpm[mn][mx] == 2:
            # どの日に実施できるか決める
            upd = max(dp[mn],dp[mx]) + 1
            # 最後に試合した日を更新
            dp[mn] = upd
            dp[mx] = upd
            # A vs Bの試合の日を記録
            dp2[mn][mx] = upd
# print(dp2)
ans = 0
for i in range(n):
    row = dp2[i]
    if row != sorted(row):
        print(-1)
        exit()
    ans = max(ans, max(row))
print(ans)

Submission status: Wrong Answer

Solution code:
"""
League
"""
n = int(input())
dp = [0] * n #必要な最小日数をもっておく
dpm = [[0]*n for i in range(n)]
dp2 = [[0]*n for i in range(n)]


mij = []
for i in range(n):
    As = list(map(int, input().split()))
    mij.append([a-1 for a in As])
# j番目において
for j in range(n-1):
    for i in range(n):
        me = i
        enemy = mij[i][j]
        mn = min(me, enemy)
        mx = max(me, enemy)
        dpm[mn][mx] += 1
        if dpm[mn][mx] == 2:
            upd = max(dp[mn],dp[mx]) + 1
            dp[mn] = upd
            dp[mx] = upd
            dp2[mn][mx] = upd
        # print(mn,mx,dp)
ans = 0
for i in range(n-1):
    row = dp2[i]
    if row != sorted(row):
        print(-1)
        exit()
    ans = max(ans, max(row))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def edge_to_vertex(n, i, j):
        'convert edge(i,j) (1-index) to vertex'
        return (2 * n - i) * (i - 1) // 2 + (j - i - 1)
    
    def topological_bfs(m, adj):
        dim_0_vertices = []
        sorted_vertices = []
        dim = [0] * m
        for i in range(m):
            for j in adj[i]:
                dim[j] += 1
        q = deque()
        for i in range(m):
            if dim[i] == 0:
                dim_0_vertices.append(i)
                q.append(i)
        while q:
            u = q.popleft()
            assert(dim[u] == 0)
            sorted_vertices.append(u)
            for v in adj[u]:
                dim[v] -= 1
                if dim[v] == 0:
                    q.append(v)
        return dim_0_vertices, sorted_vertices
        

    def bfs(adj, start):
        max_depth = 0
        visited = [False] * len(adj)
        q = deque()
        q.append([start, 0])
        while q:
            u, dist = q.popleft()
            if not visited[u]:
                visited[u] = True
                max_depth = max(max_depth, dist)
                for v in adj[u]:
                    if not visited[v]:
                        q.append([v, dist + 1])
        return max_depth

    
    n = ii()
    # 試合の組み合わせを頂点へと変換し有向グラフ隣接リストへと変換する前処理 O(n^2)
    m = n * (n - 1) // 2
    adj = [[] for _ in range(m)]
    for i in range(1, n + 1):
        L = lmi()
        vertices = [edge_to_vertex(n, min(i, j), max(i, j)) for j in L]
        for k in range(1, n - 1):
            u, v = vertices[k-1], vertices[k]
            adj[u].append(v)
    # print(adj)

    # BFS トポロジカルソートを用いて閉路判定
    dim_0_vertices, topological_sorted = topological_bfs(m, adj)
    if len(topological_sorted) != m:
        print(-1)
    # 入次数 0 の頂点から BFS を行い最大距離を返す
    else:
        date = 0
        for u in dim_0_vertices:
            date = max(date, bfs(adj, u) + 1)
        print(date)
 

if __name__ == "__main__":
    main()