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
input = sys.stdin.readline
from collections import defaultdict

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[0]+[list(map(int,input().split())) for _ in range(n)]
pos=[0]*(n+1)
ans=0
while 1:
  flag=False
  cnt=0
  check=[0]*(n+1)
  for i in range(1,n+1):
    if check[i]==1:
      continue
    if pos[i]==n-1:
      cnt+=1
      continue
    pair=arr[i][pos[i]]
    if check[pair]==1:
      continue
    if arr[pair][pos[pair]]==i:
      flag=True
      pos[i]+=1
      pos[pair]+=1
      check[i]=1
      check[pair]=1
  if cnt==n:
    break
  if flag==False:
    print(-1)
    break
  ans+=1
  print(ans,pos)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[0]+[list(map(int,input().split())) for _ in range(n)]
pos=[0]*(n+1)
ans=0
while 1:
  flag=False
  cnt=0
  check=[0]*(n+1)
  for i in range(1,n+1):
    if check[i]==1:
      continue
    if pos[i]==n-1:
      cnt+=1
      continue
    pair=arr[i][pos[i]]
    if check[pair]==1:
      continue
    if arr[pair][pos[pair]]==i:
      flag=True
      pos[i]+=1
      pos[pair]+=1
      check[i]=1
      check[pair]=1
  if cnt==n:
    print(ans)
    break
  if flag==False:
    print(-1)
    break
  ans+=1
  print(ans,pos)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [[[] for i in range(n)] for i in range(n)]
c = 0
day = 0
for i in range(n):
    ap = [i,a[i][0]-1]
    ap.sort()
    for j in range(1,n-1):
        p = [i,a[i][j]-1]
        p.sort()
        l[ap[0]][ap[1]].append(p)
        ap = p
rl = [[0 for i in range(n)] for i in range(n)]
d = deque()
for i in range(n):
    for j in range(n):
        if i < j:
            if len(l[i][j]) > 0:
                for k in l[i][j]:
                    rl[k[0]][k[1]] += 1
#print(rl)
for i in range(n):
    for j in range(n):
        if i < j:
            if rl[i][j] == 0:
                d.append([[i,j],0])
al = []
key = 0
#print(l)
if len(d) == 0:
    key = 1
while len(d):
    now,day = d.pop()
    day += 1
    if len(l[now[0]][now[1]]) == 0:
        al.append(day)
    else:
        for i in l[now[0]][now[1]]:
            if rl[i[0]][i[1]] == 1:
                rl[i[0]][i[1]] -= 1
                d.append([i,day])
            else:
                rl[i[0]][i[1]] -= 1
    if day > n*(n-1)//2:
        key = 1
        break
md = 0
for i in range(n):
    md += sum(rl[i])
if key == 1 or md > 0:
    print(-1)
else:
    print(max(al))

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [[[] for i in range(n)] for i in range(n)]
c = 0
day = 0
for i in range(n):
    ap = [i,a[i][0]-1]
    ap.sort()
    for j in range(1,n-1):
        p = [i,a[i][j]-1]
        p.sort()
        l[ap[0]][ap[1]].append(p)
        ap = p
rl = [[0 for i in range(n)] for i in range(n)]
d = deque()
for i in range(n):
    for j in range(n):
        if i < j:
            if len(l[i][j]) > 0:
                for k in l[i][j]:
                    rl[k[0]][k[1]] = 1
#print(rl)
for i in range(n):
    for j in range(n):
        if i < j:
            if rl[i][j] == 0:
                d.append([[i,j],0])
rl=[[0 for i in range(n)] for i in range(n)]
al = []
key = 0
#print(l)
while len(d):
    now,day = d.pop()
    if rl[now[0]][now[1]] == 0:
        rl[now[0]][now[1]] = 1
    else:
        key = 1
        break
    day += 1
    if len(l[now[0]][now[1]]) == 0:
        al.append(day)
        rl = [[0 for i in range(n)] for i in range(n)]
    else:
        for i in l[now[0]][now[1]]:
            d.append([i,day])
if key == 1 or len(d) == 0:
    print(-1)
else:
    print(max(al))

Submission status: Wrong Answer

Solution code:
n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if semi:
    print(-1)
  if not semi:
    print(499500)

Submission status: Wrong Answer

Solution code:
n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1
    if ans>1000:
        flag=False
        semi=True
judge=True
for i in range(n):
    if finished[i]==False:
        judge=False
        break
if judge:
    print(ans)
else:
    if not semi:
        print(-1)
    else:
        print(min(ans,499500))

Submission status: Wrong Answer

Solution code:
n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1
    if ans>1000:
        flag=False
        semi=True
judge=True
for i in range(n):
    if finished[i]==False:
        judge=False
        break
if judge:
    print(ans)
else:
    if not semi:
        print(-1)
    else:
        print(499500)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]
candidate = list(range(N))
match = 0
day = 0

while True:
    day += 1
    used = set()
    next = set()
    bool = False
    for c in candidate:
        op = A[c][0] - 1
        if c in used or op in used:
            continue
        if A[op][0] - 1 == c:
            bool = True
            A[c].popleft
            A[op].popleft
            match += 1
            next |= {c, op}
            used |= {c, op}
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()
    candidate = next

print(day)

Submission status: Wrong Answer

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

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

id = [0]*N
Lock = [-1]*N
ans = 0
flag = [True]*N
min_id = N-2
while(min_id < N-1):
    ans += 1
    if ans > N**2:
        break
    tmp = set()
    tmp_min = N
    for i in range(N):
        if id[i] >= N-1:
            continue
        else:
            if Lock[i] >= 0:
                continue
            else:
                if Lock[A[i][id[i]]-1] == i and i not in tmp:
                    Lock[A[i][id[i]]-1] = -1
                    id[A[i][id[i]]-1] += 1
                    tmp.add(A[i][id[i]]-1)
                    id[i] += 1
                else:
                    if i not in tmp:
                        Lock[i] = A[i][id[i]]-1
        tmp_min = min(tmp_min, id[i])
    min_id = tmp_min
if ans > N**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)]

id =[0]*N
Lock=[-1]*N
ans=0
while(min(id)<N-1):
  ans+=1
  if ans > N**2:
    break
  for i in range(N):
    if id[i]>=N-1:
      continue
    else:
      if Lock[i]>=0:
        continue
      else:
        if Lock[A[i][id[i]]-1]==i:
          Lock[A[i][id[i]]-1]=-1
          id[A[i][id[i]]-1] +=1
          id[i]+=1
        else:
          Lock[i]=A[i][id[i]]-1
if ans>N**2:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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

size = N*N
d = [set() for _ in range(size)]
e = [set() for _ in range(size)]

for i, j in enumerate(l, start=1):
    p = 0
    for k in j:
        while 1:
            s = (i, k) if i<k else (k, i)
            if not s in d[p] and not i in e[p] and not k in e[p]:
                d[p]|={s}
                e[p]|={i,k}
                break
            elif s in d[p]:
                p += 1
                break
            else:
                p += 1

ans = size-sum(not i for i in d)
total = N*(N-1)//2

print(ans if ans<=total else -1)

Submission status: Wrong Answer

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

d = [set() for _ in range(N-1)]
e = [set() for _ in range(N-1)]

size = N-1
for i, j in enumerate(l, start=1):
    p = 0
    for k in j:
        while p<size:
            s = (i, k) if i<k else (k, i)
            if not s in d[p] and not i in e[p] and not k in e[p]:
                d[p]|={s}
                e[p]|={i,k}
                break
            elif s in d[p]:
                p += 1
                break
            else:
                p += 1
                if p>=size:
                    d.append(set())
                    e.append(set())
                    size += 1

ans = len(d)
print(ans if ans <= N*(N-1)//2 else -1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n, pn):
    nn = edge[n]
    if nn == pn:
        game.append(n)
        game.append(pn)
    elif track[nn] == 0:
        track[nn] = 1
        dfs(nn, n)


N = int(input())

G = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
    edge[i] = G[i][cur[i]]

day = 0
cnt = 0
while cnt < N:
    day += 1
    track = [0] * N
    game = []
    for i in range(N):
        if track[i] == 0:
            track[i] == 1
            dfs(i, -1)
    if len(game) == 0:
        print(-1)
        exit()
    else:
        for j in game:
            cur[j] += 1
            c = cur[j]
            if c >= N - 1:
                edge[j] = j
                cnt += 1
            else:
                edge[j] = G[j][c]

print(day)

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)]
    b = [[] for _ in range(N-1)]
    for i in range(N):
        for j in range(N-1):
            b[j].append(A[i][j]-1)

    ans = 0
    for i in range(N-1):
        date =  0
        for j in range(N):
            go = [True for _ in range(N)]
            now = j
            go[now] = False
            d = 0
            while go[b[i][now]]:
                now = b[i][now]
                go[now] = False
                d += 1
            if (b[i][now] == j and d != 1):
                print(-1)
                exit()
            date = max(date,d)
        ans += d
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
                w[i] = -1
                w[o] = -1
        if not nxt:
            return -1
        cur = []
        for i in nxt:
            if A[i]:
                w[i] = A[i].pop()
                cur.append(i)
            else:
                r -= 1
    return d


print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
                w[i] = -1
                w[o] = -1
        if not nxt:
            return -1
        for i in nxt:
            if A[i]:
                w[i] = A[i].pop()
            else:
                w[i] = -1
                r -= 1
        cur = nxt
    return d


print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = N * (N - 1) / 2
    print(t)
    d = 0
    n = set(range(N))
    while True:
        p = 0
        l = set()
        d += 1
        for i in n:
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j].pop() 
                A[i].pop()
                t -= 1
                p += 1
        n = l
        if t == 0:
            print(d)
            break
        if p == 0:
            print(-1)
            break
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Q = deque(range(N))

days = [0]*N  # 各選手の現在の日付
pairs = [0]*N  # 次の対戦相手を管理(wait的な)

while Q:
    x = Q.popleft()  # 試合する人
    if len(matches[x]) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x].pop(0)  # xの次の対戦相手
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        Q.append(x)
        Q.append(y)
    else:
        pairs[x] = y

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)

Submission status: Wrong Answer

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


def topological_sort(V, E_in, E_from):
    '''
    # Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


E_in = defaultdict(lambda: set())
E_from = defaultdict(lambda: set())

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        E_from[make_hash(i, node_to)].add(make_hash(i, node_from))
        E_in[make_hash(i, node_from)].add(make_hash(i, node_to))

START = set()
END = set()
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        if len(E_in[h]) == 0:
            START.add(h)
        if len(E_from[h]) == 0:
            END.add(h)
if len(START) == 0 or len(END) == 0:
    print(-1)
else:
    top = topological_sort(N**2, E_from=E_from, E_in=E_in)
    dist = defaultdict(int)
    for t in top:
        for nex in E_from[t]:
            dist[nex] = max(dist[nex], dist[t]+1)
    print(max(dist.values())+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def topological_sort(V, E_in, E_from):
    '''
    # Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


E_in = defaultdict(lambda: set())
E_from = defaultdict(lambda: set())

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        E_from[make_hash(i, node_to)].add(make_hash(i, node_from))
        E_in[make_hash(i, node_from)].add(make_hash(i, node_to))

START = set()
END = set()
for i in E_from.keys():
    if len(E_in[i]) == 0:
        START.add(i)
    if len(E_from[i]) == 0:
        END.add(i)
if len(START) == 0 or len(END) == 0:
    print(-1)
else:
    top = topological_sort(N**2, E_from=E_from, E_in=E_in)
    dist = defaultdict(int)
    for t in top:
        for nex in E_from[t]:
            dist[nex] = max(dist[nex], dist[t]+1)
    print(max(dist.values())+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def topological_sort(V, E_in, E_from):
    '''
    # Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


E_in = defaultdict(lambda: set())
E_from = defaultdict(lambda: set())

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        E_from[make_hash(i, node_to)].add(make_hash(i, node_from))
        E_in[make_hash(i, node_from)].add(make_hash(i, node_to))

if all(len(E_from[i]) == 0 and len(E_in[i]) == 0 or len(E_from[i])*len(E_in[i]) != 0 for i in E_from.keys()):
    print(-1)
else:
    top = topological_sort(N**2, E_from=E_from, E_in=E_in)
    dist = defaultdict(int)
    for t in top:
        for nex in E_from[t]:
            dist[nex] = max(dist[nex], dist[t]+1)
    print(max(dist.values())+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def topological_sort(V, E_in, E_from):
    '''
    # Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


E_in = defaultdict(lambda: set())
E_from = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        E_from[make_hash(i, node_to)].add(make_hash(i, node_from))
        E_in[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

if all(len(E_from[i]) == 0 and len(E_in[i]) == 0 or len(E_from[i])*len(E_in[i]) != 0 for i in E_from.keys()):
    print(-1)
else:
    top = topological_sort(N**2, E_from=E_from, E_in=E_in)

    dist = defaultdict(int)
    for t in top:
        for nex in E_from[t]:
            dist[nex] = max(dist[nex], dist[t]+1)
    print(max(dist.values())+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def topological_sort(V, E_in, E_from):
    '''
    # Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


E_in = defaultdict(lambda: set())
E_from = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        E_from[make_hash(i, node_to)].add(make_hash(i, node_from))
        E_in[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

top = topological_sort(N**2, E_from=E_from, E_in=E_in)
if all(len(E_from[i]) == 0 and len(E_in[i]) == 0 or len(E_from[i])*len(E_in[i]) != 0 for i in E_from.keys()):
    print(-1)
else:
    top = topological_sort(N**2, E_from=E_from, E_in=E_in)

    dist = defaultdict(int)
    for t in top:
        for nex in E_from[t]:
            dist[nex] = max(dist[nex], dist[t]+1)
    print(max(dist.values())+1)

Submission status: Wrong Answer

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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_to)].add(make_hash(i, node_from))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(h)
        if pointing_i == 0:
            DST.add(h)
if len(START) == 0 or len(DST) == 0:
    print(-1)

else:
    Q = [[v, 1] for v in DST]
    visited = set()
    for v in DST:
        visited.add(v)
    dist = 1
    while Q:
        q, d = Q.pop()
        for nex in from_to[q]:
            if nex in visited:
                continue
            Q.append([nex, d+1])
            dist = d+1
            visited.add(nex)
    print(dist)

Submission status: Wrong Answer

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


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_to)].add(make_hash(i, node_from))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(h)
        if pointing_i == 0:
            DST.add(h)
if len(START) == 0 or len(DST) == 0:
    print(-1)

else:
    Q = [[v, 1] for v in DST]
    dist = 1
    while Q:
        q, d = Q.pop()
        for nex in from_to[q]:
            Q.append([nex, d+1])
            dist = d+1
    print(dist)