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:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = 1
    count = [0]*n
    check = set()
    game = []
    for i in range(n):
        if count[i] >= n-1 or i in check:
            continue
        ind = l[i][count[i]]-1
        if ind in check:
            continue
        if l[ind].index(i+1) == count[ind]:
            check |= set([i,ind])
            if i > ind:
                game.append([ind,i])
            else:
                game.append([i,ind])
            count[i] += 1
            count[ind] += 1
    while True:
        checkpre = check
        gamepre = sorted(game)
        check = set()
        game = []
        for i,j in gamepre:
            ci = True
            cj = True
            if count[i] >= n-1 or i in check:
                ci = False
            if count[j] >= n-1 or j in check:
                cj = False
            if ci:
                ind = l[i][count[i]]-1
                if ind in check:
                    continue
                if l[ind].index(i+1) == count[ind]:
                    check |= set([i,ind])
                    if i > ind:
                        game.append([ind,i])
                    else:
                        game.append([i,ind])
                    count[i] += 1
                    count[ind] += 1
            if cj:
                ind = l[j][count[j]]-1
                if ind in check:
                    continue
                if l[ind].index(j+1) == count[ind]:
                    check |= set([j,ind])
                    if j > ind:
                        game.append([ind,j])
                    else:
                        game.append([j,ind])
                    count[j] += 1
                    count[ind] += 1
        if not check:
            if sum(count) != n*(n-1):
                print(-1)
                exit()
            else:
                print(ans)
                exit()
        ans += 1
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = 1
    count = [0]*n
    check = set()
    game = []
    for i in range(n):
        if count[i] >= n-1 or i in check:
            continue
        ind = l[i][count[i]]-1
        if ind in check:
            continue
        if l[ind].index(i+1) == count[ind]:
            check |= set([i,ind])
            game.append([i,ind])
            count[i] += 1
            count[ind] += 1
    while True:
        checkpre = check
        gamepre = game
        check = set()
        game = []
        for i,j in gamepre:
            ci = True
            cj = True
            if count[i] >= n-1 or i in check:
                ci = False
            if count[j] >= n-1 or j in check:
                cj = False
            if ci:
                ind = l[i][count[i]]-1
                if ind in check:
                    continue
                if l[ind].index(i+1) == count[ind]:
                    check |= set([i,ind])
                    game.append([i,ind])
                    count[i] += 1
                    count[ind] += 1
            if cj:
                ind = l[j][count[j]]-1
                if ind in check:
                    continue
                if l[ind].index(j+1) == count[ind]:
                    check |= set([j,ind])
                    game.append([j,ind])
                    count[j] += 1
                    count[ind] += 1
        if not check:
            if sum(count) != n*(n-1):
                print(-1)
                exit()
            else:
                print(ans)
                exit()
        ans += 1
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
v = n*(n-1)//2
E = [[] for i in range(v)]
dic = {}
c = 0
for i in range(n):
    for j in range(n-1):
        a,b = i,l[i][j]-1
        if a > b:
            a,b = b,a
        if (a,b) in dic:
            l[i][j] = dic[(a,b)]
        else:
            dic[(a,b)] = c
            l[i][j] = dic[(a,b)]
            c += 1
    for j in range(n-2):
        E[l[i][j]].append(l[i][j+1])

def dfs(i):
    if visit[i]:
        if dis[i] == -1:
            return -1
        else:
            return dis[i]
    visit[i] = True
    d = 1
    for nex in E[i]:
        res = dfs(nex)
        if res == -1:
            return -1
        d = max(d,res+1)

    dis[i] = d
    return d

visit = [False]*v
dis = [-1]*v
print(dfs(l[0][0]))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
import collections
edge=collections.defaultdict(list)
idg=collections.defaultdict(int)
for i in range(1,n+1):
    l=list(map(int,input().split()))
    for j,k in zip(l,l[1:]):
        if i>k:
            x=(k,i)
        else:
            x=(i,k)
        if i>j:
            y=(j,i)
        else:
            y=(i,j)
        edge[y].append(x)
        idg[x]+=1
s=set()
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if idg[(i,j)]==0:
            s.add((i,j))
ans=0
for _ in range(n*(n-1)//2):
    i+=len(s)
    l=s
    s=set()
    for j in l:
        for k in edge[j]:
            idg[k]-=1
            if idg[k]==0:
                s.add(k)
    ans+=1
    if len(s)==0:
        break
if i<n*(n-1)//2:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
day=0
match=n*(n-1)
card=1
next=[0]*n
for i in range(n):
    a[i].append(-1)

while card>0 and match>0:
  day+=1
  player=[]
  for i in range(n):
    t=a[i][next[i]]-1
    if i==a[t][next[t]]-1:
      player.append(i)
  for i in player:
    next[i]+=1
  card=len(player)
  match-=card
if match>0:
  day=-1
print(day)
print(next)

Submission status: Wrong Answer

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

def main():
    n = int(input())
    pair = []
    for i in range(n):
        for j in range(i + 1,n):
            pair.append((i,j))

    G = {i:[] for i in pair}
    inedge = {i:0 for i in pair}
    for i in range(n):
        a = [int(i) - 1 for i in input().split()]
        for j in range(n - 2):
            if i <= a[j] and i <= a[j + 1]:
                G[(i,a[j])].append((i,a[j + 1]))
                inedge[(i,a[j + 1])] += 1
            elif i <= a[j] and i > a[j + 1]:
                G[(i,a[j])].append((a[j + 1],i))
                inedge[(a[j + 1],i)] += 1
            elif i > a[j] and i <= a[j + 1]:
                G[(a[j],i)].append((i,a[j + 1]))
                inedge[(i,a[j + 1])] += 1
            else:
                G[(a[j],i)].append((a[j + 1],i))
                inedge[(a[j + 1],i)] += 1
    
    visited = {i:0 for i in pair}
    finished = {i:0 for i in pair}

    flag = [1]
    def dfs(node): #サイクルの検出用
        visited[node] = 1
        for e in G[node]:
            if finished[e]:
                continue
            if visited[e] and finished[e] == 0:
                flag[0] = 0
                return
            dfs(e)
            if flag[0] == 0:
                return
        finished[node] = 1

    dfs((0,1))
    
    if flag[0] == 1:
        st = deque()
        dist = {i:-1 for i in pair}
        for i in pair:
            if inedge[i] == 0:
                st.append(i)
                dist[i] = 1
        
        while len(st):
            node = st.popleft()
            for e in G[node]:
                dist[e] = max(dist[e],dist[node] + 1)
                inedge[e] -= 1
                if inedge[e] == 0:
                    st.append(e)  
 
        print(max(dist.values()))
    else:
        print(-1)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

def main():
    n = int(input())
    pair = []
    for i in range(n):
        for j in range(i + 1,n):
            pair.append((i,j))

    G = {i:[] for i in pair}
    inedge = {i:0 for i in pair}
    for i in range(n):
        a = [int(i) - 1 for i in input().split()]
        for j in range(n - 2):
            if i <= a[j] and i <= a[j + 1]:
                G[(i,a[j])].append((i,a[j + 1]))
                inedge[(i,a[j + 1])] += 1
            elif i <= a[j] and i > a[j + 1]:
                G[(i,a[j])].append((a[j + 1],i))
                inedge[(a[j + 1],i)] += 1
            elif i > a[j] and i <= a[j + 1]:
                G[(a[j],i)].append((i,a[j + 1]))
                inedge[(i,a[j + 1])] += 1
            else:
                G[(a[j],i)].append((a[j + 1],i))
                inedge[(a[j + 1],i)] += 1
    
    visited = {i:0 for i in pair}
    finished = {i:0 for i in pair}

    flag = [1]
    def dfs(node): #サイクルの検出用
        visited[node] = 1
        for e in G[node]:
            if finished[e]:
                continue
            if visited[e] and finished[e] == 0:
                flag[0] = 0
                return
            dfs(e)
            if flag[0] == 0:
                return
        finished[node] = 1

    dfs((0,1))
    
    if flag[0] == 1:
        st = deque()
        dist = {i:-1 for i in pair}
        for i in pair:
            if inedge[i] == 0:
                st.append(i)
                dist[i] = 1
        
        while len(st):
            node = st.pop()
            for e in G[node]:
                dist[e] = max(dist[e],dist[node] + 1)
                inedge[e] -= 1
                if inedge[e] == 0:
                    st.append(e)  
 
        print(max(dist.values()))
    else:
        print(-1)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

n = int(input())
pair = []
for i in range(n):
    for j in range(i + 1,n):
        pair.append((i,j))

G = {i:set() for i in pair}
inedge = {i:0 for i in pair}
for i in range(n):
    a = [int(i) - 1 for i in input().split()]
    for j in range(n - 2):
        if i <= a[j] and i <= a[j + 1]:
            G[(i,a[j])].add((i,a[j + 1]))
            inedge[(i,a[j + 1])] += 1
        elif i <= a[j] and i > a[j + 1]:
            G[(i,a[j])].add((a[j + 1],i))
            inedge[(a[j + 1],i)] += 1
        elif i > a[j] and i <= a[j + 1]:
            G[(a[j],i)].add((i,a[j + 1]))
            inedge[(i,a[j + 1])] += 1
        else:
            G[(a[j],i)].add((a[j + 1],i))
            inedge[(a[j + 1],i)] += 1
    
visited = {i:0 for i in pair}
finished = {i:0 for i in pair}

flag = [1]
def dfs(node): #サイクルの検出用
    visited[node] = 1
    for e in G[node]:
        if finished[e]:
            continue
        if visited[e] and finished[e] == 0:
            flag[0] = 0
            return
        dfs(e)
        if flag[0] == 0:
            return
    finished[node] = 1

dfs((0,1))
    
if flag[0] == 1:
    st = deque()
    dist = {i:-1 for i in pair}
    for i in pair:
        if inedge[i] == 0:
            st.append(i)
            dist[i] = 1
        
    while len(st):
        node = st.pop()
        for e in G[node]:
            dist[e] = max(dist[e],dist[node] + 1)
            inedge[e] -= 1
            if inedge[e] == 0:
                st.append(e)  
 
    print(max(dist.values()))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
def proc(x):
  return int(x)-1
from collections import deque
A=[deque(map(proc,input().split())) for i in range(N)]
ans=0
num=0
NUM=N*(N-1)//2
while num<NUM:
  _=set()
  for i in range(N):
    if i in _ or len(A[i])==0:
      continue
    if A[A[i][0]][0]==i and A[i][0] not in _:
      a=A[i].popleft()
      b=A[a].popleft()
      _.add(a)
      _.add(b)
      num+=1
      print(num,a,b,'day{0}'.format(ans+1))
  if len(_)==0:
    print(-1)
    exit(0)
  ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[[] for _ in range(N)]
    for i in range(N):
        A[i]=deque(list(map(lambda x: int(x)-1,input().split())))
    days=1
    c=0
    s=set()
    pre=[]
    for i in range(N):
        if (min(i,A[i][0]),max(i,A[i][0])) in s:
            a=A[i][0]
            A[i].popleft()
            A[a].popleft()
            pre.append(i)
            pre.append(A[i][0])
            c+=2
        else:
            s.add((min(i,A[i][0]),max(i,A[i][0])))
    if c<N*(N-1):
        while c<N*(N-1):
            s=set()
            tmp=[]
            for i in pre:
                if A[i] and A[A[i][0]][0]==i:
                    tmp.append(i)
                    tmp.append(A[i][0])
            tmp=list(set(tmp))
            for i in tmp:
                A[i].popleft()
                c+=1
            pre=tmp
            days+=1
            if days>N*(N-1)//2:
                print(-1)
                exit()
    print(days)
                
            
        
    
        
        

    

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


match_sm = n * (n - 1) // 2

adj = [[] for _ in range(match_sm)]
in_deg = [0] * match_sm
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [i for i, e in enumerate(in_deg) if e == 0]
day = 0
while cnd:
    nxt_cnd = []
    for u in cnd:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt_cnd.append(v)

    cnd = nxt_cnd
    day += 1

if not in_deg.count(0):
    day = -1

print(day)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    c = [[int(i)-1 for i in input().split()] for j in range(N)]
    from collections import defaultdict
    edge = defaultdict(set)
    deg = defaultdict(int)
    for i, A in enumerate(c):
        for j in range(N-2):
            if i < A[j]:
                if i < A[j+1]:
                    edge[(i, A[j])].add((i, A[j+1]))
                    deg[(i, A[j+1])] += 1
                else:
                    edge[(i, A[j])].add((A[j+1], i))
                    deg[(A[j+1], i)] += 1
            else:
                if i < A[j+1]:
                    edge[(A[j], i)].add((i, A[j+1]))
                    deg[(i, A[j+1])] += 1
                else:
                    edge[(A[j], i)].add((A[j+1], i))
                    deg[(A[j+1], i)] += 1

    que = []
    dist = defaultdict(int)
    for i in range(N):
        for j in range(i+1, N):
            if deg[(i, j)] == 0:
                que.append((i, j))  # root
                dist[(i, j)] = 1

    def dfs(v):
        seen = defaultdict(bool)
        finished = defaultdict(bool)
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in edge[u]:
                dist[next_v] = max(dist[next_v], dist[u] + 1)
                if finished[next_v]:
                    continue
                if seen[next_v] and not(finished[next_v]):
                    # 閉路検出
                    return False
                seen[next_v] = True
                todo.append(next_v)
                break
            else:
                finished[u] = True
                todo.pop()
        return True

    if not(que):
        return print(-1)
    for s in que:
        flag = dfs(s)
        if not(flag):
            return print(-1)
    # print(dist)
    print(max(dist.values()))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            a=min(i,x)*10**3+max(i,x)
            if a in d:
                z=d[a]
                if prev!=-1:
                    edge1[prev].append(z)
                    edge2[z].append(prev)
                prev=z
            else:
                d[a]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
                prev=d[a]
    que=deque()
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            que.append(i)
            days[i]=1
    while que:
        v=que.popleft()
        for x in edge1[v]:
            if days[x]==-1:
                que.append(x)
            days[x]=max(days[x],days[v]+1)
    print(max(days))
        

    

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

M = N*N

def c(a,b):
    if a>b: a,b=b,a
    return a*N+b

G = [[] for _ in range(M)]
for i in range(N):
    a = A[i]
    x = i
    for j in range(N-1-1):
        y1 = a[j]
        y2 = a[j+1]
        G[c(x,y1)].append(c(x,y2))

dp = [0]*M
used = [False]*M
started = [False]*M
finished = [False]*M
for i in range(N):
    for j in range(i+1, N):
        s = c(i,j)
        if used[s]: continue
        used[s] = True
        stk = [(s, 0)]
        while stk:
            v, s = stk.pop()
            if s == 0:
                started[v] = True
                stk.append((v, 1))
                for to in G[v]:
                    if started[to] and not finished[to]:
                        print(-1)
                        exit()
                    if used[to]: continue
                    used[to] = True
                    stk.append((to, 0))
            else:
                finished[v] = True
                for to in G[v]:
                    dp[v] = max(dp[v], dp[to] + 1)

print(max(dp) + 1)

Submission status: Wrong Answer

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

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

def c(a,b):
    if b>a: a,b=b,a
    return a*N+b

G = [[] for _ in range(c(N,N))]
into = [0 for _ in range(c(N,N))]
for i in range(N):
    a = A[i]
    x = i
    for j in range(N-1-1):
        y1 = a[j]
        y2 = a[j+1]
        G[c(x,y1)].append(c(x,y2))
        into[c(x,y2)] += 1

into0 = []
for i in range(N):
    for j in range(i+1, N):
        x = c(i,j)
        if into[x] == 0: into0.append(x)
if not into0:
    print(-1)
    exit()

from collections import deque
dp = [0]*c(N,N)
for s in into0:
    length = 0
    used = [False]*c(N,N)
    started = [False]*c(N,N)
    finished = [False]*c(N,N)
    used[s] = True
    q = deque([(s, 0)])
    while q:
        v, s = q.popleft()
        if s == 0:
            started[v] = True
            q.append((v, 1))
            for to in G[v]:
                if started[to] and not finished[to]:
                    print(-1)
                    exit()
                dp[to] = max(dp[to], dp[v] + 1)
                if used[to]: continue
                used[to] = True
                q.append((to, 0))
        else:
            finished[v] = True

print(max(dp) + 1)

Submission status: Wrong Answer

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

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

def c(a,b):
    if b>a: a,b=b,a
    return a*N+b
def check(a, b):
    i1, j1 = a//N, a%N
    i2, j2 = b//N, b%N
    return 0 if i1 != j1 != i2 != j2 else 1


E = [[] for _ in range(c(N,N))]
h = [0 for _ in range(c(N,N))] #入次数
for i in range(N):
    a = A[i]
    x = i
    for j in range(N-1-1):
        y1 = a[j]
        y2 = a[j+1]
        E[c(x,y1)].append(c(x,y2))
        h[c(x,y2)] += 1

stack = []
for i in range(N):
    for j in range(i+1, N):
        x = c(i,j)
        if h[x] == 0: stack.append(x)

tpst = []
while stack:
    i = stack.pop()
    tpst.append(i)
    for to in E[i]:
        h[to] -= 1
        if (h[to] == 0): stack.append(to)

if len(tpst) == M:
    ans = 1
    chst = set([tpst[0]//N, tpst[0]%N])
    for i in range(1,M):
        a, b = [tpst[i]//N, tpst[i]%N]
        if a in chst or b in chst:
            ans += 1
            chst = set([a,b])
        else:
            chst.add(a)
            chst.add(b)
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	graph_out = defaultdict(list)
	graph_in = defaultdict(list)
	match_id = [[0]*N for _ in range(N)]

	def toid(i, j):  # 選手から試合IDに変換
		if i > j: i, j = j, i
		return match_id[i][j]

	cnt = 0
	for i in range(N):
		for j in range(N):
			if i < j:
				match_id[i][j] = cnt
				cnt += 1

	for i in range(N):
		for j in range(N-2):
			graph_in[toid(i, A[i][j+1]-1)].append(toid(i, A[i][j]-1))
			graph_out[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))

	cnt = defaultdict(int)  # cntが入り次数に達したら発火
	day = defaultdict(int)
	# checked = [False] * (N*(N-1)//2)
	q = deque([])
	for i, j in combinations(range(N), 2):
		match = match_id[i][j]
		if not graph_in[match]:  # 入り次数0
			q.append(match)
			day[match] = 1
			# checked[match] = True
	if not q:
		print(-1)
		exit()

	ans = 0

	while q:
		n = q.popleft()
		for node in graph_out[n]:
			if day[node]:  # 閉路
				print(-1)
				exit()
			cnt[node] += 1
			if cnt[node] == len(graph_in[node]):
				q.append(node)
				day[node] = day[n] + 1
				ans = day[node]

	print(ans) 

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	graph_out = defaultdict(list)
	graph_in = defaultdict(list)
	match_id = [[0]*N for _ in range(N)]

	def toid(i, j):  # 選手から試合IDに変換
		if i > j: i, j = j, i
		return match_id[i][j]

	cnt = 0
	for i in range(N):
		for j in range(N):
			if i < j:
				match_id[i][j] = cnt
				cnt += 1

	for i in range(N):
		for j in range(N-2):
			graph_in[toid(i, A[i][j+1]-1)].append(toid(i, A[i][j]-1))
			graph_out[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))

	cnt = defaultdict(int)  # cntが入り次数に達したら発火
	day = defaultdict(int)
	checked = [False] * (N*(N-1)//2)
	q = deque([])
	for i, j in combinations(range(N), 2):
		match = match_id[i][j]
		if not graph_in[match]:  # 入り次数0
			q.append(match)
			day[match] = 1
			checked[match] = True
	if not q:
		print(-1)
		exit()

	ans = 0

	while q:
		n = q.popleft()
		for node in graph_out[n]:
			if checked[node]:  # 閉路
				print(-1)
				exit()
			cnt[node] += 1
			if cnt[node] == len(graph_in[node]):
				q.append(node)
				day[node] = day[n] + 1
				ans = day[node]

	print(ans) 

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	graph_out = defaultdict(list)
	graph_in = defaultdict(list)
	match_id = [[0]*N for _ in range(N)]

	def toid(i, j):  # 選手から試合IDに変換
		if i > j: i, j = j, i
		return match_id[i][j]

	cnt = 0
	for i in range(N):
		for j in range(N):
			if i < j:
				match_id[i][j] = cnt
				cnt += 1

	for i in range(N):
		for j in range(N-2):
			graph_in[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))
			graph_out[toid(i, A[i][j+1]-1)].append(toid(i, A[i][j]-1))

	cnt = defaultdict(int)  # cntが入り次数に達したら発火
	day = defaultdict(int)
	checked = [False] * (N*(N-1)//2)
	q = deque([])
	for i, j in combinations(range(N), 2):
		match = match_id[i][j]
		if not graph_in[match]:  # 入り次数0
			q.append(match)
			day[match] = 1
			checked[match] = True
	if not q:
		print(-1)
		exit()

	ans = 0

	while q:
		n = q.popleft()
		for node in graph_out[n]:
			if checked[node]:  # 閉路
				print(-1)
				exit()
			cnt[node] += 1
			if cnt[node] == len(graph_in[node]):
				q.append(node)
				day[node] = day[n] + 1
				ans = day[node]

	print(ans) 

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	graph_out = defaultdict(list)
	graph_in = defaultdict(list)

	for i in range(N):
		for j in range(N-2):
			fro = "-".join(map(str, sorted([i, A[i][j]-1])))
			to = "-".join(map(str, sorted([i, A[i][j+1]-1])))
			graph_in[to].append(fro)
			graph_out[fro].append(to)

	cnt = defaultdict(int)  # cntが入り次数に達したら発火
	day = defaultdict(int)
	q = deque([])
	for i, j in combinations(range(N), 2):
		match = "{}-{}".format(str(i), str(j))
		if not graph_in[match]:  # 入り次数0
			q.append(match)
			day[match] = 1
	if not q:
		print(-1)
		exit()

	ans = 0
	while q:
		n = q.popleft()
		for node in graph_out[n]:
			if day[node]:  # 閉路
				print(-1)
				exit()
			cnt[node] += 1
			if cnt[node] == len(graph_in[node]):
				q.append(node)
				day[node] = day[n] + 1
				ans = day[node]

	print(ans) 

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = []
for i in range(n):
    b = inpl()
    a.append(deque(b))
res = 0
while True:
    res += 1
    end = False
    can = False
    s = set()
    for i in range(n):
        if i in s or a[i] == deque([]): continue
        end = True
        chk = a[i][0] - 1
        if a[chk][0] == i+1:
            can = True
            a[i].popleft(); a[chk].popleft()
            s.add(i); s.add(chk)
    if end:
        if can: continue
        print(-1)
        quit()
    print(res)
    break

Submission status: Wrong Answer

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

n = int(input())
U = n**2
G = [[] for _ in range(U)]
parent = [0]*U
for i in range(n):
  A = list(map(lambda x:int(x)-1, input().split()))
  for j in range(n-2):
    a = A[j]
    b = A[j+1]
    G[min(i, a)*n+max(i, a)].append(min(i, b)*n+max(i, b))
    parent[min(i, b)*n+max(i, b)] += 1

stack = [(i*n+j, 1) for i in range(n-1) for j in range(i+1, n) if not parent[i*n+j]]
ans = 1
cnt = 0
while stack:
  v, t = stack.pop()
  ans = max(ans, t)
  cnt += 1
  for nv in G[v]:
    parent[nv] -= 1
    if not parent[nv]:
      stack.append((nv, t+1))
if cnt == n*(n-1)//2:
  print(ans)
else:
  print(-1)