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:
#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
rem=n*(n-1)//2
while rem and Q:#Qでは終了判定にならない
    i = Q.popleft()
    if i==n:
        if not Q:
            break
        cnt += 1
        Q.append(n)
        Done=set()
        continue
    if i not in Done and a[i]:
        p = a[i].pop()
        if p not in Done:##この判定しないと1日に複数回試合することになる
            if a[p][-1]==i:
                Q.append(i)
                Q.append(p)
                a[p].pop()
                Done.add(p)###
                Done.add(i)
                rem-=1
        else:#戻す ##ここのインデントww
            a[i].append(p)
                #a[p].append(i)
        #else:
        #    Done.remove(p)
        
if rem:
    print(-1)
    sys.exit()
        
print(cnt)

Submission status: Wrong Answer

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:
        if not Q:
            break
        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:
                Q.append(i)
                Q.append(p)
                a[p].pop()
                Done.add(p)###
            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: Wrong Answer

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:
                Q.append(i)
                Q.append(p)
                a[p].pop()
                Done.add(p)###
            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: Wrong Answer

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

listed = [-1] *  n
cnt = 1
while True:
    matched = False
    for i in range(n):
        if listed[i] == -1 and len(A[i]) > 0:
            # print(i,cnt,"POP")
            listed[i] = A[i].popleft() #i番目のqueueから最新を取り出す
    for i in range(n):
        aite = listed[i]
        if i == listed[aite]:
            listed[i] = -1
            listed[aite] = -1
            matched = True
    if not matched:
        print(-1)
        exit()
    if all([len(r) == 0 for r in A]):
        break
    cnt += 1
print(cnt)

Submission status: Wrong Answer

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

listed = [-1] *  n
cnt = 1
while True:
    for i in range(n):
        if listed[i] == -1 and len(A[i]) > 0:
            # print(i,cnt,"POP")
            listed[i] = A[i].popleft() #i番目のqueueから最新を取り出す
    for i in range(n):
        aite = listed[i]
        if i == listed[aite]:
            listed[i] = -1
            listed[aite] = -1
    if all([len(r) == 0 for r in A]):
        break
    if cnt > 10**6:
        print(-1)
        exit()
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N  = int(input())
ll = []
for i in range(N):
    l = [int(x) for x in input().split()]
    ll.append(l)
a = [[0 for i in range(2)] for j in range(N+1)]
for i in range(N):
    a[i+1][0] = ll[i][0]
    a[i+1][1] = 1
end = 0
ans = 0
z = 0
while True:
    tai = [0]*(N+1)
    ans += 1
    for i in range(1,N+1):
        if tai[i] != 0:
            continue
        now = a[i][0]
        if a[now][0] == i and now > i:
            tai[i] = 1
            tai[now] = 1
            if a[now][1] <= N-2:
                a[now][0] = ll[now-1][a[now][1]]
                a[now][1] += 1
                if a[now][1] == N-1:
                    a[now][0] == 0
                    end += 1
            if a[i][1] <= N-2:
                a[i][0] = ll[i-1][a[i][1]]
                a[i][1] += 1
                if a[i][1] == N-1:
                    a[i][0] == 0
                    end += 1
    if ans == 1 and max(tai) == 0:
        print(-1)
        break
    if end == N:
        print(ans+1)
        break

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

orders = set()
for i in range(len(A)):
    for j in range(len(A[i])):
        orders.add(str(i)+"vs"+str(A[i][j]))
orders = list(orders)

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

graph = dict()
for i in range(N):
    for j in range(N):
        if i != j:
            graph[str(min(i,j))+"vs"+str(max(i,j))] = []
            
max_move = [0 for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        graph[str(min(i,A[i][j]))+"vs"+str(max(i,A[i][j]))] \
        .append(str(min(i,A[i][j+1]))+"vs"+str(max(i,A[i][j+1])))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

graph = dict()
for i in range(N):
    for j in range(N):
        if i != j:
            graph[str(min(i,j))+"vs"+str(max(i,j))] = []
            
max_move = [0 for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        graph[str(min(i,A[i][j]))+"vs"+str(max(i,A[i][j]))] \
        .append(str(min(i,A[i][j+1]))+"vs"+str(max(i,A[i][j+1])))
        
#辞書でグラフを表現しているのを配列にする
translater = dict()
num = 0
for key in graph.keys():
    translater[key] = num
    num+=1

translated_graph = [[] for _ in range(num)]

for i, value in zip(range(num), graph.values()):
    for direction in value:
        translated_graph[i].append(translater[direction])     
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

graph = dict()
for i in range(N):
    for j in range(N):
        if i != j:
            graph[str(min(i,j))+"vs"+str(max(i,j))] = []
            
max_move = [0 for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        graph[str(min(i,A[i][j]))+"vs"+str(max(i,A[i][j]))] \
        .append(str(min(i,A[i][j+1]))+"vs"+str(max(i,A[i][j+1])))
        
#辞書でグラフを表現しているのを配列にする
translater = dict()
num = 0
for key in graph.keys():
    translater[key] = num
    num+=1

translated_graph = [[] for _ in range(num)]

for i, value in zip(range(num), graph.values()):
    for direction in value:
        translated_graph[i].append(translater[direction])     


import sys

# トポロジカルソート
points_to_there = [0 for _ in range(len(translated_graph))]
for i in range(len(translated_graph)):
    for direction in translated_graph[i]:
        points_to_there[direction] += 1

next_out = set()
for i in range(len(points_to_there)):
    if points_to_there[i] == 0:
        next_out.add(i)

if len(next_out) == 0:
    print(-1)
    sys.exit()

seen = set()
topo_sorted = []
while len(next_out) > 0:
    outed = next_out.pop()
    print(outed)
    if outed in seen:
        print(-1)
        sys.exit()
    topo_sorted.append(outed)
    seen.add(outed)
    for direction in translated_graph[outed]:
        points_to_there[direction]-=1
        if points_to_there[direction] == 0:
            next_out.add(direction)

costs = [0 for _ in range(len(translated_graph))]

max_cost = 0
for i in range(len(topo_sorted)):
    checking = topo_sorted[i]
    now_cost = costs[checking]
    for direction in translated_graph[checking]:
        if costs[direction] < 1+now_cost:
            costs[direction] = 1+now_cost
        if max_cost < costs[direction]:
            max_cost = costs[direction]
print(max_cost+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [deque(list(map(lambda x :int(x)-1, input().split()))) for _ in range(N)]

day = 0
candidates = set(range(N))
while len(candidates)>0:
    day += 1
    nextday = set()
    for candidate in candidates:
        if len(A[candidate]) == 0:
            continue
        opponent = A[candidate][0]
        if A[opponent][0] == candidate:
            A[opponent].popleft()
            A[candidate].popleft()
            
            nextday.add(candidate)
            nextday.add(opponent)
    candidates = nextday

for p in A:
    if len(p) > 0:
        print(-1)
        break
else:
    print(day)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = [[]*N for _ in range(N)]

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


    A = deque(A)
    current_i = 0
    ans = 1

    empty_count = 0

    while empty_count < N:
        found = False
        ignore_i = set()
        for i in range(N):
            a = A[i]
            if len(a) == 0 or i in ignore_i: continue

            target_i = a[0]-1
            target = A[target_i]
            if len(target) == 0:
                print(-1)
                exit()

            # print(i+1,target_i+1,target[0],A,"ok" if target[0]-1 == i else "ng")
            if target[0]-1 == i:
                found = True
                _, _ = target.popleft(), a.popleft()

                if len(a) == 0:
                    empty_count += 1
                if len(target) == 0:
                    empty_count += 1

                ignore_i.add(target_i)



        ans += 1
        if not found:
            print(-1)
            exit()


    print(ans)




if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = [[]*N for _ in range(N)]

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


    A = deque(A)
    current_i = 0
    ans = 1

    empty_count = 0

    while empty_count < N:
        found = False
        ignore_i = -1
        for i in range(N):
            a = A[i]
            if len(a) == 0 or i == ignore_i: continue

            target_i = a[0]-1
            target = A[target_i]
            if len(target) == 0:
                print(-1)
                exit()

            # print(i+1,target_i+1,target[0],A,"ok" if target[0]-1 == i else "ng")
            if target[0]-1 == i:
                found = True
                _, _ = target.popleft(), a.popleft()

                if len(a) == 0:
                    empty_count += 1
                if len(target) == 0:
                    empty_count += 1

                ignore_i = target_i



        ans += 1
        if not found:
            print(-1)
            exit()


    print(ans)




if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = [[]*N for _ in range(N)]

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


    A = deque(A)
    current_i = 0
    ans = 1

    empty_count = 0

    while empty_count < N:
        found = False
        for i in range(N):
            a = A[i]
            if len(a) == 0: continue

            target_i = a[0]-1
            target = A[target_i]
            if len(target) == 0:
                print(-1)
                exit()

            # print(i+1,target_i+1,target[0],A,"ok" if target[0]-1 == i else "ng")
            if target[0]-1 == i:
                found = True
                _, _ = target.popleft(), a.popleft()

                if len(a) == 0:
                    empty_count += 1
                if len(target) == 0:
                    empty_count += 1

        ans += 1
        if not found:
            print(-1)
            exit()


    print(ans)




if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
for _ in range(n):
  A.append(list(map(int,input().split())))

current_node = [0 for _ in range(n)]
ongoing = [i for i in range(n)]
days = 0
def get_matched():
  matched = []
  for i in range(n):
    i_current = current_node[i]
    if i_current >= n-1:
      continue
 #   print(i, i_current, len(A[i]))
    opponent = A[i][i_current] - 1
    opponent_current = current_node[opponent]
    if i == A[opponent][opponent_current] - 1:
      matched.append([i, opponent])
  return matched

def proceed(matched):
  done = 0
  for m in matched:
    current_node[m[0]] += 1
    if current_node[m[0]] == n-1:
      done += 1
      ongoing.remove(m[0])
  return done

Submission status: Wrong Answer

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 tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

ij2u = {}
v = 0
for i in range(n):
    for j in range(n):
        ii,jj = min(i,j), max(i,j)
        if (ii,jj) not in ij2u:
            ij2u[ii,jj] = v
            ij2u[jj,ii] = v
            v += 1
N = v+1        
ns = [[] for _ in range(N)]
for i in range(n):
    a[i] = list(map(lambda x: int(x)-1, input().split()))
    for j in range(n-2):
        ns[ij2u[i,a[i][j]]].append(ij2u[i, a[i][j+1]])

seen = [False] * N
done = [False] * N
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
dist = [None] * N
def sub(u):
    if dist[u] is not None:
        return dist[u]
    if not ns[u]:
        d = 1
    else:
        d = 1
        for v in ns[u]:
            d = max(d, sub(v)+1)
    dist[u] = d
    return d
    
for u in range(N):
    if done[u]:
        continue
    pos = dfs(u, -1)
    if pos>=0:
        break
if pos>=0:
    print(-1)
else:
    ans = 0
    for u in range(n):
        ans = max(ans, sub(u))
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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

ij2u = {}
v = 0
for i in range(n):
    for j in range(n):
        ii,jj = min(i,j), max(i,j)
        if (ii,jj) not in ij2u:
            ij2u[ii,jj] = v
            ij2u[jj,ii] = v
            v += 1
N = v+1        
ns = [[] for _ in range(N)]
for i in range(n):
    a[i] = list(map(lambda x: int(x)-1, input().split()))
    for j in range(n-2):
        ns[ij2u[i,a[i][j]]].append(ij2u[i, a[i][j+1]])

seen = [False] * N
done = [False] * N
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
dist = [None] * N
def sub(u):
    if dist[u] is not None:
        return dist[u]
    if not ns[u]:
        d = 1
    else:
        d = 0
        for v in ns[u]:
            d = max(d, sub(v)+1)
    dist[u] = d
    return d
    
for u in range(N):
    if done[u]:
        continue
    pos = dfs(u, -1)
    if pos>=0:
        break
if pos>=0:
    print(-1)
else:
    ans = 0
    for u in range(n):
        ans = max(ans, sub(u))
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

ij2u = {}
v = 0
for i in range(n):
    for j in range(n):
        ii,jj = min(i,j), max(i,j)
        if (ii,jj) not in ij2u:
            ij2u[ii,jj] = v
            ij2u[jj,ii] = v
            v += 1
N = v+1        
ns = [[] for _ in range(N)]
for i in range(n):
    a[i] = list(map(lambda x: int(x)-1, input().split()))
    for j in range(n-2):
        ns[ij2u[i,a[i][j]]].append(ij2u[i, a[i][j+1]])

seen = [False] * N
done = [False] * N
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
dist = [None] * N
def sub(u):
    if dist[u] is not None:
        return dist[u]
    if not ns[u]:
        d = 1
    else:
        d = 0
        for v in ns[u]:
            d = max(d, sub(v)+1)
    dist[u] = d
    return d
    
for u in range(N):
    pos = dfs(u, -1)
    if pos>=0:
        break
if pos>=0:
    print(-1)
else:
    ans = 0
    for u in range(n):
        ans = max(ans, sub(u))
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


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

    # print(A)

    days = 0
    while True:
        flag = True
        ta = set()
        for i in range(N):
            if len(A[i]) == 0 or i in ta:
                continue
            if i == A[A[i][0]][0]:
                t = A[i][0]
                ta |= set([t])
                A[i].pop(0)
                A[t].pop(0)
                flag = False
        days += 1
        if flag:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


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

    # print(A)

    days = 0
    while True:
        flag = True
        for i in range(N):
            if len(A[i]) == 0:
                continue
            if i == A[A[i][0]][0]:
                t = A[i][0]
                A[i].pop(0)
                A[t].pop(0)
                flag = False
        days += 1
        if flag:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] # 試合グラフ
indegree = [0 for i in range((N * (N - 1)) // 2)] # 入次数
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    # i と a - 1の試合
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if done[game]: # 既に終わっている試合の場合　閉路と見なす
      print(-1)
      exit(0)
    done[game] = True
    for child in G[game]: # 翌日のゲームを探索
      indegree[child] -= 1
      if indegree[child] == 0: # 入次数が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

print(day)

Submission status: Wrong Answer

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] # 試合グラフ
indegree = [0 for i in range((N * (N - 1)) // 2)] # 入次数
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    # i と a - 1の試合
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if done[game]: # 既に終わっている試合の場合　閉路と見なす
      print(-1)
      exit(0)
    done[game] = False
    for child in G[game]: # 翌日のゲームを探索
      indegree[child] -= 1
      if indegree[child] == 0: # 入次数が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

print(day)

Submission status: Wrong Answer

Solution code:
# PyPy3 (2.4.0)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        # 入次数が 0 の頂点を deque に入れる
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        return self.nodes
    
    def get_depth(self):
        return self.depth

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

# 試合と頂点の対応表
M = [[-1 for _ in range(N)] for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1

# 試合 j が 試合 i の翌日以降にしか行えない -> G[i][j]

G = [[] for _ in range((N*(N-1)//2))]
# 頂点(試合) の入次数
In = [0]*(N*(N-1)//2)
# 入力からグラフ, 配列を生成
for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) == 0:
    print(-1)
else:
    print(max(depth) + 1)

Submission status: Wrong Answer

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        # 入次数が 0 の頂点を deque に入れる
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        return self.nodes
    
    def get_depth(self):
        return self.depth

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

# 試合と頂点の対応表
M = [[-1 for _ in range(N)] for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1

# 試合 j が 試合 i の翌日以降にしか行えない -> G[i][j]

G = [[] for _ in range((N*(N-1)//2))]
# 頂点(試合) の入次数
In = [0]*(N*(N-1)//2)
# 入力からグラフ, 配列を生成
for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) == 0:
    print(-1)
else:
    print(max(depth) + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
c = [0 for _i in range(n)]
a = [list(map(int, input().split())) for _i in range(n)]

tree = [[[] for _i in range(n)] for _j in range(n)]
for i in range(n):
    for j in range(n-2):
        x, y = sorted([i, a[i][j]-1])
        z, w = sorted([i, a[i][j+1]-1])
        tree[x][y].append([z, w])

result = []


visit = [[-1 for _i in range(n)] for _j in range(n)]
visit[0][1] = 1

def solve(x, y, visit):
    if tree[x][y] == []:
        return result.append(visit[x][y])
    for i, j in tree[x][y]:
        if visit[i][j]>0:
            import sys
            print(-1)
            sys.exit()
        visit[i][j] = visit[x][y]+1
        solve(i, j, visit.copy())
        visit[i][j] = -1
solve(0,1,visit)
print(max(result))