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:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

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:
    # i と a - 1の試合
    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 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)
# この頂点からスタートしてBFSで、同じ頂点は通らないようにして移動
# 行けない場所があったら閉路あり
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に入った頂点からスタートしてグラフの最長経路を求める
# 閉路なしなので、より長い道があれば更新

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))

Submission status: Time Limit Exceeded

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

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:
    # i と a - 1の試合
    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 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
  
# stackに入った頂点からスタートしてグラフの最長経路を求める
# 閉路なしなので、より長い道があれば更新

# 入次数が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))

Submission status: Time Limit Exceeded

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

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:
    # i と a - 1の試合
    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 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)
# この頂点からスタートしてBFSで、同じ頂点は通らないようにして移動
# 行けない場所があったら閉路あり
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に入った頂点からスタートしてグラフの最長経路を求める
# 閉路なしなので、より長い道があれば更新

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))

Submission status: Time Limit Exceeded

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

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:
    # i と a - 1の試合
    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 # 試合に対する入次数が1
    cur = game

done = set()
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が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)

Submission status: Time Limit Exceeded

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

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:
    # i と a - 1の試合
    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 # 試合に対する入次数が1
    cur = game

done = set()
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が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)

Submission status: Time Limit Exceeded

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

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:
    # i と a - 1の試合
    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 # 試合に対する入次数が1
    cur = game

done = set()
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が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)

Submission status: Time Limit Exceeded

Solution code:
# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

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:
    # i と a - 1の試合
    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 # 試合に対する入次数が1
    cur = game
  
done = [False for i in range((N * (N - 1)) // 2)] # 試合完了
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が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)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()

for i in range(n*(n-1)//2):
    check(i)
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    dfs_path(i)
print(max(max(finish), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    nodes.add(min(i, pre) * n + max(i, pre))
    for j in tmp[1:]:
        l, g = min(i, j - 1), max(i, j - 1)
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        pre = j - 1
nodes = list(nodes)
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()

for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        pre = tmp[j] - 1
nodes = list(adjacent_list.keys())
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()

for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        nodes.add(pre_l * n + pre_g)
        nodes.add(l * n + g)
        pre = tmp[j] - 1
nodes = list(nodes)
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()

for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        nodes.add(pre_l * n + pre_g)
        nodes.add(l * n + g)
        pre = tmp[j] - 1
nodes = list(nodes)
#まず、閉路検
seen = defaultdict(bool)
visited = defaultdict(bool)
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        nodes.add(pre_l * n + pre_g)
        nodes.add(l * n + g)
        pre = tmp[j] - 1
nodes = list(nodes)
#まず、閉路検
seen = [False for i in range((n + 2) * n)]
visited = [False for i in range((n + 2) * n)]
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = [[] for i in range((n + 2) * n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        nodes.add(pre_l * n + pre_g)
        nodes.add(l * n + g)
        pre = tmp[j] - 1
nodes = list(nodes)
#まず、閉路検
seen = [False for i in range((n + 2) * n)]
visited = [False for i in range((n + 2) * n)]
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = [[] for i in range((n + 2) * n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        nodes.add(pre_l * n + pre_g)
        nodes.add(l * n + g)
        pre = tmp[j] - 1
not_candidate = set([])
nodes = list(nodes)
for i in nodes:
    if len(adjacent_list[i]) == 0:
        not_candidate.add(i)
        continue
    for j in adjacent_list[i]:
        not_candidate.add(j)
#まず、閉路検
seen = [False for i in range((n + 2) * n)]
visited = [False for i in range((n + 2) * n)]
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    if i not in not_candidate:
        dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
adjacent_list = [[] for i in range((n + 2) * n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        pre = tmp[j] - 1
not_candidate = set([])
for i in range((n + 2) * n):
    if len(adjacent_list[i]) == 0:
        not_candidate.add(i)
        continue
    for j in adjacent_list[j]:
        not_candidate.add(j)
#まず、閉路検
seen = [False for i in range((n + 2) * n)]
visited = [False for i in range((n + 2) * n)]
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in range((n + 2) * n):
    check(i)
finish = defaultdict(int)
for i in range((n + 2) * n):
    if i not in not_candidate :
        dfs_path(i)
print(max(max(finish.values()), 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
adjacent_list = [[] for i in range((n + 2) * n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        pre = tmp[j] - 1
not_candidate = set()
for i in range((n + 2) * n):
    for j in adjacent_list[j]:
        not_candidate.add(j)
#まず、閉路検
seen = [False for i in range((n + 2) * n)]
visited = [False for i in range((n + 2) * n)]
def check(node):
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()
for i in range((n + 2) * n):
    check(i)
finish = defaultdict(int)
for i in range((n + 2) * n):
    if i not in not_candidate:
        dfs_path(i)
print(max(finish.values()))

Submission status: Time Limit Exceeded

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

ans = 0
judge = True
while judge:
    ans += 1
    skip = set()
    judge = False
    for i in range(N):
        if len(A[i]) == 0: continue
        t = A[i].pop()
        if (i, t) in skip:
            skip.remove((i, t))
            judge = True
        else:
            skip.add((t, i))
    #print(skip)
    for t, i in skip:
        A[i].append(t)

if all([len(i) == 0 for i in A]):
    print(ans-1)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

ans = 0
judge = True
while any([len(i) > 0 for i in A]) and judge:
    ans += 1
    dic = {}
    skip = set()
    judge = False
    for i in range(N):
        if len(A[i]) == 0: continue
        t = A[i].pop()
        if (i, t) in skip:
            skip.remove((i, t))
            judge = True
        else:
            skip.add((t, i))
    #print(skip)
    for t, i in skip:
        A[i].append(t)

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

Submission status: Time Limit Exceeded

Solution code:
def opp(i):  #対戦希望相手
    return a[i][nex[i]]

from sys import stdin
#入力
readline=stdin.readline
n=int(readline())
m=n*(n-1)//2
a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

nex=[0]*n
before=set(list(range(n)))
day=0
for day in range(1,m+1):
    now=set()
    flags=[False]*n
    while len(before)>0:
        p=before.pop()
        q=opp(p)
        if opp(q)==p and flags[p]==False and flags[q]==False:
            flags[p]=True
            flags[q]=True
            nex[p]+=1
            nex[q]+=1
            if nex[p]<n-1:
                now.add(p)
            if nex[q]<n-1:
                now.add(q)
            if q in before:
                before.remove(q)
    before=now
    if len(before)==0:
        break

if min(nex)==n-1:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def opp(i):  #対戦希望相手
    return a[i][nex[i]]

from sys import stdin
#入力
readline=stdin.readline
n=int(readline())
m=n*(n-1)//2
a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

nex=[0]*n
before=set(list(range(n)))
day=0
for day in range(1,m+1):
    now=set()
    flags=[False]*n
    l=len(before)
    for i in range(l):
        if len(before)==0:
            break
        p=before.pop()
        q=opp(p)
        if opp(q)==p and flags[p]==False and flags[q]==False:
            flags[p]=True
            flags[q]=True
            nex[p]+=1
            nex[q]+=1
            if nex[p]<n-1:
                now.add(p)
            if nex[q]<n-1:
                now.add(q)
            if q in before:
                before.remove(q)
    before=now
    if len(before)==0:
        break

if min(nex)==n-1:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def opp(i):  #対戦希望相手
    return a[i][nex[i]]

from sys import stdin
#入力
readline=stdin.readline
n=int(readline())
m=n*(n-1)//2
a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

nex=[0]*n
before=set(list(range(n)))
day=0
while len(before)>0:
    day+=1
    now=set()
    flags=[False]*n
    while len(before)>0:
        p=before.pop()
        q=opp(p)
        if opp(q)==p and flags[p]==False and flags[q]==False:
            flags[p]=True
            flags[q]=True
            nex[p]+=1
            nex[q]+=1
            if nex[p]<n-1:
                now.add(p)
            if nex[q]<n-1:
                now.add(q)
            if q in before:
                before.remove(q)
    before=now

if min(nex)==n-1:
    print(day)
else:
    print(-1)