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:
def main():
    from collections import deque, defaultdict

    n, *aa = [deque(map(int, l.split())) for l in open(0)]

    n = n[0]
    days = 0
    rem = list(range(n))
    while 1:
        today = defaultdict(bool)
        days += 1
    #     print(days, aa)
        new_rem = []
        for i in rem:
#             print(f'{i=}')
            if not today[i]:
                j = aa[i][0]-1
#                 print(f'{j=}')
                if not today[j] and i == aa[j][0]-1:
                    today[i] = True
                    today[j] = True
                    
        changed = False
#         print(f'{rem=}, {today},{aa=}')
        for i in rem:
            if today[i]:
                changed = True
                aa[i].popleft()
            if len(aa[i]):
                new_rem.append(i)
#         print(f'{new_rem=},{aa=}')
        rem = new_rem
        if not changed:
            return -1
        if not len(new_rem):
            return days
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False

    while True:
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
        t += 1
        if t > N * (N-1):
            fail = True
            break
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False

    while True:
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
        t += 1
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque, defaultdict

    n, *aa = [deque(map(int, l.split())) for l in open(0)]

    n = n[0]
    days = 0
    rem = list(range(n))
    while 1:
        today = defaultdict(bool)
        days += 1
    #     print(days, aa)
        complete = True
        new_rem = []
        for i in rem:
            pl = aa[i]
            if not len(aa[i]):
                continue
            else:
                complete = False
                if not today[i] and i+1 == aa[pl[0]-1][0]:
                    today[i] = True
                    today[pl[0]-1] = True
        if complete:
            return days-1
        else:
            changed = False
            for i in rem:
                if today[i]:
                    changed = True
                    aa[i].popleft()
                if len(aa[i]):
                    new_rem.append(i)
            if not changed:
                return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, *aa = [deque(map(int, l.split())) for l in open(0)]

n = n[0]
days = 0
rem = list(range(n))
while 1:
    today = [False]*n
    days += 1
#     print(days, aa)
    complete = True
    new_rem = []
    for i in rem:
        pl = aa[i]
        if not len(aa[i]):
            continue
        else:
            complete = False
            if not today[i] and i+1 == aa[pl[0]-1][0]:
                today[i] = True
                today[pl[0]-1] = True
    if complete:
        print(days-1)
        break
    else:
        changed = False
        for i in rem:
            if today[i]:
                changed = True
                aa[i].popleft()
            if len(aa[i]):
                new_rem.append(i)
        if not changed:
            print(-1)
            break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, *aa = [deque(map(int, l.split())) for l in open(0)]

n = n[0]
days = 0

while 1:
    today = [False]*n
    days += 1
#     print(days, aa)
    complete = True
    for i, pl in enumerate(aa):
        if not len(pl):
            continue
        else:
            complete = False
            if not today[i] and i+1 == aa[pl[0]-1][0]:
                today[i] = True
                today[pl[0]-1] = True
    if sum(today):
        for i,present in enumerate(today):
            if present:
                aa[i].popleft()
    elif complete:
        print(days-1)
        break
    else:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, *aa = [deque(map(int, l.split())) for l in open(0)]

n = n[0]

aa = [None] + aa

today = [0]*(n+1)

days = 0

while 1:
    today = [0]*(n+1)
    days += 1
#     print(days, aa)
    complete = True
    for i, pl in enumerate(aa):
        if i == 0 or len(pl)==0:
            continue
        else:
            complete = False
            if today[i]==0 and i == aa[pl[0]][0]:
                today[i] = 1
                today[pl[0]] = 1
    if sum(today):
        for i,present in enumerate(today):
            if present:
                aa[i].popleft()
    elif complete:
        print(days-1)
        break
    else:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = []
    for _ in range(n):
        t = deque(list((map(lambda x: int(x) - 1, input().split()))))
        A.append(t)

    res = 0
    emp = [1] * n
    while True:
        check = [0] * n
        for i in range(n):
            if A[i] and not check[i]:
                idx = A[i][0]
                if not check[idx] and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    check[i] = check[idx] = 1
            if not A[i]:
                emp[i] = 0
        res += 1
        if sum(emp) == 0:
            break
        if sum(check) == 0:
            print(-1)
            exit()
    print(res)





if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts, A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    if days > 5000:
        print(-1)
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Time Limit Exceeded

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

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts, A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    if days > 50000:
        print(-1)
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Time Limit Exceeded

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

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts, A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    if not flg or days > 1000*1001//2:
        print(-1)
        exit()
    days += 1

Submission status: Time Limit Exceeded

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

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts,A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Time Limit Exceeded

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

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts,A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # if all([cnt == n-1 for cnt in cnts]):
    #     print(days)
    #     exit()  
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Time Limit Exceeded

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

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    for cnt,a in zip(cnts,A):
        if cnt == n-1: tekis.append(-1)
        else: tekis.append(a[cnt])
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    if all([cnt == n-1 for cnt in cnts]):
        print(days)
        exit()  
    if not flg:
        print(-1)
        exit()
    days += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read


def main():
    N, *X = map(int, read().split())
    A = [0] * N
    for i in range(N):
        A[i] = X[(N - 1) * i : (N - 1) * (i + 1)]

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

    total_mathces = 0
    for day in range(M):
        matches = 0
        played = [False] * N
        for i in range(N - 1):
            if played[i] or not A[i]:
                continue
            j = A[i][-1] - 1
            if not played[j] and i + 1 == A[j][-1]:
                played[i] = played[j] = True
                A[i].pop()
                A[j].pop()
                matches += 1

        if matches == 0:
            ans = -1
            break

        total_mathces += matches
        if total_mathces == M:
            ans = day + 1
            break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [0] * N
    for i in range(N):
        A[i] = [int(s) - 1 for s in readline().split()]

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

    total_mathces = 0
    for day in range(M):
        matches = 0
        played = [False] * N
        for i in range(N):
            if played[i] or not A[i]:
                continue
            j = A[i][-1]
            if not played[j] and i == A[j][-1]:
                played[i] = True
                played[j] = True
                A[i].pop()
                A[j].pop()
                matches += 1

        if matches == 0:
            ans = -1
            break

        total_mathces += matches
        if total_mathces == M:
            ans = day + 1
            break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

battle=[]

def mainasu(x):
    return int(x)-1
front=[]

for _ in range(n):
    tmp=list(map(mainasu,input().split()))[::-1]
    front.append(tmp.pop())
    battle.append(tmp)

day=0

#pri()
cnt=0
while 1:
    flag=0
    for i in range(n):
        if front[i]<n and i==front[front[i]]:
            flag=1
            front[front[i]]=n
            front[i]=n

    if flag==0:
        break

    cnt=0
    for i in range(n):
        if front[i]==n:
            if len(battle[i])>0:
                front[i]=battle[i].pop()
            else:
                cnt+=1
    day+=1
    

if cnt==n:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

battle=[]

def mainasu(x):
    return int(x)-1

front=[]

for _ in range(n):
    tmp=list(map(mainasu,input().split()))[::-1]
    front.append(tmp.pop())
    battle.append(tmp)

def pri():
    global front,battle,day
    print(day,front,battle)

day=0

#pri()

while 1:
    flag=0
    for i in range(n):
        if front[i]<n and i==front[front[i]]:
            flag=1
            front[front[i]]=n
            front[i]=n

    for i in range(n):
        if front[i]==n:
            if len(battle[i])>0:
                front[i]=battle[i].pop()
    
    if flag==0:
        break
    
    day+=1

flag=0
for item in front:
    if item!=n:
        flag=1
        break

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

Submission status: Time Limit Exceeded

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

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

que = deque([(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 que:
  v, t = que.pop()
  ans = max(ans, t)
  cnt += 1
  for nv in G[v]:
    parent[nv] -= 1
    if not parent[nv]:
      que.appendleft((nv, t+1))
if cnt == n*(n-1)//2:
  print(ans)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(p, EdgeTo, Length, Visited):
    if p in Visited: return -1
    if p in Length: return Length[p]
    else:
        maxL = 0
        nV = Visited | {p}
        if p not in EdgeTo:
            Length[p] = 1
            return 1
        else:
            for e in EdgeTo[p]:
                back = dfs(e, EdgeTo, Length, nV)
                if back == -1:
                    Length[p] = -1
                    return -1
                else: maxL = max(maxL, back)
            Length[p] = maxL + 1
            return maxL + 1
        
def solve():
    input = sys.stdin.readline
    N = int(input())
    edgeTo = dict()
    edgeFrom = dict()
    Length = dict()
    A = [[int(a) for a in input().split()] for _ in range(N)]
    for i in range(1, N + 1):
        p = (min(i, A[i-1][0]), max(i, A[i-1][0]))
        for j in range(1, N - 1):
            nextp = (min(i, A[i-1][j]), max(i, A[i-1][j]))
            if p in edgeTo: edgeTo[p].append(nextp)
            else: edgeTo[p] = [nextp]
            if nextp in edgeFrom: edgeFrom[nextp].append(p)
            else: edgeFrom[nextp] = [p]
            p = nextp

    Ans = -1
    for i in range(1, N + 1):
        if (min(i, A[i-1][0]), max(i, A[i-1][0])) not in edgeFrom:
            b = dfs((min(i, A[i-1][0]), max(i, A[i-1][0])), edgeTo, Length, set())
            if b == -1:
                print(-1)
                break
            else: Ans = max(Ans, b)
    else: print(Ans)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# atcoder problems solving
# League
from collections import deque
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    graph = {(i, j): [] for i in range(1, N+1) for j in range(i+1, N+1)}
    indegree = {(i, j): 0 for i in range(1, N+1) for j in range(i+1, N+1)}

    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N-2):
            x, y = a[j], a[j+1]
            z, w = i+1, i+1
            graph[(min(z, x), max(z, x))].append((min(w, y), max(w, y)))
            indegree[(min(w, y), max(w, y))] += 1

    d = deque()
    e = deque()
    visited = {(i, j): False for i in range(1, N+1) for j in range(i+1, N+1)}

    cnt = 1
    match = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if indegree[(i, j)] == 0:
                d.append((i, j))
                visited[(i, j)] = True
                match += 1

    while d:
        while d:
            x = d.popleft()
            for node in graph[x]:
                indegree[node] -= 1
                if indegree[node] == 0:
                    e.append(node)
                    visited[node] = True
                    match += 1
        if e:
            d = e
            e = deque()
            cnt += 1

    if match == N*(N-1)//2:
        print(cnt)
    else:
        print(-1)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[] for i in range(n)]
for i in range(n):
  a[i]=[int(x)-1 for x in input().split()]
  
cnt=0
allcnt=0
while 1:
  cnt+=1
  tod_cnt=0
  vs=[0]*n
  for i in range(n):
    if vs[i]:
      continue
    if len(a[i]) < 1:
      vs[i]=1
      continue
    x=a[i][0]
    if vs[x]==0 and a[x][0]==i:
      #print(i,a[i],x,a[x])
      vs[i]=1
      vs[x]=1
      a[i].pop(0)
      a[x].pop(0)
      allcnt+=1
  if allcnt == n*(n-1)//2:
    break
  if tod_cnt == allcnt:
    cnt=-1
    break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


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

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = [[] for _ in range(N*(N-1)//2)]
    inn = [[] for _ in range(N*(N-1)//2)]
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            # fで書いていたけど遅いので、移す
            a = i
            b = A[i][j]
            if a > b:
                a, b = b, a
            frm = b-1+(N-2)*a-a*(a-1)//2
            a = i
            b = A[i][j+1]
            if a > b:
                a, b = b, a
            to = b-1+(N-2)*a-a*(a-1)//2
            out[frm].append(to)
            inn[to].append(frm)
    # print(out)

    # 閉路検出
    # 始点からのパスを保持しながらDFSする
    hist = [False]*(N*(N-1)//2)

    def dfs(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in out[v]:
            if hist[u] is False:
                curr, last = dfs(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs(f(0, A[0][0]))
    if longest == INF:
        print(-1)
        return

    def dfs2(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in inn[v]:
            if hist[u] is False:
                curr, last = dfs2(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs2(last)
    if longest == INF:
        print(-1)
        return
    else:
        print(longest)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
from itertools import product
INF = float("inf")


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

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = defaultdict(list)
    inn = defaultdict(list)
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            out[f(i, A[i][j])].append(f(i, A[i][j+1]))
            inn[f(i, A[i][j+1])].append(f(i, A[i][j]))
    # print(out)

    # 閉路検出
    # 始点からのパスを保持しながらDFSする
    hist = [False]*(N*(N-1)//2)

    def dfs(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in out[v]:
            if hist[u] is False:
                curr, last = dfs(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs(f(0, A[0][0]))
    if longest == INF:
        print(-1)
        return

    def dfs2(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in inn[v]:
            if hist[u] is False:
                curr, last = dfs2(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs2(last)
    if last == INF:
        print(-1)
        return
    else:
        print(longest)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc139/tasks/abc139_e
# 詳しくは図の解説を。シミュレーションを高速化するか、トポロジカルソートをうまく使うか
# ここでは練習のためトポロジカルソートをうまく使うことにする

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N = read_a_int()
A = read_matrix(N)
A = [mina(*a) for a in A]  # 0based indexに

# 試合idを決定する
matchID = {}
cnt = 0
for i, j in combinations(range(N), r=2):
    matchID[i, j] = cnt
    matchID[j, i] = cnt  # 一応逆に入力されても大丈夫なように
    cnt += 1

# 入力をmatchID形式に変換
for i, j in product(range(N), range(N - 1)):
    A[i][j] = matchID[i, A[i][j]]

# DAGを作る
graph = defaultdict(lambda: [])
indeg = [0] * cnt
for a in A:
    for i in range(N - 2):
        graph[a[i]].append(a[i + 1])
        indeg[a[i + 1]] += 1

# トポロジカルソートの容量ですべての試合の日数を割り振る
day = [-1] * cnt  # 何日目にその試合が行われたか
is_visited = [False] * cnt
que = deque()  # 各要素は(ノード, 到達可能な最短日数) #流入量0になったノードから加えていく
for i in range(cnt):  # 初期化
    if indeg[i] == 0:
        is_visited[i] = True
        que.append((i, 1))

while que:
    u, d = que.popleft()
    day[u] = d  # 流入量0になったときのdなので
    for to in graph[u]:
        indeg[to] -= 1
        if indeg[to] or is_visited[to]:  # 流入待ちがまだあるor訪問済みならやる必要はない
            continue
        que.append((to, d + 1))
        is_visited[to] = True

print(-1 if -1 in day else max(day))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    battle_list = [-1 for _ in range(n)]
    for i in range(n):
        if len(a_list[i]) > 0:
            j = a_list[i][0]
            battle_list[i] = j
        if (battle_list[i] == j) & (battle_list[j] == i):
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    if battle_today == 0:
        day = -1
        break
print(day)