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:
import sys
input = sys.stdin.readline

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    prev = now

d = {k:1 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
q = [i for i in nodes if not in_cnt[i]]
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    prev = now

d = {k:1 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    prev = now

d = {k:1 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
ret = []
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  ret.append(x)
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    prev = now

d = {k:1 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
ret = []
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  ret.append(x)
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    prev = now

d = {k:1 for k in nodes}
f = {k:0 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
ret = []
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  ret.append(x)
  f[x] = 1
  for y in graph[x]:
    if f[y]:
      print(-1)
      exit()
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

d = {k:1 for k in nodes}
f = {k:0 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
ret = []
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  ret.append(x)
  f[x] = 1
  for y in graph[x]:
    if f[y]:
      print(-1)
      exit()
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def topological_sort(graph):
  count = 0
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  newq = deque([])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        newq.append(y)
    if not q:
      q = newq
      newq = deque([])
      count += 1
  if [i for i in nodes if in_cnt[i]]:
    return None,count
  return ret,count

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans,count = topological_sort(graph)
if not ans:
  print(-1)
else:
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def topological_sort(graph):
  d = {i:1 for i in nodes}
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None,d
  return ret,d

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans,d = topological_sort(graph)
if not ans:
  print(-1)
else:
  print(max(d[i] for i in nodes))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def topological_sort(graph):
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None
  return ret

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans = topological_sort(graph)
if not ans:
  print(-1)
else:
  d = {i:1 for i in nodes}
  for x in ans:
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
  print(max(d[i] for i in nodes))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def topological_sort(graph):
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None
  return ret

N = I()
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = IL()
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans = topological_sort(graph)
if not ans:
  print(-1)
else:
  d = {i:1 for i in nodes}
  for x in ans:
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
  print(max(d[i] for i in nodes))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def topological_sort(graph):
  keys = [k for k in graph]
  in_cnt = {k:0 for k in graph}
  for x in keys:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in keys if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in keys if in_cnt[i]]:
    return None
  return ret

N = I()
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = IL()
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans = topological_sort(graph)
if not ans:
  print(-1)
else:
  d = {i:1 for i in nodes}
  for x in ans:
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
  print(max(d[i] for i in nodes))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	match = defaultdict(int)
	cnt = 0
	for i, j in combinations(range(N), 2):
		match[(i, j)] = cnt
		match[(j, i)] = cnt
		cnt += 1

	V = N*(N-1)//2
	graph = [[] for _ in range(V)]
	dag = [0]*V

	for i in range(N):
		for j in range(N-2):
			graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
			dag[match[(i, A[i][j+1]-1)]] += 1

	q = deque([i for i in range(V) if dag[i] == 0])
	day = [1]*V
	while q:
		p = q.popleft()
		for v in graph[p]:
			dag[v] -= 1
			if dag[v] == 0:
				day[v] = day[p]+1
				q.append(v)

	if any(dag):
		print(-1)
	else:
		print(max(day))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [LIST() for _ in range(N)]

match_id = [[0]*N for _ in range(N)]

def toid(i, j):
	i, j = sorted([i, j])
	return match_id[i][j]

cnt = 0
for i in range(N):
	for j in range(N):
		if i < j:
			match_id[i][j] = cnt
			cnt += 1

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

gout = [[] for _ in range(V)]
deg = [0]*V
for i in range(N):
	for j in range(N-2):
		gout[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))
		deg[toid(i, A[i][j+1]-1)] += 1

topo = [v for v in range(V) if deg[v] == 0 ]
day = [0]*V
deq = deque(topo)
ans = 0
while deq:
	v = deq.popleft()
	for t in gout[v]:
		deg[t] -= 1
		if deg[t] == 0:
			deq.append(t)
			day[t] = day[v] + 1
			ans = day[t]
if any(deg):
	print(-1)
	exit()
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
finish=[0]*N
day=0
tired=[False]*N
while 1:
  day+=1
  battle=False
  for i in range(N):
    tired[i]=False
    if finish[i]==N-1:
      continue
    enemy=A[i][finish[i]]-1
    if i==A[enemy][finish[enemy]]-1 and i>enemy and not tired[enemy]:
      finish[enemy]+=1
      finish[i]+=1
      tired[enemy]=True
      tired[i]=True
      battle=True
      #print("day:{0},{1}vs{2}".format(day,i+1,enemy+1))
  if battle==False:
    day-=1
    break
if min(finish)<N-1:
  print(-1)
else:
  print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]

def c(x,y):
    if y < x:
        x,y = y,x
    return x*n+y

e = [[] for i in range(n**2)]
count = [0]*(n**2)
for i in range(n):
    for j in range(n-2):
        y = c(i,a[i][j]-1)
        z = c(i,a[i][j+1]-1)
        count[z] += 1
        e[y].append(z)

q = []

for i in range(n-1):
    for j in range(i+1,n):
        x = c(i,j)
        if count[x] == 0:
            q.append(x)
ans = 0

while q:
    
    ans += 1
    old = q
    q = []
    for nowq in old:
        for nex in e[nowq]:
            count[nex] -= 1
            
            if count[nex] == 0:
                q.append(nex)
if sum(count) > 0:
    print(-1)
else:    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            if used[u] <= used[v]:
                q.append(u)
                used[u] = max(used[u], used[v] + 1)
print(max(used))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
# print(edges)
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            if used[u] <= used[v]:
                q.append(u)
                used[u] = max(used[u], used[v] + 1)

print(max(used))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
# print(edges)
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            used[u] = max(used[u], used[v] + 1)
            q.append(u)
print(max(used))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    mi.discard(t)
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  #print(g)
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    #print(dp)
  print(ans+1)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m

  for i in range(m):
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
  print(ans+1)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    return dp[t]
  ans=0
  for i in range(m):
    v=[0]*m
    c=[0]*m
    dp=[0]*m
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
  print(ans+1)

if __name__=='__main__':
  main()