Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

n = int(input())
orders = [[x - 1 for x in list(map(int, input().split()))] for _ in range(n)]

d = defaultdict(list)
e = defaultdict(list)

for i in range(n):
	for j in range(n - 2):
		a1, a2 = min(i, orders[i][j]), max(i, orders[i][j])
		b1, b2 = min(i, orders[i][j + 1]), max(i, orders[i][j + 1])
		d[(a1, a2)].append((b1, b2))
		e[(b1, b2)].append((a1, a2))

visited = [[0 for _ in range(n)] for _ in range(n)]

tpsort = []
def visit(cur):
	a, b = cur
	if visited[a][b] == -1:
		print(-1)
		sys.exit()
	elif visited[a][b] == 0:
		visited[a][b] = -1
		for nxt in e[cur]:
			visit(nxt)
		visited[a][b] = 1
		tpsort.append(cur)

for i in range(n):
	for j in range(i + 1, n):
		if visited[i][j] == 0:
			#print((i, j))
			visit((i, j))
#print(tpsort)

def dfs(a, cnt):
	if len(d[a]) == 0:
		return cnt
	else:
		return max([dfs(x, cnt + 1) for x in d[a]])

i = 0
max_ans = 0
while True:
	if len(e[tpsort[i]]) > 0:
		break
	max_ans = max(max_ans, dfs(tpsort[i], 1))
	i += 1

print(max_ans)

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    la = len(a[m])
    nokori_games += la
    if m in done:
      pass
    elif la:
      teki = a[m][0]
      jibun = m + 1
      if a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
      elif not len(a[teki - 1]):
        print(-1)
        sys.exit()
  if nokori_games:
    if not len(done):
      print(-1)
      sys.exit()
  else:
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    la = len(a[m])
    nokori_games += la
    if m in done:
      pass
    elif la:
      teki = a[m][0]
      jibun = m + 1
      if a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
      elif not len(a[teki - 1]):
        print(-1)
        sys.exit()
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    la = len(a[m])
    nokori_games += la
    if m in done:
      pass
    elif la:
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append([x,tmp])
        return

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = get_unique_list(q)
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep="\n")
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    
    #この試合はこの試合のあとでないといけない、という条件がいくつもあるので
    #クリティカルパスを求めるイメージ(トポロジカルソート)
    #もしDAGでなければ無理なので-1
    N = I()
    A = LLIN_(N)
    #M = 0 #試合数
    edge = defaultdict(list)
    matches = set()
    for i,a in enumerate(A):
        for j,rival in enumerate(a):
            p1,p2 = sorted([i,rival])
            match = (p1,p2)
            matches.add(match)
            if j != N-2:
                p1,p2 = sorted([i,a[j+1]])
                next_match = (p1,p2)
                edge[match].append(next_match)

    dp = defaultdict(int)
    visited = set()
    def dfs(match):
        if match in visited:
            if match in dp:
                return dp[match]
            else:
                return -1 #閉路検出
        
        for next_match in edge[match]:
            dp[match] = max(dp[match], dfs(next_match)+1)

        #print(match,dp[match])
        return dp[match]

    ans = 0
    for match in matches:
        #print(match)
        res = dfs(match) + 1
        if res == -1:
            print(-1)
            exit()
        ans = max(ans,res)
    print(ans)




    """#O(試合数)
    N = I()
    A = []
    #消化した試合は削除していく
    for _ in range(N):
        *a, = reversed(LI_())
        A.append(a)
    #pprint("A",A)
    
    match = set()
    for i,a in enumerate(A):
        rival = a[-1]
        rival_of_rival = A[rival][-1]
        if rival_of_rival == i:
            match.add(i)
            match.add(rival)

    
    day = 0
    while match:
        day += 1
        last_match = deepcopy(match)
        match = set()

        for i in last_match:
            A[i].pop()
        
        for i in last_match:
            if A[i]:
                rival = A[i][-1]
                rival_of_rival = A[rival][-1]
                if rival_of_rival == i:
                    match.add(i)
                    match.add(rival)
    for a in A:
        if a:
            print(-1)
            exit()

    print(day)"""

    """ O(N^3)
    N = I()
    A = LLIN_(N)
    indexes = [0] * N
    cnt = 0
    match = set()
    for i in range(N*N):
        update = False
        today_players = set()
        for k in range(N):
            index = indexes[k]
            if index >= N-1: #全試合done
                continue
            rival = A[k][index]
            if (k,rival) in match: #前回の希望相手との試合がまだ
                continue
            if (rival,k) in match :
                if not {k,rival} & today_players:
                    cnt += 1
                    update = True
                    match.remove((rival,k))
                    today_players.add(k)
                    today_players.add(rival)
                    indexes[k] += 1
                    indexes[rival] += 1
            else:
                match.add((k,rival))


            
        if not update:
            if cnt != (N*(N-1))//2:
                print(-1)
                exit()
            else:
                print(i)
                exit()"""

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

n = int(input())

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

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

def solve_e(n, a_list):
    days = 0
    ind_list = [0] * n
    match_count = 0
    queue = list(range(n))
    stack = dict()
    while len(queue) > 0:
        days += 1
        new_queue = []
        for p in queue:
            if ind_list[p] < n - 1:
                q = a_list[p][ind_list[p]] - 1
                k = str(min(p, q)) + "_" + str(max(p, q))
                if k in stack.keys():
                    ind_list[p] += 1
                    ind_list[q] += 1
                    # print(days, p, q)
                    new_queue.append(p)
                    new_queue.append(q)
                    match_count += 1
                else:
                    stack[k] = 1
        queue = new_queue
    if match_count == n * (n - 1) // 2:
        return days - 1
    else:
        return -1


def test():
    N = 1000
    A_list = []
    for i in range(N):
        A_list.append(list(range(1, i + 1)) + list(range(i + 2, N + 1)))
    print(solve_e(N, A_list))


def main():
    N = int(input())
    A_list = []
    for _ in range(N):
        A_list.append(list(map(int, input().split())))
    print(solve_e(N, A_list))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def solve_e(n, a_list):
    days = 0
    ind_list = [0] * n
    match_count = 0
    queue = list(range(n))
    stack = dict()
    while len(queue) > 0:
        days += 1
        new_queue = []
        for p in queue:
            if ind_list[p] < n - 1:
                q = a_list[p][ind_list[p]] - 1
                k = str(min(p, q)) + "_" + str(max(p, q))
                if k in stack.keys():
                    ind_list[p] += 1
                    ind_list[q] += 1
                    # print(days, p, q)
                    new_queue.append(p)
                    new_queue.append(q)
                    match_count += 1
                else:
                    stack[k] = 1
        queue = new_queue
    if match_count == n * (n - 1) // 2:
        return days - 1
    else:
        return -1


def test():
    N = 1000
    A_list = []
    for i in range(N):
        A_list.append(list(range(1, i + 1)) + list(range(i + 2, N + 1)))
    print(solve_e(N, A_list))


def main():
    N = int(input())
    A_list = []
    for _ in range(N):
        A_list.append(list(map(int, input().split())))
    print(solve_e(N, A_list))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import copy
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

day=0

match=[0]*n
jyunban=deque([i for i in range(n)])
jyunban_n=deque()
while True:
  jyunban_n.clear()
  day+=1
  check=[True]*n
  while  len(jyunban)!=0:
    i=jyunban.pop()
    if match[i]==n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
        jyunban_n.append(i)
        jyunban_n.append(vs)
      
    if jyunban==[]:
      if not False in check:
        print(day,-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
  jyunban=copy.copy(jyunban_n)
#  print (jyunban)
        
print(day)

Submission status: Time Limit Exceeded

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

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
ans = 0

while any(len(a[i]) != 0 for i in range(n)):
    ans += 1
    li = [True]*n
    for i in range(n):
        if li[i] and len(a[i]) != 0:
            if li[a[i][0]-1] and a[a[i][0]-1][0]-1 == i:
                li[i] = False
                li[a[i][0]-1] = False
                a[a[i][0]-1].pop(0)
                a[i].pop(0)
    if all(li[i] for i in range(n)):
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep="\n")
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():

    #O(試合数)
    N = I()
    A = []
    #消化した試合は削除していく
    for _ in range(N):
        *a, = reversed(LI_())
        A.append(a)
    #pprint("A",A)
    
    match = set()
    for i,a in enumerate(A):
        rival = a[-1]
        rival_of_rival = A[rival][-1]
        if rival_of_rival == i:
            match.add(i)
            match.add(rival)

    
    day = 0
    while match:
        day += 1
        last_match = deepcopy(match)
        match = set()

        for i in last_match:
            A[i].pop()
        
        for i in last_match:
            if A[i]:
                rival = A[i][-1]
                rival_of_rival = A[rival][-1]
                if rival_of_rival == i:
                    match.add(i)
                    match.add(rival)
    for a in A:
        if a:
            print(-1)
            exit()

    print(day)

    """ O(N^3)
    N = I()
    A = LLIN_(N)
    indexes = [0] * N
    cnt = 0
    match = set()
    for i in range(N*N):
        update = False
        today_players = set()
        for k in range(N):
            index = indexes[k]
            if index >= N-1: #全試合done
                continue
            rival = A[k][index]
            if (k,rival) in match: #前回の希望相手との試合がまだ
                continue
            if (rival,k) in match :
                if not {k,rival} & today_players:
                    cnt += 1
                    update = True
                    match.remove((rival,k))
                    today_players.add(k)
                    today_players.add(rival)
                    indexes[k] += 1
                    indexes[rival] += 1
            else:
                match.add((k,rival))


            
        if not update:
            if cnt != (N*(N-1))//2:
                print(-1)
                exit()
            else:
                print(i)
                exit()"""

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def ts(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    Q = []
    for i in range(n)[::-1]:
        Q.append(-1)
        Q.append(i)
        Q.append(3)
        Q.append(i)
        Q.append(2)
        Q.append(i)
        Q.append(1)
    while Q:
        tp = Q.pop()
        if tp == 2:
            j = Q.pop()
            if done[j]: continue
            done[j] = 1
            L.append(j)
            checking[j] = 0
            continue
        elif tp == 3:
            j = Q.pop()
            k = Q.pop()
            D[j] = max(D[j], (D[k] + 1 if k >= 0 else 0))
        elif tp == 1:
            j = Q.pop()
            if done[j]: continue
            checking[j] = 1
            for k in E[j]:
                if checking[k]:
                    return []
                Q.append(k)
                Q.append(j)
                Q.append(3)
                Q.append(k)
                Q.append(2)
                Q.append(k)
                Q.append(1)
    return L[::-1]
def ca(i, j):
    return max(i, j) * (max(i, j)-1) // 2 + min(i, j)

N = int(input())
M = N * (N-1) // 2
X = [[] for i in range(M)]
for i in range(N):
    A = [int(a)-1 for a in input().split()]
    for j in range(N-2):
        X[ca(i, A[j])].append(ca(i, A[j+1]))
D = [0] * M
L = ts(X)
print(max(D) + 1 if L else -1)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2+1):
  matchfunc=lambda x: (x==b[b[x]-1]-1 and b[x]!=x+1)
  match=list(filter(matchfunc,range(N)))
  #print(match)
  for i in range(len(match)):
    c[match[i]]+=1
    b[match[i]]=a[match[i]][c[match[i]]]
    if match==[]:
      print(-1)
      exit()  
  #for i in range(N):
    #if b[i]==i+1:
      #cnt+=0
    #elif i==b[b[i]-1]-1:
      #c[i]+=1
  #print('c='+str(c))
  #for i in range(N):
    #b[i]=a[i][c[i]]
  #print('b='+str(b))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()

print('-1')

Submission status: Time Limit Exceeded

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

day=0

match=[0 for i in range(n)]
jyunban=[i for i in range(n)]

while True:
  jyunban_n=[]
  day+=1
  check=[True for i in range(n)]
  for i in jyunban:
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
        jyunban_n.append(i)
        jyunban_n.append(vs)
      
    if i==jyunban[-1]:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
  jyunban=copy.copy(jyunban_n)
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  matchfunc=lambda x: (x==b[b[x]-1]-1 and b[x]!=x+1)
  match=list(filter(matchfunc,range(N)))
  #print(match)
  for i in range(len(match)):
    c[match[i]]+=1
    b[match[i]]=a[match[i]][c[match[i]]]
  #for i in range(N):
    #if b[i]==i+1:
      #cnt+=0
    #elif i==b[b[i]-1]-1:
      #c[i]+=1
  #print('c='+str(c))
  #for i in range(N):
    #b[i]=a[i][c[i]]
  #print('b='+str(b))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()

print('-1')

Submission status: Time Limit Exceeded

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

class Cycle(Exception):
    pass

paths = {}
st = set()

def dfs(a, b):

    node = (min(a, b), max(a, b))

    if node in paths:
        return paths[node]

    if node in st:
        raise Cycle()

    st.add(node)

    ns = [1]
    i = A[a].index(b)
    for j in range(i):
        ns.append(1 + dfs(a, A[a][j]))

    i = A[b].index(a)
    for j in range(i):
        ns.append(1 + dfs(b, A[b][j]))

    st.remove(node)
    paths[node] = max(ns)
    return paths[node]

ans = -1
try:
    for i in range(N):
        for j in range(N - 1):
            ans = max(ans, dfs(i, A[i][j]))
    print(ans)
except Cycle:
    print(-1)

Submission status: Time Limit Exceeded

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

class Cycle(Exception):
    pass

paths = {}
st = set()

def dfs(a, b):

    node = (min(a, b), max(a, b))

    if node in paths:
        return paths[node]

    if node in st:
        raise Cycle()

    st.add(node)

    ns = [1]
    i = A[a].index(b)
    for j in range(i):
        ns.append(1 + dfs(a, A[a][j]))

    i = A[b].index(a)
    for j in range(i):
        ns.append(1 + dfs(b, A[b][j]))

    st.remove(node)
    paths[node] = max(ns)
    return paths[node]

ans = -1
try:
    for i in range(N):
        ans = max(ans, dfs(i, A[i][-1]))
    print(ans)
except Cycle:
    print(-1)

Submission status: Time Limit Exceeded

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

class Cycle(Exception):
    pass

paths = {}
st = set()

def dfs(a, b):

    if (a, b) in paths:
        return paths[(a, b)]

    if (a, b) in st:
        raise Cycle()

    st.add((a, b))

    ns = [1]
    i = A[a].index(b)
    for j in range(i):
        ns.append(1 + dfs(a, A[a][j]))

    i = A[b].index(a)
    for j in range(i):
        ns.append(1 + dfs(b, A[b][j]))

    st.remove((a, b))
    paths[(a, b)] = max(ns)
    return paths[(a, b)]

ans = -1
try:
    for i in range(N):
        ans = max(ans, dfs(i, A[i][-1]))
    print(ans)
except Cycle:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  A.append(list(map(int, input().split())))
#試合にコードを割り当てる
#of[l] = 前の番号の競技者の「既に数え上げた試合の数」
#r = 相手
#l = じぶん
def code(l, r, of):
  if l > r:
      l, r = r, l
  return of[l] + r - l - 1
#オフセットを作る。重複の試合を取り除くため、
#1ならN - 1試合、2ならN - 2試合...という風にする
of = [0] * (N + 1)
for i in range(N):
  of[i + 1] = of[i] + N - i - 1
#print(of)
#試合の前後関係を持つグラフ
#たぶんDAGになっている。なってないなら試合組めないと思う
g = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
  for j in range(N - 2):
      fcode = code(i, A[i][j] - 1, of)
      tcode = code(i, A[i][j + 1] - 1, of)
      g[fcode].append(tcode)
#print(g)
def sort_topologically(g):
  n = len(g)
  #ecはコードによる試合頂点の入次数を記録
  ec = [0] * n
  for i in range(n):
    for e in g[i]:
      ec[e] += 1
  #print(ec)
  #retは入次数0の頂点を順にとってきている
  ret = [0] * n
  q = 0
  for i in range(n):
    if ec[i] == 0:
      ret[q] = i
      q += 1
  #p = 参照中の入次数0の試合
  #q = 入次数0の頂点数
  #while文はp == qの時点で終わる
  #for文では、入次数0の頂点pから出る有向辺を除去する
  #その上で入次数0の頂点が増えればretへ追加
  #このretは確かにトポロジカル順序になる
  p = 0
  #print(ret)
  while p < q:
    for to in g[ret[p]]:
      ec[to] -= 1
      if ec[to] == 0:
        ret[q] = to
        q += 1
    p += 1
  #ソートが終わったなら全ての辺は除去済みのはずである
  #このグラフは一応連結しているはずなので閉路検知ができる
  for i in range(n):
    if ec[i] > 0:
      return None
  return ret

od = sort_topologically(g)
#print(od)
#Noneなら閉路を持つので試合構築不可能
if not od:
  print(-1)
else:
  #dp = トポロジカル順序を持つ順序集合の先頭からi番目までを見た際の最大パス長
  dp = [1] * (N * (N - 1) // 2)
  for i in range(N * (N - 1) // 2):
    for e in g[od[i]]:
      dp[e] = max(dp[e], dp[od[i]] + 1)
  #print(dp)
  print(max(dp))

Submission status: Time Limit Exceeded

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

day=0
last_i=0
jyunban=[i for i in range(n)]
match=[0 for i in range(n)]
while True:
  day+=1
  check=[True for i in range(n)]
  jyunban_n=[]
  if jyunban==[]:
    print(-1)
    sys.exit()
  
  for i in jyunban:
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
        jyunban_n.append(i)
        jyunban_n.append(vs)
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())

a = []
for i in range(n):
  v = list(map(int, input().split(' ')))
  a.append(v)

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	ggl=lambda : list(map(int, input().split()))
	aal=[ggl() for _ in range(n)]
	
	match_list=[al[0] for al in aal]
	finised_num=[0]*n
	last_match_day=[0]*n
	
	ttn=0
	
	dd=0
	while ttn < n*(n-1):
		dd+=1
		pttn = ttn
		
		for i, nm in enumerate(match_list):
			pp=nm-1
			if nm == -1 or last_match_day[i] >=dd or last_match_day[pp] >= dd:
				#print(i,nm)
				pass
			elif match_list[nm-1]==i+1:
				if finised_num[i] >= n-2:
					match_list[i]=-1
				else:
					match_list[i]=aal[i][finised_num[i]+1]
					
				if finised_num[pp] >= n-2:
					match_list[pp]=-1
				else:
					match_list[pp]=aal[pp][finised_num[pp]+1]
					
				finised_num[i]+=1
				finised_num[pp]+=1
				last_match_day[i]=dd
				last_match_day[pp]=dd
				ttn+=2
		
		if pttn==ttn:
			return -1
			
	return dd
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def make(x,y):
    if x<y:
        return str(x)+"_"+str(y)
    else:
        return str(y)+"_"+str(x)


n = int(input())

s = set()
r = set()
edge = {}
redge = {}
for x in range(n):
    al = list(map(lambda x:int(x)-1, input().split()))
    s.add(make(x,al[0]))
    for i in range(len(al)-1):
        v = make(x,al[i])
        u = make(x,al[i+1])

        if v not in edge:
            edge[v] = []
        edge[v].append(u)
        if u not in redge:
            redge[u] = set()
        redge[u].add(v)
        r.add(u)

s = s - r

res = 0
while len(s)>0:
    res += 1
    s2 = set()
    for v in s:
        if v not in edge:
            continue
        for u in edge[v]:
            redge[u].remove(v)
            if len(redge[u])==0:
                s2.add(u)
    s = s2

for v in redge:
    if len(redge[v])>0:
        print(-1)
        exit()
print(res)