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():
    N = int(input())
    
    A = [None] * N
    for i in range(N):
        A[i] = list(map(int, input().split()))
        
    
    day = 0
    roop_flag = True
    
    b = [A[i][0] for i in range(N)]

    while roop_flag:
        
        day += 1
        # 基本はNGの状態にしておく
        roop_flag = False
        done = [False] * N
        
        for i in range(N):
            if b[i] is None:
                continue
            
            if not done[i] and not done[b[i] - 1]:
                if b[b[i] - 1] == i + 1:
                    roop_flag = True
                    
                    done[i] = True
                    done[b[i] - 1] = True
                    
                    A[i] = A[i][1:]
                    A[b[i] -1] = A[b[i] - 1][1:]

                    if len(A[b[i] - 1]) > 0:
                        b[b[i] - 1] = A[b[i] - 1][0]
                    else:
                        b[b[i] - 1] = None
                    
                    if len(A[i]) > 0:
                        b[i] = A[i][0]
                    else:
                        b[i] = None
                    

        if b == [None] * N:
            print(day)
            quit()
            
        
    print(-1)
    

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    
    A = [None] * N
    for i in range(N):
        A[i] = list(map(int, input().split()))
        
    
    day = 0
    roop_flag = True

    while roop_flag:
        # 基本はNGの状態にしておく
        roop_flag = False
        
        done = [False] * N
        b = [None] * N
        
        # 次に消化すべき組み合わせをとる
        for i in range(N):
            if len(A[i]) > 0:
                b[i] = A[i][0]
            
        if b == [None]*N:
            print(day)
            quit()
        
        for i in range(N):
            if not done[i]:
                if b[i] is None:
                    continue
                
                if b[b[i] - 1] == i + 1:
                    roop_flag = True

                    done[i] = True
                    done[b[i] -1] = True
                    
                    A[i] = A[i][1:]
                    A[b[i] -1] = A[b[i] -1][1:]
        day += 1
        
    print(-1)
    

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

num_game_left = N * (N - 1) // 2
num_days = 0
left_players = set(range(N))
while 0 < num_game_left:
    game_players = set()
    for i in left_players:
        if i in game_players:
            continue
        j = A[i][-1]
        if A[j][-1] == i:
            game_players.add(i)
            game_players.add(j)
    num_game_left -= len(game_players) // 2

    if not game_players:
        break

    num_days += 1
    for i in game_players:
        A[i].pop()
        if not A[i]:
            left_players.remove(i)

if num_game_left == 0:
    print(num_days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

num_game_left = N * (N - 1) // 2
num_days = 0
left_players = set(range(N))
while 0 < num_game_left:
    game_players = set()
    for i in left_players:
        if i in game_players:
            continue
        j = A[i][0]
        if A[j] and A[j][0] == i:
            game_players.add(i)
            game_players.add(j)
    num_game_left -= len(game_players) // 2

    if not game_players:
        break

    num_days += 1
    for i in game_players:
        A[i].popleft()
        if not A[i]:
            left_players.remove(i)

if num_game_left == 0:
    print(num_days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

num_game_left = N * (N - 1) // 2
num_days = 0
left_players = set(range(N))
while 0 < num_game_left:
    game_players = set()
    for i in left_players:
        if i in game_players:
            continue
        j = A[i][0]
        if A[j] and A[j][0] == i:
            game_players.add(i)
            game_players.add(j)
    num_game_left -= len(game_players) // 2

    if len(game_players) == 0:
        break

    num_days += 1
    for i in game_players:
        A[i].popleft()
        if not A[i]:
            left_players.remove(i)

if num_game_left == 0:
    print(num_days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

num_game_left = N * (N - 1) // 2
num_days = 0
while 0 < num_game_left:
    ids = [None] * N
    for i in range(N):
        if A[i]:
            ids[i] = A[i][0]
        else:
            ids[i] = None

    game_players = set()
    for i in range(N):
        if ids[i] is None:
            continue
        j = ids[i]
        if ids[j] == i:
            game_players.add(i)
            game_players.add(j)
    assert len(game_players) % 2 == 0
    num_game_left -= len(game_players) // 2

    if len(game_players) == 0:
        break

    num_days += 1
    for i in game_players:
        A[i].popleft()

if num_game_left == 0:
    print(num_days)
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)
ans = 0
n = 0
while n < ((N-1)*N)//2:
    f = []
    ans += 1
    t = 0
    for i in range(1,N+1):
        if i in f:
            continue
        if len(A[i]) > 0:
            a = A[i][0]
        else:
            continue
        if (A[a][0] == i):
            if a not in f:
                A[i].pop(0)
                A[a].pop(0)
                f.append(i)
                f.append(a)
                n += 1
                t = 1
    if t == 0:
        print(-1)
        quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [rl()[::-1] for _ in range(N)]
answer = 0
match = 0
while True:
    used = set()
    bool = False
    for i in range(N):
        if len(A[i]) == 0:
            continue
        op = A[i][-1] - 1
        if op in used or i in used:
            continue
        if op > i and A[op][-1]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            bool = True
            A[i].pop()
            A[op].pop()
    
    answer += 1
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [rl()[::-1] for _ in range(N)]
answer = 0
match = 0
while A:
    used = set()
    bool = False
    for i in range(N):
        if len(A[i]) == 0:
            continue
        op = A[i][-1] - 1
        if op in used or i in used:
            continue
        if op > i and A[op][-1]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            bool = True
            A[i].pop()
            A[op].pop()
    
    answer += 1
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N = int(input())

adjacent = defaultdict(list)
indeg = defaultdict(int)
for i in range(N):
    Ai = list(map(int, input().split()))
    c_prev = (0, 0)
    for Aij in Ai:
        Aij -= 1
        c = (i, Aij) if i < Aij else (Aij, i)
        if c_prev != (0, 0):
            adjacent[c_prev].append(c)
            indeg[c] += 1
        c_prev = c

visited = defaultdict(bool)
q = deque()
for i in range(N - 1):
    for j in range(i + 1, N):
        if indeg[(i, j)] == 0:
            q.append((i, j))
            visited[(i, j)] = True

order = []
while len(q) > 0:
    u = q.popleft()
    order.append(u)
    for v in adjacent[u]:
        indeg[v] -= 1
        if indeg[v] == 0 and visited[v] == False:
            visited[v] = True
            q.append(v)

if len(order) == N * (N - 1) // 2:
    people = set()
    ans = 1
    for p in order:
        if p[0] in people or p[1] in people:
            ans += 1
            people = set(p)
        else:
            people.add(p[0])
            people.add(p[1])
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
m = N*(N-1) // 2

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(i+1, N):
    hash_table[i][j] = hash_table[j][i] = count
    count += 1


graph = [[] for i in range(m)]
before_this = [0] * m
for i in range(1, N+1):
  A = deque(list(map(int, input().split())))
  pre_a = A.popleft()
  pre_pair = hash_table[i-1][pre_a-1]
  for a in A:
    pair = hash_table[i-1][a-1]
    graph[pre_pair].append(pair)
    before_this[pair] += 1
    pre_pair = pair


games = deque([])
for i in range(m):
  if not before_this[i]:
    games.append(i)


if not games:
  ans = -1
else:
  ans = 0
  num_finished = 0
  while games:
    ans += 1
    num_games = len(games)
    num_finished += num_games
    for i in range(num_games):
      pair = games.popleft()
      subseq = graph[pair]
      for ss in subseq:
        before_this[ss] -= 1
        if not before_this[ss]:
          games.append(ss)
    
  if num_finished != m:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
m = N*(N-1) // 2

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
    for j in range(i+1, N):
        hash_table[i][j] = hash_table[j][i] = count
        count += 1


graph = [[] for i in range(m)]
is_root = [True] * m
for i in range(1, N+1):
    A = deque(list(map(int, input().split())))
    pre_a = A.popleft()
    pre_pair = hash_table[i-1][pre_a-1]
    for a in A:
        pair = hash_table[i-1][a-1]
        graph[pre_pair].append(pair)
        is_root[pair] = False
        pre_pair = pair


stack = []
is_in_stack = [False] * m
for i in range(m):
    if is_root[i]:
        stack.append(i)
        is_in_stack[i] = True


if not stack:
    ans = -1
else:
  ans = 1
  depth = [1] * m
  while stack:
      pair = stack[-1]
      subseq = graph[pair]
      have_next = False
      for ss in subseq:
          if is_in_stack[ss]:
              ans = -1
              stack = []
              have_next = True
              break

          if have_next or depth[ss] > depth[pair]:
              continue

          have_next = True
          depth[ss] = depth[pair] + 1
          ans = max(ans, depth[ss])
          stack.append(ss)
          is_in_stack[ss] = True

      if not have_next:
          pair = stack.pop()
          is_in_stack[pair] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
m = N*(N-1) // 2

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
    for j in range(i+1, N):
        hash_table[i][j] = hash_table[j][i] = count
        count += 1


graph = [[] for i in range(m)]
is_root = [True] * m
for i in range(1, N+1):
    A = deque(list(map(int, input().split())))
    pre_a = A.popleft()
    pre_pair = hash_table[i-1][pre_a-1]
    for a in A:
        pair = hash_table[i-1][a-1]
        graph[pre_pair].append(pair)
        is_root[pair] = False
        pre_pair = pair


stack = []
for i in range(m):
    if is_root[i]:
        stack.append(i)


if not stack:
    ans = -1
else:
  ans = 1
  depth = [1] * m
  while stack:
      pair = stack[-1]
      subseq = graph[pair]
      have_next = False
      for ss in subseq:
          if ss in stack:
              ans = -1
              stack = []
              have_next = True
              break

          if have_next or depth[ss] > depth[pair]:
              continue

          have_next = True
          depth[ss] = depth[pair] + 1
          ans = max(ans, depth[ss])
          stack.append(ss)

      if not have_next:
          stack.pop()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

N=int(input())
A=[[] for _ in range(N)]

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

NE=[0]*N#i番目の人が，次何番目の試合をするかのリスト
F=[0]*N#i番目の人が，該当する日に試合をしたか記憶しておく

#i+1日目の試合をする人はi日目に試合をした人なので，それを記憶．
q1=queue.Queue()
q2=queue.Queue()

#初日
for i in range(N):
    opp=A[i][0]-1
    if A[opp][0]-1==i:
        NE[i]+=1
        q1.put(i)

ans=1
#d日目
for d in range(N*(N-1)//2):
    F=[0]*N
    while not q2.empty():
        a=q2.get()
        q1.put(a)
    while not q1.empty():
        i=q1.get()
        if NE[i]==N-1:
            continue
        opp=A[i][NE[i]]-1
        if F[i]==1 or F[opp]==1:#その日に試合したことがある人はスルー,oppの重複防止
            continue
        if A[opp][NE[opp]]-1==i:
            NE[i]+=1
            NE[opp]+=1
            F[i]=1
            F[opp]=1
            if NE[i]!=N-1:
                q2.put(i)
            if NE[opp]!=N-1:
                q2.put(opp)
    ans+=1
    if q2.empty() and q2.empty():
        break

for i in range(N):
    if NE[i]!=N-1:
        ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

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

    adj = defaultdict(list)
    in_num = defaultdict(int)
    for i in range(N):
        for j in range(N-2):
            x1 = x2= i+1
            y1 = A[i][j]
            y2 = A[i][j+1]
            if x1 > y1:
                x1, y1 = y1, x1
            if x2 > y2:
                x2, y2 = y2, x2
            adj[(x1, y1)].append((x2, y2))
            in_num[(x2, y2)] += 1
    st = []
    ng = (N * (N - 1)) // 2
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if in_num[(i, j)] == 0:
                st.append((i, j))
                ng -= 1
    ans = 0
    while st:
        ans += 1
        st_new = []
        for par in st:
            for child in adj[par]:
                if in_num[child] == 1:
                    st_new.append(child)
                    ng -= 1
                in_num[child] -= 1
        if st_new:
            st = st_new
        else:
            break

    if ng:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def dfs(path, visited, i, j, memo = dict()):
    if (i, j) not in path: return 0
    if (i, j) in memo: return memo[(i, j)]
    maxlength = 0
    for ni, nj in path[(i, j)]:
        if (ni, nj) in visited: 
            memo[(i, j)] = -1
            return -1
        else:
            nl = dfs(path, visited | {(i, j)}, ni, nj, memo)
            if nl == -1: 
                memo[(i, j)] = -1
                return -1
            else: maxlength = max(maxlength, nl)

    memo[(i, j)] = maxlength + 1
    return maxlength + 1

def solve():
    input = sys.stdin.readline
    N = int(input())
    path = dict()
    path[(-1, -1)] = set()
    for i in range(N):
        A = [int(a) - 1 for a in input().split()]
        path[(-1, -1)] |= {(min(i, A[0]), max(i, A[0]))}
        for j in range(N-2):
            if (min(i, A[j]), max(i, A[j])) in path: path[(min(i, A[j]), max(i, A[j]))] |= {(min(i, A[j+1]), max(i, A[j+1]))}
            else: path[(min(i, A[j]), max(i, A[j]))] = {(min(i, A[j+1]), max(i, A[j+1]))}

    memo = dict()
    print(dfs(path, set(), -1, -1, memo))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def dfs(path, visited, i, j, length):
    if (i, j) not in path: return length
    else:
        maxlength = 0
        maxNode = set()
        for ni, nj in path[(i, j)]:
            if (ni, nj) in visited:
                return -1
            else:
                nl = dfs(path, visited | {(i, j)}, ni, nj, length + 1)
                if nl == -1: return -1
                else: maxlength = max(maxlength, nl)

        return maxlength

def solve():
    input = sys.stdin.readline
    N = int(input())
    path = dict()
    path[(-1, -1)] = set()
    start = set()
    for i in range(N):
        A = [int(a) - 1 for a in input().split()]
        path[(-1, -1)] |= {(min(i, A[0]), max(i, A[0]))}
        for j in range(N-2):
            if (min(i, A[j]), max(i, A[j])) in path:
                path[(min(i, A[j]), max(i, A[j]))] |= {(min(i, A[j+1]), max(i, A[j+1]))}
            else: path[(min(i, A[j]), max(i, A[j]))] = {(min(i, A[j+1]), max(i, A[j+1]))}

    ans = 0
    for i, j in path[(-1, -1)]:
        l = dfs(path, set(), i, j, 1)
        if l == -1:
            print(-1)
            break
        ans = max(ans, l)
    else: print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [deque() for _ in range(N)]
    for i in range(N):
        for j, a in enumerate(list(map(int, input().split()))):
            A[i].append(a-1)
    match = 0
    day = 0

    while match < N * (N - 1) // 2:
        day += 1
        Today = set()
        for i in range(N):
            if i not in Today and A[i]:
                j = A[i].popleft()
                if j not in Today and A[j]:
                    revi = A[j].popleft()
                    if i == revi:
                        match += 1
                        Today |= {i, j}
                    else:
                        A[i].appendleft(j)
                        A[j].appendleft(revi)
                else: A[i].appendleft(j)

        #print("Day:", day)
        #print(Today)
        #print(A)
        
        if not Today:
            print(-1)
            break
    else: print(day)
                
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) - 1 for a in input().split()] for _ in range(N)]
    pointer = dict()
    match = 0
    day = 0
    for i in range(N): pointer[i] = 0

    while match < N * (N - 1) // 2:
        day += 1
        Today = [-1] * N
        for i in range(N):
            if Today[i] == -1 and pointer[i] < N - 1:
                j = A[i][pointer[i]]
                if Today[j] == -1 and A[j][pointer[j]] == i:
                    match += 1
                    Today[i] = j
                    Today[j] = 1
        valid = False
        for i, t in enumerate(Today):
            if t >= 0:
                pointer[i] += 1
                valid = True
        if valid: continue
        print(-1)
        break
    else: print(day)
                
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
 
to = [[] for _ in range(MAXV)]
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)]
 
def toId(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]
visited = [False] * MAXV
calculated = [False] * MAXV
dp = [1] * MAXV
 
def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
 
    for u in to[v]:
        res = dfs(u)
        if res == -1: return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]
 
def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1
    
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i, a[i][j])
        for j in range(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')
            return
        ans = max(ans, res)
    print(ans)
    return
  
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

day=0
zan=[n-1]*n
zann=sum(zan)

while True:
  day+=1
  sumi=set(range(n))
  kouho=list(sumi)
  sumi=set()
  
  for i in kouho:
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print(-1)
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

day=0
zan=[n-1]*n
zann=sum(zan)

while day<10**6:
  day+=1
  kouho=list(range(n))
  sumi=set()
  
  for i in range(n):
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print(-1)
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)
    
print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

day=0
zan=[n-1]*n
zann=sum(zan)

while True:
  day+=1
  kouho=list(range(n))
  sumi=set()
  
  for i in range(n):
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print(-1)
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)

Submission status: Time Limit Exceeded

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

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

	def label(a, b):
		if a > b:
			a, b = b, a
		return (a - 1) * (2 * n - a) // 2 + b - a - 1

	m = n * (n - 1) // 2
	g = [[] for _ in range(m)]
	deg = [0] * (m)
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y)
			g[label(i, x)].append(t)
			deg[t] += 1

	depth = [None] * m
	q = deque()
	for i, d in enumerate(deg):
		if not d:
			depth[i] = 1
			q.append(i)
	while q:
		cur = q.popleft()
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				q.append(nxt)
	print(max(depth) if all(depth) else -1)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def f(g: list, deg: list):
	l = len(g)
	depth = [0] * l
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				ret.append(nxt)
				q.append(nxt)
	if l > len(ret):
		return False
	return max(depth)

def label(a, b, n):
	if a > b:
		a, b = b, a
	return (a - 1) * (2 * n - a) // 2 + b - a - 1


def main():
	n = int(input())
	g = [[] for _ in range(n * (n - 1) // 2)]
	deg = [0] * (n * (n - 1) // 2)
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y, n)
			g[label(i, x, n)].append(t)
			deg[t] += 1
	depth = f(g, deg)
	if not depth:
		print(-1)
		exit()
	print(depth + 1)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n=int(input())
a=[]
for i in range(n):
    a.append(tuple(map(int,input().split())))
#print(a)

root=[[] for i in range(n*(n-1)//2)]
buf=0
for i in range(n):
    buf=0
    for j in range(n-1):
        if j==0:
            x=min(i,a[i][j]-1)
            y=max(i,a[i][j]-1)
            buf=x*(2*n-2-x+1)//2+(y-x)-1
            #print(x,y,buf)
            continue
        x=min(i,a[i][j]-1)
        y=max(i,a[i][j]-1)
        node=x*(2*n-2-x+1)//2+(y-x)-1
        #print(x,y,node)
        root[buf].append(node)
        buf=node
flag=[True]

#閉路☑
def dfs(node,par): 
    dp[node]=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]==0:
            flag[0]=False
            return
        if dp[item]==-1: 
            dfs(item,node)
    dp[node]=1#finish
dp=[-1]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dfs(i,i)
        if flag[0]==False:
            break
if flag[0]==False:
    print(-1)
    sys.exit()
dp=[-1]*(n*(n-1)//2)
def dfs1(node,par): 
    buf=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]!=-1:
            buf=max(buf,dp[item])
            continue
        if dp[item]==-1: 
            buf=max([buf,dfs1(item,node)])
    dp[node]=buf+1#finish
    return buf+1

for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dp[i]=dfs1(i,i)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

id=[[0 for j in range(N)] for i in range(N)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    id[i][j]=v
    v+=1

def toId(i,j):
  if i>j:
    i,j=j,i
  return id[i][j]

to=[[] for i in range(v)]
inner=[0 for i in range(v)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j]].append(a[i][j+1])
    inner[a[i][j+1]]+=1

stack=[]
isstarted=[False for i in range(v)]
dist=[0 for i in range(v)]
for i in range(v):
  if inner[i]==0:
    stack.append([i,1])

while stack:
  node=stack.pop()
  e=node[0]
  d=node[1]
  if d>dist[e]:
    dist[e]=d
  inner[e]-=1
  if inner[e]<=0 and not isstarted[e]:
    isstarted[e]=True
    children=to[e]
    for child in children:
      stack.append([child,dist[e]+1])
for i in range(len(isstarted)):
  if not isstarted[i]:
    print(-1)
    break
else:
  ans=0
  for i in range(len(dist)):
    if dist[i]>ans:
      ans=dist[i]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
MAXN=1005
MAXV=N*(N-1)//2

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

id=[[0 for j in range(MAXN)] for i in range(MAXN)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    id[i][j]=v
    v+=1

def toId(i,j):
  if i>j:
    i,j=j,i
  return id[i][j]

to=[[] for i in range(MAXV)]
inner=[0 for i in range(MAXV)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j]].append(a[i][j+1])
    inner[a[i][j+1]]+=1

ans=0
stack=[]
isstarted=[False for i in range(v)]
dist=[0 for i in range(v)]
for i in range(v):
  if inner[i]==0:
    stack.append([i,1])

while stack:
  node=stack.pop()
  e=node[0]
  d=node[1]
  if d>dist[e]:
    dist[e]=d
  else:
    d=dist[e]
  if dist[e]>ans:
    ans=dist[e]
  inner[e]-=1
  if inner[e]<=0 and not isstarted[e]:
    isstarted[e]=True
    children=to[e]
    for child in children:
      stack.append([child,d+1])
for i in range(len(isstarted)):
  if not isstarted[i]:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N=int(input())
MAXN=1005
MAXV=N*(N-1)//2

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

id=[[0 for j in range(MAXN)] for i in range(MAXN)]
v=0
for i in range(N-1):
  for j in range(i+1,N):
    id[i][j]=v
    v+=1

def toId(i,j):
  if i>j:
    i,j=j,i
  return id[i][j]

to=[[] for i in range(MAXV)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for i in range(MAXV)]
calculated=[False for i in range(MAXV)]
dp=[0 for i in range(MAXV)]

def dfs(v):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(v):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)