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:


from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j != 0:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
            b = (l,h)



    match_today = deque()
    checked = defaultdict(bool)
    for i in range(N):
        l,h = min(i+1, A[i][0]), max(i+1, A[i][0])
        #print(l,h, before[(l,h)])
        if before[(l,h)] == 0 and not checked[(l,h)]:
            match_today.append((l,h))
            checked[(l,h)] = True

    """
    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
    """
                

    
    ans = 0
    cnt_match = 0 
    f = True
    while f:
        f = False
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
                    f = True
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
                b = (l,h)



    match_today = deque()
    checked = defaultdict(bool)
    for i in range(N):
        l,h = min(i+1, A[i][0]), max(i+1, A[i][0])
        #print(l,h, before[(l,h)])
        if before[(l,h)] == 0 and not checked[(l,h)]:
            match_today.append((l,h))
            checked[(l,h)] = True

    """
    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
    """
                

    
    ans = 0
    cnt_match = 0 
    while match_today:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
                b = (l,h)



    match_today = deque()

    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
                

    
    ans = 0
    cnt_match = 0 
    while match_today:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    nxt = defaultdict(set)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                nxt[b].add((l,h))
                b = (l,h)



    match_today = deque()

    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
                

    
    ans = 0
    cnt_match = 0 
    while match_today:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    nxt = defaultdict(set)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                nxt[b].add((l,h))
                b = (l,h)



    match_today = deque()

    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
                

    
    ans = 0
    cnt_match = 0 
    while len(match_today) > 0:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    nxt = defaultdict(set)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                nxt[b].add((l,h))
                b = (l,h)



    match_today = deque()

    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
                

    match_tomorrow = deque()
    ans = 0
    cnt_match = 0 
    while len(match_today) > 0:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_tomorrow.append((nl, nh))
        
        match_today = match_tomorrow
        match_tomorrow = deque()


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict
from collections import deque

N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

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

for i in range(N):

    for j,a in enumerate(A[i]):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = deque()

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = deque()
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    #print( match_today)
    ans += 1
    
    for _ in range(len(match_today)):
        l,h = match_today.popleft()
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = deque()


if cnt_match == N*(N-1) // 2:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict
from collections import deque

N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

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

    for j,a in enumerate(A):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = deque()

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = deque()
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    #print( match_today)
    ans += 1
    
    for _ in range(len(match_today)):
        l,h = match_today.popleft()
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = deque()


if cnt_match == N*(N-1) // 2:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict


N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

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

    for j,a in enumerate(A):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = []
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    #print( match_today)
    ans += 1
    cnt_today = 0
    
    for l,h in match_today:
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = []


if cnt_match == N*(N-1) // 2:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict

N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

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

    for j,a in enumerate(A):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = []
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    #print( match_today)
    ans += 1
    cnt_today = 0
    
    for l,h in match_today:
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = []


if cnt_match == N*(N-1) // 2:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    for _ in range(n):
        a.append(deque(list(map(int, input().split()))))
    
    siai = n*(n-1)
    d = [0]*n

    while siai:
        f = 0
        for i in range(n):
            if a[i] and a[a[i][0]-1][0] == i+1:
                f = 1
                day = max(d[i], d[a[i][0]-1])
                d[i] = day + 1
                d[a[i][0]-1] = day + 1
                siai -= 2
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if not f:
            print(-1)
            break
    else:
        print(max(d))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    b = [0]*n
    cnt = 0
    while True:
        f = 0
        f2 = 0
        sumi = [0]*n
        for i in range(n):
            if sumi[i] == 1 or b[i] == n-1:
                f2 += 1
                continue
            aite = a[i][b[i]] - 1
            if a[aite][b[aite]]-1 == i and sumi[aite]==0:
                f = 1
                b[i] += 1
                b[aite] += 1
                sumi[i] = 1
                sumi[aite] = 1
        if f2==n:
            break
        elif f:
            cnt += 1
        else:
            print(-1)
            exit()
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
cleared_num=0
new_search_index=set(range(1,N+1))
for answer in range(1,N**3):
  matched_flag=[False]*(N+1)
  unchanged=True

  search_index=new_search_index;
  new_search_index=set()
  for i in search_index:
    if matched_flag[i]:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      if len(amat[i])==0:
        cleared_num+=1
      else:
        new_search_index.add(i)  
      if len(amat[ai_next])==0:
        cleared_num+=1
      else:
        new_search_index.add(ai_next)
      unchanged=False
      
  if unchanged:
    print(-1)
    sys.exit()
  elif cleared_num==N:
    print(answer)
    sys.exit()

Submission status: Time Limit Exceeded

Solution code:
#閉路判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in edge[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in edge[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
if find_loop(n*n,edge,0)==False:print(-1);exit()
t=find_loop(n*n,edge,1)
ans=[1]*n*n
for i in t:
  for j in edge[i]:ans[j]=max(ans[j],ans[i]+1)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for _ in range(n)] 
tcnt,ans=0,0
while tcnt<n*(n-1)//2:
    cnt=0
    chk=[]
    for i in range(n-1):
        if i in chk:
            continue
        else:
            if a[i]:
                b=a[i][0]-1
                if b in chk:
                    continue
                else:
                    if b>i and a[b][0]-1==i:
                        chk.append(a[i].popleft()-1)
                        a[b].popleft()
                        cnt+=1
    tcnt+=cnt
    ans+=1
    if cnt==0:
        ans=-1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split()))[::-1] for _ in range(n)]
tcnt,ans=0,0
while tcnt<n*(n-1)//2:
  cnt=0
  chk=[]
  for i in range(n-1):
    if i in chk:
      continue
    else:
      if a[i]:
        b=a[i][-1]-1
        if b in chk:
          continue
        else:
          if b>i and a[b][-1]-1==i:
            chk.append(a[i].pop()-1)
            a[b].pop()
            cnt+=1
  tcnt+=cnt
  ans+=1
  if cnt==0:
    ans=-1
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split()))[::-1] for _ in range(n)]
tcnt,ans=0,0
while tcnt<n*(n-1)//2:
  cnt=0
  chk=[]
  for i in range(n-1):
    if i in chk:
      continue
    else:
      if a[i]:
        b=a[i][-1]-1
        if b in chk:
          continue
        else:
          if b>i and a[b][-1]-1==i:
            chk.append(a[i].pop()-1)
            chk.append(a[b].pop()-1)
            cnt+=1
  tcnt+=cnt
  ans+=1
  if cnt==0:
    ans=-1
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split()))[::-1] for _ in range(n)]
cnt,tcnt=0,0
ans=0
chk=[]
while tcnt<n*(n-1)//2:
  cnt=0
  chk=[]
  for i in range(n-1):
    if i in chk:
      continue
    else:
      if a[i]:
        b=a[i][-1]-1
        if b in chk:
          continue
        else:
          if b>i and a[b][-1]-1==i:
            chk.append(a[i].pop()-1)
            chk.append(a[b].pop()-1)
            cnt+=1
  tcnt+=cnt
  ans+=1
  if cnt==0:
    ans=-1
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

temp_list = []
for _ in range(n):
    a_list = [int(x) - 1 for x in input().split()][::-1]
    temp_list.append(a_list)

end_flag = [False] * n
day = 0
while False in end_flag:
    break_flag = True
    day += 1

    skip_flag = end_flag[:]
    
    for i in range(n):
        if skip_flag[i]:
            continue
        skip_flag[i] = True

        j = temp_list[i][-1]
        if skip_flag[j]:
            continue
        i_ = temp_list[j][-1]

        if i == i_:
            temp_list[i].pop()
            if len(temp_list[i]) == 0:
                end_flag[i] = True

            skip_flag[j] = True
            temp_list[j].pop()
            if len(temp_list[j]) == 0:
                end_flag[j] = True

            break_flag = False
        
    if break_flag:
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    for _ in range(N):
        npos, *l = list(map(int,input().split()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [-1] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now < 0:
                continue
            if now in already:
                continue
            if i == now:
            	continue
            if i in already:
                continue

            if i == next_pos[now] - 1:
                if end:
                    end = False
                if A[i]:
                    next_pos[i] = A[i].pop(0)
                else:
                    next_pos[i] = -1
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = -1
                al_add(i)
                al_add(now)
        ans += 1
        if end:
            ans = -1
            break
        if next_pos == check:
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
sys.setrecursionlimit(10**6)

def main():
    maxn = 1005
    maxv =  maxn * (maxn-1) // 2
    to = [[] for _ in range(maxv)] # 頂点間の辺の情報
    id = [[[] for _ in range(maxn)] for _ in range(maxn)] # 試合のid=DAGの頂点番号
    
    def toId(i,j): # 選手idから試合idを返す関数
        if i > j: # i,jが逆になっても試合idは同じ
            i,j = j,i
        return id[i][j]

    visited = [False]*maxv
    calculated = [False]*maxv
    dp = [1]*maxv # Vからスタートしたときの最長経路。頂点の個数ベースで経路の長さを数えるので、初期値は1

    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1 # 計算が終わっていない頂点を2度訪れるのはループがあるということ
            return dp[v]
        visited[v] = True
        for u in to[v]: # 全ての辺をなめる
            res = dfs(u)
            if res == -1: return -1 # ループがあれば-1を返す
            dp[v] = max(dp[v], res+1)
        calculated[v] = True
        return dp[v]

    n = int(input())
    a = [nl() for _ in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1 # 選手idを0始まりに変換
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1 # 0から順に各試合にidを割り振る
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i,a[i][j]) # 選手idを試合id(頂点番号)に置き換える
        for j in range(n-2): # 頂点間の依存関係はn-2個
            to[a[i][j+1]].append(a[i][j])
    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1') # ループがあれば-1を返す（問題文の指示）
            return
        ans = max(ans, res)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    v = n*(n-1)//2
    A = [list(map(int,input().split())) for _ in range(n)]

    # 頂点と i vs j との対応は (i < j)
    # (n-j+i)(n-j+i-1)//2 + i

    path = [set() for _ in range(v)]

    def vertex(vs1,vs2):
        m,M = sorted([vs1,vs2])
        return (n-M+m)*(n-M+m-1)//2 + m

    parent = set(range(v))

    for i in range(n):
        for j in range(1,n-1):
            vs = vertex(i,A[i][j] - 1)
            vsp= vertex(i,A[i][j-1] - 1)
            path[vs].add(vsp)
            if vsp in parent:
                parent.remove(vsp)

    def dfs(start):
        if memo[start] != -1:
            return memo[start]
        que = deque([(start,1)])
        ret = 0
        while que:
            p,d = que.pop()
            for nxt in path[p]:
                ret = max(ret,d+1)
                que.append((nxt,d+1))
        memo[start] = ret
        return ret

    ans = -1
    memo = [-1]*v
    for i in parent:
        ans  = max(ans, dfs(i))
    print(ans)

main()

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    v = n*(n-1)//2
    A = [list(map(int,input().split())) for _ in range(n)]

    # 頂点と i vs j との対応は (i < j)
    # (n-j+i)(n-j+i-1)//2 + i

    path = [set() for _ in range(v)]

    def vertex(vs1,vs2):
        m,M = sorted([vs1,vs2])
        return (n-M+m)*(n-M+m-1)//2 + m

    parent = set(range(v))

    for i in range(n):
        for j in range(1,n-1):
            vs = vertex(i,A[i][j] - 1)
            vsp= vertex(i,A[i][j-1] - 1)
            path[vs].add(vsp)
            if vsp in parent:
                parent.remove(vsp)

    def dfs(start):
        reached = [False]*v
        que = deque([(start,1)])
        ret = 0
        while que:
            p,d = que.pop()
            for nxt in path[p]:
                ret = max(ret,d+1)
                que.append((nxt,d+1))
        return ret

    ans = -1
    for i in parent:
        ans  = max(ans, dfs(i))
    print(ans)

main()

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    v = n*(n-1)//2
    A = [list(map(int,input().split())) for _ in range(n)]

    # 頂点と i vs j との対応は (i < j)
    # (n-j+i)(n-j+i-1)//2 + i

    path = [set() for _ in range(v)]

    def vertex(vs1,vs2):
        m,M = sorted([vs1,vs2])
        return (n-M+m)*(n-M+m-1)//2 + m

    parent = set(range(v))

    for i in range(n):
        for j in range(1,n-1):
            vs = vertex(i,A[i][j] - 1)
            vsp= vertex(i,A[i][j-1] - 1)
            path[vs].add(vsp)
            if vsp in parent:
                parent.remove(vsp)

    def dfs(start):
        reached = [False]*v
        que = deque([(start,1)])
        ret = 0
        while que:
            p,d = que.pop()
            for nxt in path[p]:
                ret = max(ret,d+1)
                que.append((nxt,d+1))
        return ret

    ans = -1
    for i in parent:
        ans  = max(ans, dfs(i))
    print(ans)

main()