Problem: 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.

Submission attempts (in order):





import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] 

  



が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append([i,1])

if len(stack) == 0:
  print(-1)
  exit(0)

dist = [-1 for i in range((N * (N - 1)) // 2)]
while stack:
  v, d = stack.pop()
  if dist[v] >= d:
    continue
  dist[v] = d
  for child in G[v]:
    stack.append([child, d + 1])

for d in dist:
  if d == -1:
    print(-1)
    break
else:
  print(max(dist))






import sys
readline = sys.stdin.readline

N = int(readline())

to_id = {}
next_id = 0
def convert_to_id(a,b,next_id):
  if (a,b) not in to_id:
    to_id[(a,b)] = next_id
    to_id[(b,a)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id[(i,a - 1)]
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game

done = set()

が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if game in done: 
      print(-1)
      exit(0)
    done.add(game)
    for child in G[game]: 
      indegree[child] -= 1
      if indegree[child] == 0: が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

if len(done) != ((N * (N - 1)) // 2):
  print(-1)
  exit(0)
print(day)






import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game

done = set()

が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if game in done: 
      print(-1)
      exit(0)
    done.add(game)
    for child in G[game]: 
      indegree[child] -= 1
      if indegree[child] == 0: が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

if len(done) != ((N * (N - 1)) // 2):
  print(-1)
  exit(0)
print(day)






import sys
readline = sys.stdin.readline

N = int(readline())

to_id = [[-1] * N for i in range(N)]
next_id = 0
def convert_to_id(a,b,next_id):
  if to_id[a][b] == -1:
    to_id[a][b] = next_id
    to_id[b][a] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id[i][a - 1]
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game

done = set()

が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if game in done: 
      print(-1)
      exit(0)
    done.add(game)
    for child in G[game]: 
      indegree[child] -= 1
      if indegree[child] == 0: が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

if len(done) != ((N * (N - 1)) // 2):
  print(-1)
  exit(0)
print(day)






import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] 

が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)


if len(stack) == 0:
  print(-1)
  exit(0)
  
from collections import deque
q = deque(stack)
visited = set()
while q:
  v = q.popleft()
  if v in visited:
    continue
  visited.add(v)
  for child in G[v]:
    q.append(child)

if len(visited) != (N * (N - 1)) // 2:
  print(-1)
  exit(0)




stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append([i,1])

dist = [0 for i in range((N * (N - 1)) // 2)]
while stack:
  v, d = stack.pop()
  if dist[v] >= d:
    continue
  dist[v] = d
  for child in G[v]:
    stack.append([child, d + 1])
  
print(max(dist))






import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] 

が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if done[game]: 
      print(-1)
      exit(0)
    done[game] = True
    for child in G[game]: 
      indegree[child] -= 1
      if indegree[child] == 0: が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

if sum(done) != ((N * (N - 1)) // 2):
  print(-1)
  exit(0)
print(day)






import sys
readline = sys.stdin.readline

N = int(readline())

id_dic = {}
next_id = 0
def to_id(a,b):
  if a > b:
    a,b = b,a
  return id_dic[(a,b)]
def convert_to_id(a,b,next_id):
  if a > b:
    a,b = b,a
  if (a,b) not in id_dic:
    id_dic[(a,b)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] 
indegree = [0 for i in range((N * (N - 1)) // 2)] 
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id(i,a - 1)
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] 

が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if done[game]: 
      print(-1)
      exit(0)
    done[game] = False
    for child in G[game]: 
      indegree[child] -= 1
      if indegree[child] == 0: が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

print(day)

import sys
readline = sys.stdin.readline

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

candi = set(range(N))

day = 0
while candi:
  day += 1
  nex = set()
  done = set()
  for player in candi:
    if player in done:
      continue
    
    if len(A[player]) == 0:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if A[rival][-1] == player:
      
      A[player].pop()
      A[rival].pop()
      if A[player]:
        nex.add(player)
      done.add(player)
      if A[rival]:
        nex.add(rival)
      done.add(rival)
  if len(done) == 0:
    
    print(-1)
    exit(0)
  candi = nex
  
print(day)

Verdicts: Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Wrong Answer

Accepted