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 queue import deque
N = int(input())
A = {}
for i in range(1,N+1):
    A[i] = deque(map(int,input().split()))
# print(A)

GAME = N*(N-1)//2
cnt = 0
ans = 0
cnt2 = 0
while cnt < GAME:
    ok = [True]*N
    for i in range(1,N+1):
        if A[i] and ok[i-1]:
            t = A[i][0]
            if ok[t-1] and A[t] and i == A[t][0]:
                A[i].popleft()
                A[t].popleft()
                cnt += 1
                ok[i-1] = False
                ok[t-1] = False
    ans += 1
    cnt2 += 1
    if cnt2 > GAME:
        ans = -1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(lambda s: int(s) - 1, input().split())) for _ in range(n)]

def f():
    day = 0
    ptrs = [0] * n
    players = set(range(n))

    while players:
        visited = set()
        removals = set()
        for i in players:
            if i in visited:
                continue
            
            x = a[i][ptrs[i]] # iの次候補
            if x in visited:
                continue

            y = a[x][ptrs[x]] # xの次候補
            if i == y:
                ptrs[i] += 1
                ptrs[x] += 1
                visited.add(i)
                visited.add(x)
                if ptrs[i] == n - 1:
                    removals.add(i)
                if ptrs[x] == n - 1:
                    removals.add(x)

        # すべて未訪問の場合
        if len(visited) == 0:
            return -1
        players -= removals
        day += 1
    
    return day



print(f())

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

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

progress_list = [0] * N
next_list = [a[0] - 1 for a in A]
done_match = 0

day_limit = N * (N - 1) // 2 + 1
for i in range(day_limit):
    exhausted = [0] * N

    for man_idx in range(N):
        opponent_idx = next_list[man_idx]
        if (opponent_idx == -1) or exhausted[opponent_idx] or exhausted[man_idx]:
            continue
        opponents_opponent = next_list[opponent_idx]

        if man_idx == opponents_opponent:
            # print('day', i + 1, ',', man_idx + 1, opponent_idx + 1)
            exhausted[man_idx] += 1
            progress_list[man_idx] += 1
            if progress_list[man_idx] >= N - 1:
                next_list[man_idx] = -1
            else:
                next_list[man_idx] = A[man_idx][progress_list[man_idx]] - 1
            exhausted[opponent_idx] += 1
            progress_list[opponent_idx] += 1
            if progress_list[opponent_idx] >= N - 1:
                next_list[opponent_idx] = -1
            else:
                next_list[opponent_idx] = A[opponent_idx][progress_list[opponent_idx]] - 1
            done_match += 1

    if done_match == N * (N - 1) // 2:
        print(i + 1)
        exit()

else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N=int(input())

A=[[int(i) for i in input().split()] for _ in range(N)]
l=[0 for _ in range(N)]
ll=[0 for _ in range(N)]
day=0
while True:
    if min(l)==N-1:
        can=True
        break
    can=False
    for i in range(N):
        if l[i]==N-1:
            continue
        j=A[i][l[i]]-1
        if A[j][l[j]]-1==i:
            ll[i]+=1
            can=True
    l=deepcopy(ll)
    if can==False:
        break
    day+=1
if can==False:
    print(-1)
if can==True:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=0
	count+=1
	taisenzumi=[0]*n
	for i in range(n):
		if taisenzumi[i]:continue
		if data[i]:
			aite=data[i][0]
			# print(data[i],aite)
			if taisenzumi[aite-1]:continue
			# print(data[i],aite)
			if data[aite-1][0]==i+1:
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=1
			else:continue
	if not flag:
		break
else:
	print(count)
	exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])

ans = 0
zerodic = set()
while (True):
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in zerodic:
      if len(dic[i]) == 0:
        zerodic.add(i)
      elif i not in tmpset:
        aite = dic[i][0]
        if aite not in tmpset and dic[aite][0] == i:
          dic[i].popleft()
          dic[aite].popleft()
          tmpset.add(i)
          tmpset.add(aite)
          playcount += 1
  if playcount > 0:
    ans += 1
  if playcount == 0:
    break
failedflag = False
if len(zerodic) != N:
  failedflag = True
if failedflag:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
nt = []
for i in range(n):
  tmp = input().split()
  for j in range(n-1):
    tmp[j] = int(tmp[j])
  nt.append(tmp)

day = 0
j = []
for i in range(n):
  j.append(0)
  
while(True):
  #print(j)
  tmp = []
  for i in range(n):
    if j[i] < n-1 and nt[nt[i][j[i]]-1][j[nt[i][ j[i] ]-1]] == i+1:
      tmp.append(i)
  #print(tmp)
  if len(tmp) == 0:
    break
  for i in tmp:
    j[i] += 1
  day += 1
  
error = 0
for i in range(n):
  if j[i] != n-1:
    day = -1
    break

print(day)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n = int(input())
    am = []

    from collections import deque

    for i in range(n):
        am.append(deque(list(map(lambda x: int(x) - 1, input().split()))))

    cnt = n * (n - 1) // 2

    day = 0
    while cnt > 0:
        day += 1
        match = 0
        done = {}
        for i in range(n):
            if i in done:
                continue
            if len(am[i]) == 0:
                continue
            j = am[i][0]
            if j not in done and am[j][0] == i:
                am[i].popleft()
                am[j].popleft()
                done[i] = 1
                done[j] = 1
                match += 1

        if match == 0:
            print(-1)
            return
        else:
            cnt -= match

    print(day)
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = [[]]
for i in range(N):
    A.append(deque(map(int,input().split())))
checklist = [-1] * (N+1)
day = 0
total = 0
flg = True
#どうせTLE
while total < (N*(N-1)//2) and flg:
    flg = False
    for i in range(1,N+1):
        if A[i] and A[A[i][0]]:
            enemy = A[i][0]
            if A[enemy][0] == i and checklist[enemy] < 0 and checklist[i] < 0:
                checklist[i] = 1
                checklist[enemy] = 1
                A[enemy].popleft()
                A[i].popleft()
                total += 1
                flg = True
    checklist = [-1] * (N+1)
    day += 1

if flg:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [list(int(_) for _ in input().split()) for i in range(n)]
l = [i+[0] for i in l]
x = [0]*n
s = set(list(range(n)))

for i in range(n*(n+1)+1):
    if len(s) == 0:
        print(i)
        break
    z = [l[ii][x[ii]] for ii in range(n)]
    sdel = set()
    for ii in s:
        if z[z[ii]-1] == ii + 1:
            if x[ii] <= n - 3:
                x[ii] = x[ii]+1
            else:
                sdel.add(ii)
    [s.remove(ii) for ii in sdel]
    if i == n*(n+1):
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = [0]*N

for i in range(N):
    X = list(map(int,input().split()))
    X = deque(X)
    for j in range(N-1):
        X[j] = [i+1,X[j]]
    A[i] = X

res = 0
cnt = 0
while cnt < (N*(N-1))//2:
    prev = cnt
    flag = [0]*N
    for i in range(N):
        if flag[i] == 0:
            if len(A[i]) != 0:
                X = A[i][0]
                ind = X[1]-1
                if len(A[ind]) != 0:
                    if A[ind][0] == X[::-1] and flag[ind] == 0:
                        A[i].popleft()
                        A[ind].popleft()
                        flag[i] = 1
                        flag[ind] = 1
                        cnt += 1
        else:
            continue
    if cnt == prev:
        res = -1
        break
    else:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
fin = [False] * N
sleep = [False] * N
An = [''] * N
deg = [0] * N
for n in range(N):
    An[n] = [int(x) for x in input().split()]

days = 0
while False in fin:
    days += 1
    matched = [False] * N
    flag = False
    for n in [n for n in range(N) if fin[n]==False and sleep[n]==False]:
        if matched[n]:
            continue
        op = An[n][deg[n]]
        if matched[op - 1]:
            continue
        if An[op - 1][deg[op - 1]] == n + 1:
            flag = True
            matched[n] = True
            matched[op - 1] = True
            deg[n] += 1
            deg[op - 1] += 1
            sleep[op - 1] = False
            if deg[n] == N - 1:
                fin[n] = True
            if deg[op - 1] == N - 1:
                fin[op - 1] = True
        else:
            sleep[n] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class Solution:
    def main(self):
        N = int(input())
        A = []
        for i in range(N):
            a = list(map(lambda x: int(x)-1, input().split())) + [-1]
            A.append(a)

        hashmap = defaultdict(set)
        for i in range(N):
            hashmap[A[i][0]].add(i)

        # print(hashmap)

        cnt = 0
        old_cnt = 0
        checklist = set(range(N))

        for day in range(1, N*(N-1)+1):
            cands = set()
            for i in checklist:
                if i in hashmap and A[i][0] in hashmap[i]:
                    if i < A[i][0]:
                        cands.add((i, A[i][0]))
                    else:
                        cands.add((A[i][0], i))

            for x, y in cands:
                # print(x, y)
                hashmap[y].remove(x)
                hashmap[x].remove(y)
                hashmap[A[x][1]].add(x)
                hashmap[A[y][1]].add(y)
                A[x].pop(0)
                A[y].pop(0)
                cnt += 1

            if cnt == N*(N-1)//2:
                print(day)
                break
            elif cnt == old_cnt:
                print(-1)
                break
            else:
                old_cnt = cnt
                checklist = set().union(*cands)
                # print(cands)
                # print(checklist)


if __name__ == '__main__':
    Solution().main()

Submission status: Time Limit Exceeded

Solution code:
#
import random


def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)

    ans = 0
    targets = list(range(n))
    random.shuffle(targets)

    while True:
        match = set()
        for i in targets:
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]]
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        s, t = edge
        self.E[s].append(t)


def solve(N: int, A: "List[List[int]]"):
    a_head = [0]*N
    battle = [True]*N
    next_battle = battle[:]

    day = -1
    g = Graph(N)

    while True:
        day += 1
        flag = False

        battle[:] = next_battle
        for i, h in enumerate(a_head):
            # print(battle)
            if h == N-1:
                continue
            if battle[i] == True:
                next_battle[i] = False
            else:
                continue
            # print("day:{}, {}, {}".format(day+1, i+1, A[i][h]-1))
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True

                next_battle[i] = True
                next_battle[A[i][h]-1] = True
                g.E[A[i][h]-1].remove(i)
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        print(day)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]
count=0
match=0
max_match=n*(n-1)//2
flag=True
while(match!=max_match):
    s=set()
    for i in range(1,n+1):
        if A[i-1] and (not {i,A[i-1][0]}&s):
            j = A[i-1][0]
            if i==A[j-1][0]:
                match+=1
                s|={i,j}
                A[i-1].pop(0)
                A[j-1].pop(0)
    if not s:
        flag = False
        break
    count+=1
print(count if flag else -1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

match = n * (n - 1) // 2
day = 0
waiting = []
finished = 0
for i in range(n):
    waiting.append(list(map(int, input().split())))

while match != 0:
    ml = [0] * n
    for i, wait_l in enumerate(waiting):
        if len(wait_l) == 0 or len(waiting[wait_l[0] - 1]) == 0:
            continue
        if ml[i] == 0 and ml[wait_l[0] - 1] == 0:
            if (i + 1) == waiting[wait_l[0] - 1][0]:
                ml[i] = 1
                ml[wait_l[0] - 1] = 1
                if len(waiting[i]) != 1:
                    waiting[i] = waiting[i][1:]
                else:
                    waiting[i] = []
                    finished += 1
                if len(waiting[wait_l[0] - 1]) != 1:
                    waiting[wait_l[0] - 1] = waiting[wait_l[0] - 1][1:]
                else:
                    waiting[wait_l[0] - 1] = []
                    finished += 1
                match -= 1
    if sum(ml) != 0:
        day += 1
        if finished == n:
            print(day)
            exit()
    else:
        print("-1")
        exit()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def judge_and_count(A_lst, already_played, played_count):
    count = 0
    roop_count = 0
    while np.sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if roop_count > 10**8:
                        return -1
        count += 1
        already_played[:] = 0 # 10**3
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = np.zeros(N+1)
played_count = np.zeros(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections

def solve(N: int, A: "List[List[int]]"):
    res = 0

    while any([len(a) > 0 for a in A]):
        matched = set()
        any_mached = False
        for i,a in enumerate(A): 
            if len(a) > 0 and i not in matched:
                enemy = a[0] - 1
                if len(A[enemy]) > 0 and enemy not in matched:
                    enemy_enemy = A[enemy][0] - 1
                    if i == enemy_enemy:
                        del A[i][0]
                        del A[enemy][0]
                        matched.add(i)
                        matched.add(enemy)
                        any_mached = True
        if not any_mached:
            res = -1
            break
        res += 1

    print(res)
    return

def solve2(N: int, A: "List[List[int]]"):
    res = 0

    A = { i : collections.deque(a) for i,a in enumerate(A) }

    while len(A.items()):
        matched = set()
        del_keys = set()
        any_mached = False
        for i,a in A.items(): 
            if len(a) > 0 and i not in matched:
                enemy = a[0] - 1
                if len(A[enemy]) > 0 and enemy not in matched:
                    enemy_enemy = A[enemy][0] - 1
                    if i == enemy_enemy:
                        A[i].popleft()
                        if not len(A[i]):
                            del_keys.add(i)
                        A[enemy].popleft()
                        if not len(A[enemy]):
                            del_keys.add(enemy)
                        matched.add(i)
                        matched.add(enemy)
                        any_mached = True
        if not any_mached:
            res = -1
            break

        for k in del_keys:
            del A[k]

        res += 1

    print(res)
    return

def solve3(N: int, A: "List[List[int]]"):
    res = 0

    A = { i : a for i,a in enumerate(A) }

    while len(A.items()):
        matched = set()
        del_keys = set()
        any_mached = False
        for i,a in A.items(): 
            if len(a) > 0 and i not in matched:
                enemy = a[-1] - 1
                if enemy in A and enemy not in matched:
                    enemy_enemy = A[enemy][-1] - 1
                    if i == enemy_enemy:
                        A[i].pop()
                        if not len(A[i]):
                            del_keys.add(i)
                        A[enemy].pop()
                        if not len(A[enemy]):
                            del_keys.add(enemy)
                        matched.add(i)
                        matched.add(enemy)
                        any_mached = True
        if not any_mached:
            res = -1
            break

        for k in del_keys:
            del A[k]

        res += 1

    print(res)
    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ [ int(next(tokens)) for _ in range(N-1) ] for _ in range(N) ]  # type: "List[List[int]]"
    solve3(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    row = list(map(int, input().split()))
    row = [r - 1 for r in row]
    A.append(row)

A.append([1000] * N)

counter = [0] * (N + 1)
finish = 0

ans = 0
check_done = set()
while finish < N * (N - 1) // 2:
    checked = set()
    ans += 1

    exit_flg = True
    for n in range(N):
        # ある日程ですでにnは戦っている
        if n in checked:
            continue
        checked.add(n)

        # nの対戦は終了
        if counter[n] == N - 1:
            continue

        n_match = A[n][counter[n]]  # nの対戦相手
        n_match_match = A[n_match][counter[n_match]]  # nの対戦相手の対戦相

        # nの対戦相手はある日の試合をすでに終えている
        if n_match in checked:
            continue

        # マッチング成立
        if n == n_match_match:
            exit_flg = False

            checked.add(n_match)

            finish += 1
            counter[n] += 1
            counter[n_match] += 1

    # 一つも組み合わせられなかった
    if exit_flg:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# Your code here!
n=int(input().rstrip())
a=[]
#been=[]
cnt=[]
for i in range(n):
    cnt.append(0)
   # been.append(0)
    a.append(input().rstrip().split(" "))
    for j in range(n-1):
        a[i][j]=int(a[i][j])
ans=0
day=0
last=int(n*(n-1)/2)


while(not last==0):
    olast=last
    day=day+1
    for i in range(n):
        cnt[i]=0
     #   been[i]=0
    for i in range(n):
        if(cnt[i]==1 or len(a[i])==0):# or been[i]==1):
            continue
        else:
            s=a[i][0]
            if(len(a[s-1])==0 or cnt[s-1]==1 or i >s-1):
                continue
            #been[i]=1
            if( i+1==a[s-1][0] and s==a[i][0]  ):
                cnt[i]=1
                cnt[s-1]=1
                last=last-1
                del a[i][0]
                del a[s-1][0]
    #print(a)
    #print(last)
    if(last==olast):
        day=-1
        break
    
    
print(day)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  l=[]
  for _ in range(n):
    _l=LI()
    _l.reverse()
    l.append(_l)

  c=n*(n-1)
  ans=1
  nagasa=[n-1]*n
  while True:
    m=[0]*n
    _c=c

    for i in range(n):
      if c<=0:
        return ans

      if m[i]!=0:
        continue

      if nagasa[i]!=0:
        a=l[i][-1]-1

        if a<i:
          continue

        if m[a]!=0:
          continue

        if nagasa[a]!=0:
          if l[a][-1]==i+1:
            l[a].pop()
            l[i].pop()
            m[a]=1
            m[i]=1
            nagasa[a]-=1
            nagasa[i]-=1
            c-=2
          else:
            continue
        else:
          return -1
      else:
        continue
    if _c==c:
      return -1
    ans+=1
    if ans>n*n:
      return -1


  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		edge[match_dict[(x,y)]].append(match_dict[(z,w)])
		parent[match_dict[(z,w)]].append(match_dict[(x,y)])
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		if finish[c]:
			continue
		finish[c] = True
		for e in edge[c]:
			if finish[e]:
				continue
			can_match = True
			for p in parent[e]:
				if not finish[p]:
					can_match = False
					break
			if can_match:
				new_candidate.append(e)
	day += 1
	candidate = new_candidate

all_finished = sum([1 if f else 0 for f in finish]) == M
if all_finished:
	print(day)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from fractions import Fraction
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

def main():
    A_list = []
    if 'LOCAL' in os.environ:
        N = 1000
        for i in range(N):
            tmp = [j for j in range(N) if i != j]
            random.shuffle(tmp)
            A_list.append(tmp)

    else:
        N = _I()
        for i in range(N):
            A_list.append(LI())
        #  perr(A_list)
    new_A_list = {}
    for aidx, A in enumerate(A_list):
        new_A_list[aidx] = tuple(i-1 for i in A)
    A_list = new_A_list

    """
    まず、N=1000までなので、
    1000*1000=10**6まである。
    試合の日数を最小かする。
    つまりできるだけ効率よく1日に試合を詰め込むことを考える
    そもそも1のところに2とあったら、
    全通りを求めると？
    どの試合にするかで1000*999/2の階乗=10**6/2の階乗通りある
    まず選手iの1つ目を見ていく
    その相手のところをみて、current_idxがiだったら試合可能

    """

    current_opponent_idx = None
    current_day = 0
    is_ok = False
    # 各選手の試合状況
    current_position_list = {i:0 for i in range(N)}
    done_player_list = set()
    position_sum = 0
    done_sum = (N-1)*N
    all_done_players = set()
    while True:
        #  print('day: ', current_day)
        #  print('current position list', current_position_list)
        #  pdb.set_trace()
        is_ok = False
        #  if all(position == N-1 for position in current_position_list):
        if position_sum == done_sum:
            # 全試合終了
            break

        for i in range(N):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if i in done_player_list:
                continue

            if i in all_done_players:
                # この選手はすべての試合を終了している
                continue

            # iの試合相手のidx
            opponent_idx = A_list[i][current_position_list[i]]
            if opponent_idx in done_player_list:
                # 試合相手がすでに今日試合してた場合
                continue

            #  print('i', i)
            #  print('opponent', opponent_idx)

            # iの試合相手の次の相手が選手iなら成立する
            if A_list[opponent_idx][current_position_list[opponent_idx]] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                done_player_list.add(opponent_idx)
                done_player_list.add(i)
                current_position_list[i] += 1
                current_position_list[opponent_idx] += 1
                if current_position_list[i] == N-1:
                    all_done_players.add(i)
                if current_position_list[opponent_idx] == N-1:
                    all_done_players.add(opponent_idx)
                position_sum += 2
                # 試合がまだ可能であるというフラグをつける
                is_ok = True

        if not is_ok:
            # 1試合も成立しなかったらストップする
            print(-1)
            exit()

        done_player_list = set()
        current_day += 1

    print(current_day)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
league = []
match = {}
for i in range(n):
    league.append(list(map(int, input().split())))
    match[i+1] = league[i].pop()

ans = 0
cnt = 0
while cnt < n:
    tmp = []
    for k,v in match.items():
        if v in match and match[v] == k:
            tmp.append(v-1)
    if not tmp:
        print(-1)
        exit()
    for i in tmp:
        if not league[i]:
            cnt += 1
            del match[i+1]
        else:
            match[i+1] = league[i].pop()
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
nt = []
for i in range(n):
  tmp = input().split()
  for j in range(n-1):
    tmp[j] = int(tmp[j])
  nt.append(tmp)

day = 0
j = []
for i in range(n):
  j.append(0)
  
while(True):
  #print(j)
  tmp = []
  for i in range(n):
    if j[i] < n-1 and nt[nt[i][j[i]]-1][j[nt[i][ j[i] ]-1]] == i+1:
      tmp.append(i)
  #print(tmp)
  if len(tmp) == 0:
    break
  for i in tmp:
    j[i] += 1
  day += 1
  
error = 0
for i in range(n):
  if j[i] != n-1:
    day = -1

print(day)