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: Time Limit Exceeded

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n
    aconditions = {}
    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)
        aconditions[i] = set(al)

    # print(agrid)
    # print(aconditions)

    ans = 0
    while True:
        match = set()
        for i in range(n):
            if i in match:  # この日対戦済み
                continue
            if len(aconditions[i]) == 0:  # もう全部対戦済み
                continue
            target = agrid[i][agrid_pointer[i]]
            if target in match:  # この日対戦済み
                continue
            if agrid_pointer[target] == n - 1 or agrid[target][agrid_pointer[target]] != i:  # 次対戦できない
                continue
            # can match
            aconditions[i].remove(target)
            agrid_pointer[i] += 1

            aconditions[target].remove(i)
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for v in aconditions.values():
        if len(v) != 0:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

#B
def B():
    a,b = LI()
    for i in range(10000):
        if 1+i*a-i >= b:
            print(i)
            return
    return

#C
def C():
    n = I()
    a = LI()
    ans = 0
    r = 1
    for l in range(n):
        if r == l:
            r += 1
        while r < n and a[r-1] >= a[r]:
            r += 1
        ans = max(ans, r-l-1)
    print(ans)
    return

#D
def D():
    n = I()
    print(n*(n-1)>>1)
    return

#E
def E():
    n = I()
    a = LIR(n)
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    index = [0]*n
    ma = n*(n-1)
    m = ma>>1
    for t in range(m):
        k = [1 if index[i] < n-1 else 0 for i in range(n)]
        for i in range(n):
            if k[i]:
                j = a[i][index[i]]
                if k[j]:
                    if a[j][index[j]] == i:
                        index[i] += 1
                        index[j] += 1
                        k[i] = 0
                        k[j] = 0
        if sum(index) == ma:
            print(t+1)
            return
    print(-1)
    return

#F
def F():
    n = I()
    p = LIR(n)

    return

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

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

for i in range(N):
    A[i].append(-1)
A.append([-1])

def f():
    can_use = [n for n in range(N) if A[A[n][0]][0] == n]
    for n in can_use:
        A[n].popleft()
    return len(can_use)

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

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

day = 0
while True:
    popped = 0
    plist = set()
    zeros = 0
    for i in range(n):
        if len(a[i]) == 0:
            zeros += 1
            continue
        if i in plist:
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if num in plist:
            continue
        if a[num][0] - 1 == i:
            plist.add(num)
            a[i].popleft()
            a[num].popleft()
            popped += 1
    if popped == 0:
        if zeros == n:
            break
        else:
            day = -1
            break
    day += 1

print(day)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ass = []
    for _ in range(N):
        As = list(map(lambda x: int(x)-1, input().split()))
        Ass.append(As+[N])

    iAs = [0] * N
    ans = 1
    while True:
        useds = [False] * N
        isOK = False
        for i in range(N):
            if useds[i]: continue
            j = Ass[i][iAs[i]]
            if j == N or useds[j]: continue
            if Ass[j][iAs[j]] == i:
                iAs[i] += 1
                iAs[j] += 1
                useds[i] = True
                useds[j] = True
                isOK = True
        if not isOK:
            print(-1)
            return
        if sum(iAs) == N*(N-1):
            print(ans)
            return
        ans += 1

solve()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

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

ans = 0
match = [True]
while 1:
    match = []
    done = [False]*N
    for i in range(N):
        if done[i] : continue
        if not A[i] : continue
        j = A[i][-1]
        if A[j][-1] == i:
            done[i] = True
            done[j] = True
            match.append((i,j))
    for i in range(N):
        if done[i] : A[i].pop()
    if not match: break
    ans += 1
if sum(len(B) for B in A)>0: ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: a-1, As))))
  A.append(As)
#print(A)
d = 0
n = 0
while True:
  s = set()
  gs = []
  for i in range(N):
    if A[i] == []:
      continue
    j = A[i][-1]
    if i in s or j in s:
      continue
    if A[j] == []:
      continue
    if A[j][-1] == i:
      gs.append((i, j))
      n += 1
      A[i].pop()
      A[j].pop()
      s.add(i)
      s.add(j)
  if gs == []:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  d += 1
print(d)

Submission status: Time Limit Exceeded

Solution code:
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

from collections import deque
def solve(N, A):
    ans = 0
    todo = N * (N-1)
    to_inspect = range(N)
    while True:
        ans += 1
        found = False
        pairings = [None] * N
        to_inspect2 = set()
        for i in to_inspect:
            row = A[i]
            if row:
                j = row[0]
                if pairings[i] == pairings[j] == None and A[j] and A[j][0] == i:
                    pairings[i] = j
                    pairings[j] = i
                    row.popleft()
                    A[j].popleft()
                    found = True
                    todo -= 2
                    to_inspect2.add(i)
                    to_inspect2.add(j)
        if not todo: return ans
        if not found: return -1
        to_inspect = to_inspect2
    
        
                
        

N = rri()
A = []
for _ in xrange(N):
    row = rrm()
    A.append(deque(x-1 for x in row))
print solve(N, A)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = [None for _ in range(n)]
for i in range(n):
    tmp = list(map(lambda a: int(a) - 1, input().split()))
    a[i] = tmp

updated = True
cnt = 0
while updated:
    updated = False
    pops = []
    for i in range(n):
        if len(a[i]) == 0 or len(a[a[i][0]]) == 0:
            continue
        if i == a[a[i][0]][0]:
            pops.append(i)
    if len(pops) > 0:
        updated = True
        cnt += 1
    for p in pops:
        a[p].pop(0)
valid = True
for i in range(n):
    if len(a[i]) > 0:
        valid = False
        break
if valid:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

a = []

for i in range(N):

    A = list(map(int,input().split()))

    a.append(A)

day = 0
flag = True
end = 0

while end < N:

    day += 1

    Q = []
    flag = False

    for i in range(N):


        if len(a[i]) > 0  and a[ a[i][0]-1 ][0] == i + 1 and a[i][0] > i + 1:

            Q.append(a[i][0])
            Q.append(i + 1)

            flag = True

    if not flag:
        break

    #print (a,Q)

    for q in Q:
        del a[q-1][0]

        if len(a[q-1]) == 0:
            end += 1



if flag:
    print (day)
else:
    print (-1)

Submission status: Time Limit Exceeded

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

ans = 0
p = [0] * n
while True:
    ans += 1
    u = [False] * n
    for i in range(n):
        if p[i] >= n - 1:
            continue
        o = a[i][p[i]] - 1
        # print('i={} o={}'.format(i, o))
        if a[o][p[o]] - 1 == i:
            u[i] = True
    has_update = False
    has_next = False
    for i in range(n):
        if u[i]:
            p[i] += 1
            has_update = True
        if p[i] < n - 1:
            has_next = True
    if not has_update:
        print(-1)
        sys.exit(0)
    if has_next:
        continue
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = [list(map(int, raw_input().split(" "))) for _ in range(N)]
total = N * (N - 1) // 2

match_today = 0
day_count = 0
match_count = 0
today_game = [False] * N

while match_count < total:
    today_game = [False] * N
    day_count += 1
    for i, a in enumerate(A):
        if not a:
            continue
        x = a[0] - 1
        if A[x][0] == i + 1 and not today_game[i] and not today_game[x]:
            match_count += 1
            match_today += 1
            del a[0]
            del A[x][0]
            today_game[i] = True
            today_game[x] = True
    if match_today == 0 and match_count < total:
        print(-1)
        break
else:
    print(day_count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

game = [[] for i in range(n)]

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

index = [0 for i in range(n)]
days = 0
finish = 0
tot = (n*(n-1))//2
flag = True
ok = True
tempok = False
while flag:
    tempok = False
    cant = set()
    for i in range(n):
        if i in cant:
            continue
        if index[i] >= n-1:
            continue
        vs = game[i][index[i]]
        vs -= 1
        if vs in cant:
            continue
        if game[vs][index[vs]]-1 == i:
            finish += 1
            index[i] += 1
            index[vs] += 1
            tempok = True
            cant.add(vs)
            cant.add(i)
            # print(i,vs)
        if finish >= tot:
            ok = True
            flag = False
            break
    if not tempok:
        ok = False
        break
    days += 1
    # print(finish)
    # print(tot)
    # print(days)
    # print(index)
    # print(game)

if not ok:
    print(-1)
else:
    print(days)

Submission status: Time Limit Exceeded

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    agrid = []
    aconditions = {}
    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(deque(al))
        aconditions[i] = set(al)

    # print(agrid)
    # print(aconditions)

    ans = 0
    while True:
        match = set()
        for i in range(n):
            if i in match:  # この日対戦済み
                continue
            if len(aconditions[i]) == 0:  # もう全部対戦済み
                continue
            target = agrid[i][0]
            if target in match:  # この日対戦済み
                continue
            if agrid[target][0] != i:  # 次対戦できない
                continue
            # can match
            aconditions[i].remove(target)
            agrid[i].popleft()
            aconditions[target].remove(i)
            agrid[target].popleft()
            match.add(i)
            match.add(target)

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for v in aconditions.values():
        if len(v) != 0:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N = int(input())
    A = [deque(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
    ans = 0
    while True:
        empty = 0
        used = set()
        for i in range(N):
            if len(A[i]) == 0:
                empty += 1
                continue
            j = A[i][0]
            if len(A[j]) and A[j][0] == i and i not in used and j not in used:
                used.add(i)
                used.add(j)
                A[i].popleft()
                A[j].popleft()
        if empty == N:
            break
        if len(used) == 0:
            ans = -1
            break
        ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0
p = [0] * n
while True:
    ans += 1
    u = [False] * n
    for i in range(n):
        if p[i] >= n - 1:
            continue
        o = a[i][p[i]] - 1
        # print('i={} o={}'.format(i, o))
        if a[o][p[o]] - 1 == i:
            u[i] = True
    has_update = False
    for i in range(n):
        if u[i]:
            p[i] += 1
            has_update = True
    if not has_update:
        print(-1)
        sys.exit(0)
    has_next = False
    for i in range(n):
        if p[i] < n - 1:
            has_next = True
    if has_next:
        continue
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
t = 0
f = 1
cur = [0]*(n+1)
while f:
    f = 0
    done = [0]*(n+1)
    for i in range(1,n+1):
        if done[i] or cur[i] == n-1:
            continue
        op = a[i-1][cur[i]]
        if a[op-1][cur[op]] == i and not done[op]:
            cur[i] += 1
            cur[op] += 1
            done[i] = 1
            done[op] = 1
            f = 1
    if f:
      t += 1
if any([x<n-1 for x in cur[1:]]):
    print(-1)
else:
    print(t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
alist=[]
nowlist=[]
klist=[]
incre=0
error=0
day=0

for i in range(n):
    alist.append(list(map(int, input().split())))

for i in range(n):
    nowlist.append(0)

while error==0 and incre<n*(n-1):
    koho=[]
    for i in range(n):
        if nowlist[i]<n-1:
            small=sorted([i+1, alist[i][nowlist[i]]])
            koho.append(small)
    koho=sorted(koho)
    swit=0
    for i in range(len(koho)-1):
        if koho[i]==koho[i+1]:
            nowlist[koho[i][0]-1]+=1
            nowlist[koho[i][1]-1]+=1
            incre+=2
            swit=1
    day+=1
    if swit==0:
        day=-1
        error=1
    #print(nowlist)

print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split(" "))) for _ in range(N)]
total = N * (N - 1) // 2

match_today = 0
day_count = 0
match_count = 0
today_game = [False] * N

while match_count < total:
    today_game = [False] * N
    day_count += 1
    for i, a in enumerate(A):
        if not a:
            continue
        x = a[0] - 1
        if A[x][0] == i + 1 and not today_game[i] and not today_game[x]:
            match_count += 1
            match_today += 1
            del a[0]
            del A[x][0]
            today_game[i] = True
            today_game[x] = True
    if match_today == 0 and match_count < total:
        print(-1)
        break
else:
    print(day_count)

Submission status: Time Limit Exceeded

Solution code:
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

from collections import deque
def solve(N, A):
    ans = 0
    todo = N * (N-1)
    while True:
        ans += 1
        found = False
        pairings = [None] * N
        for i, row in enumerate(A):
            if row:
                j = row[0]
                if pairings[i] == pairings[j] == None and A[j] and A[j][0] == i:
                    pairings[i] = j
                    pairings[j] = i
                    row.popleft()
                    A[j].popleft()
                    found = True
                    todo -= 2
        if not todo: return ans
        if not found: return -1
        
                
        

N = rri()
A = []
for _ in xrange(N):
    row = rrm()
    A.append(deque(x-1 for x in row))
print solve(N, A)

Submission status: Accepted

Solution code:
import collections

def topological():
    """トポロジカルソート (有向グラフ) O(V+E)

    Vars:
        n (int):     頂点数
        edge (list): 辺に関するリスト (edge[i]: iを始点に持つ辺の終点のリスト)
    
    Returns:
        list/bool: トポロジカル順序 (閉路が存在する場合はFalse)
    """
    in_degree = [0] * n
    for i in range(n):
        for v in edge[i]:
            in_degree[v] += 1
    
    nodelist = collections.deque()
    for i in range(n):
        if in_degree[i] == 0:
            nodelist.append(i)
    
    res = []
    while nodelist:
        p = nodelist.popleft()
        for q in edge[p]:
            in_degree[q] -= 1
            depth[q] = max(depth[q], depth[p] + 1)
            if in_degree[q] == 0:
                nodelist.append(q)
        
        res.append(p)
    
    if len(res) == n:
        return res
    else:
        return False


m = int(input())
a = [list(map(int, input().split())) for _ in range(m)]

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

num = 0
table = [[-1] * m for _ in range(m)]
for i in range(m):
    for j in range(i+1, m):
        table[i][j] = num
        table[j][i] = num
        num += 1

edge = [[] for _ in range(n)]
for i in range(m):
    for j in range(m-2):
        edge[table[i][a[i][j]-1]].append(table[i][a[i][j+1]-1])

depth = [0] * n
l = topological()

if not l:
    print(-1)
else:
    print(max(depth) + 1)

Submission status: Accepted

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

l = [i for i in range(n)]
pos = [0] * n
res = 0
cnt = 0
while True:
    res += 1
    flag = True
    tmp = l.copy()
    l = []
    used = [False] * n
    for v in tmp:
        if used[v] or pos[v] == n - 1:
            continue

        opp = a[v][pos[v]] - 1

        if used[opp] or pos[opp] == n - 1:
            continue

        if a[opp][pos[opp]] - 1 == v:
            pos[v] += 1
            pos[opp] += 1
            l.append(v)
            l.append(opp)
            used[v] = True
            used[opp] = True
            flag = False
            if pos[v] == n - 1:
                cnt += 1
            if pos[opp] == n - 1:
                cnt += 1

    if flag:
        print(-1)
        break

    if cnt == n:
        print(res)
        break

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(input())
    A = [[]]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #AR[i][j] => iにとって選手jとの試合が何番目か
    AR = [[]]
    for i in range(1,N+1):
        AR.append([0]*(N+1))
        for j in range(1,N):
            b = A[i][j]
            AR[i][b] = j

    edges =[[[] for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            jForI = AR[i][j]
            if jForI < N-1:
                nxForI = A[i][jForI+1]
                edges[i][j].append((min(i,nxForI),max(i,nxForI)))
            iForJ = AR[j][i]
            if iForJ < N-1:
                nxForJ = A[j][iForJ+1]
                edges[i][j].append((min(j,nxForJ),max(j,nxForJ)))
    del A
    del AR

    steps = {}
    def dfs(i,j):
        #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
        if (i,j) not in steps:
            steps[(i,j)] = 0
            res = 1
            for a,b in edges[i][j]:
                res = max(res,dfs(a,b)+1)
            steps[(i,j)] = res
        elif steps[(i,j)] == 0:
            print(-1)
            exit()
        return steps[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j))
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
import bisect
import math
import itertools
from collections import deque
import copy

# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    L = [[] for _ in range(N + 1)]

    for j in range(N):
        a = list(map(int, input().split()))
        L[j + 1] = deque(a)


    k =0

    current_revise =set(range(N+1))
    while k<50000000: # １日分の作業

        pre_revise =copy.copy(current_revise)
        current_revise =set()

        for i in pre_revise: #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and i not in current_revise and can not in current_revise:
                L[i].popleft()
                L[can].popleft()

                current_revise.add(i)
                current_revise.add(can)
        k += 1

        if len(current_revise)==0:
            break


    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
graph = [[[] for _ in range(n+1)] for _ in range(n+1)]
indeg = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    a = tuple(map(int, input().split()))
    for j, v in enumerate(a):
        if j == n-2:
            continue
        tmp = (min(i, a[j+1]), max(i, a[j+1]))
        indeg[tmp[0]][tmp[1]] += 1
        if i < v:
            graph[i][v].append(tmp)
        else:
            graph[v][i].append(tmp)

cnt = n * (n-1)//2
q = deque([])
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if indeg[i][j] == 0:
            q.append((i, j, 1))
            cnt -= 1

ans = -1
while q:
    x, y, day = q.popleft()
    # print(x, y, day)
    ans = max(ans, day)
    for p, r in graph[x][y]:
        if indeg[p][r] == 0:
            continue
        indeg[p][r] -= 1
        if indeg[p][r] == 0:
            q.append((p, r, day+1))
            cnt -= 1

if cnt == 0:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if (i,j) not in stepMemo:
                ans = max(ans,dfs(i,j,set()))
    print(ans)
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = Counter()

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v] += 1
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = len(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                rg[v] -= 1
                if rg[v] == 0:
                    ns.append(v)
                    done += 1
        s = ns

    if done != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = Counter()

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v] += 1
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = len(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                rg[v] -= 1
                if rg[v] == 0:
                    ns.append(v)
                    done += 1
        s = ns

    if done != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()