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:
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]

    now = [0] * N
    day = 0
    MAX = (N*(N-1)) // 2
    gamed_day = [-1] * N
    finished = 0
    while True:
        if day > MAX:
            print(-1)
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.9:
        print(n**2 //2)
        exit()
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        A = [list(map(int, input().split())) for _ in range(N)]

        already_p = set()
        days = 0
        done = set()
        while True:
            for i, a in enumerate(A):
                if len(a) == 0:
                    done.add(i + 1)
                    continue
                if i + 1 not in already_p:
                    if a[0] not in already_p:
                        if A[a[0] - 1][0] == i + 1:
                            already_p.add(i + 1)
                            already_p.add(a[0])
                            A[a[0] - 1] = A[a[0] - 1][1:]
                            A[i] = a[1:]

            if len(done) == N:
                break

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

            already_p = set()
            days += 1

        print(days)


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
match_players = {i: [int(x)-1 for x in input().split()] for i in range(n)}

res = -1
daycnt = 0
isdones = [False] * n
while True:
  daycnt += 1
  played_idxs = []
  is_matched = False
  for i in range(n):
    if i in played_idxs:
      continue
    if isdones[i]:
      continue
    target_idx = match_players[i][0]
    if target_idx in played_idxs:
      continue
    if match_players[target_idx][0] == i:
      is_matched = True
      played_idxs.append(target_idx)
      played_idxs.append(i)
      del match_players[i][0]
      if len(match_players[i]) == 0:
        isdones[i] = True
      del match_players[target_idx][0]
      if len(match_players[target_idx]) == 0:
        isdones[target_idx] = True
  if all(isdones):
    res = daycnt
    break
  if is_matched is False:
    res = -1
    break

print(res)

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

N = int(input())
n = N

data= [ [int(elm) - 1 for elm in input().split(" ")] for i in range(N)]
#print(data)

nexts = [0 for _ in range(n)]
goal = [N-1 for _ in range(n)]

day = 1
while True:
    done = False
    nows = []
    for jibun_i in range(n):
        next_i = nexts[jibun_i]
        if next_i == n-1 or jibun_i in nows:
            continue

        #print(jibun_i, next_i)
        aite_i = data[jibun_i][next_i]

        if data[aite_i][nexts[aite_i]] == jibun_i and aite_i not in nows:
            done = True
            nexts[jibun_i] += 1
            nexts[aite_i] += 1
            nows += [jibun_i, aite_i]

    if goal == nexts:
        out = day
        break
    if not done:
        out = -1
        break
    
    day += 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
total = N*(N-1)//2
flag = 1
cnt = 0
days = 0
while flag:
  flag = 0
  for i in range(N-1,-1,-1):
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        flag = 1
        cnt += 1
  else:
    if flag == 1:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque
 
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
 
n = getN()
 
match = [0 for i in range((n*(n-1))//2)]
child = [[] for i in range((n*(n-1))//2)]
isroot = [True for i in range((n*(n-1))//2)]
 
 
def bfs():
    q = deque([])
    for root, rt in enumerate(isroot):
        if rt:
            q.append(root)
            match[root] = 1
    # print(match)
    while(q):
        item = q.popleft()
        # print(q, item, child[item])
        for ch in child[item]:
            if match[ch] < match[item] + 1:
                match[ch] = match[item] + 1
                q.append(ch)
 
    return
 
 
 
 
for idd in range(n):
    nums = getList()
    i = idd + 1
    for j,k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i,j)
        iii, k = min(i, k), max(i,k)
        idx1 = ((j-1)*(j-2))//2 + (ii-1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        isroot[idx2] = False
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)
 
#
# print(child)
# print(isroot)
# # sys.exit()
 
bfs()
# print("gg")
ans = 1
for m in match:
    if m > ans:
        ans = m
    if m == 0:
        print(-1)
        sys.exit()
 
print(ans)

Submission status: Time Limit Exceeded

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

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
    if abs(s_time - time.time()) > 1.9:
        print(n**2 //2)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  import sys

  sys.setrecursionlimit(10**7)
  readline = sys.stdin.readline

  
  n = int(readline())
  a = [list(map(int,readline().split())) for _ in range(n)]
  d = 0
  m = set(range(n))
  
  while m:
    candidate = set()
    for i in m:
      if i in candidate or not a[i]:
        continue
      j = a[i][0]-1
      if a[j][0]-1 == i:
        candidate.add(i)
        candidate.add(j)

    if candidate:
      for i in candidate:
        a[i] = a[i][1:]
        if not a[i]:
          m.remove(i)
      d+=1
    else:
      d=-1
      break
      
  print(d)


if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ann = [[0 for x in range(n-1)]]+[[int(x) for x in input().split()]for i in range(n)]
# print(ann)

indexes = [0 for x in range(n+1)]
#
days = 0
match_count = 0
fight_persons = {}
while(match_count < (n*(n-1))//2):
    fight_persons = set([])
    # print(f"{days} day")
    # print(indexes)
    for self_i,an in enumerate(ann[1:]):
        self_i += 1
        # print(f"self_i = {self_i}")
        if self_i in fight_persons or len(an) <= indexes[self_i]:
            continue
        person_i = an[indexes[self_i]]
        # print(f"person_i = {person_i}")
        if person_i in fight_persons or len(ann[person_i]) <= indexes[person_i]:
            continue
        if ann[person_i][indexes[person_i]] == self_i:
            # print("fight!!!")
            # print(person_i,self_i)
            match_count += 1
            indexes[self_i] += 1
            indexes[person_i] += 1
            fight_persons.add(self_i)
            fight_persons.add(person_i)
    # print(fight_persons)
    if len(fight_persons) > 0:
        days += 1
    else:
        break


# print("+++++++++++++++")
if match_count < (n*(n-1))//2:
    print(-1)
else:
    print(days)

Submission status: Time Limit Exceeded

Solution code:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count, more_play, nexts):
    count = 0
    roop_count = 0##########
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if more_play[i] and already_played[i] == 0:
                p1 = i
                if nexts[p1] == N-1:
                    continue
                p2 = A_lst[p1][nexts[p1]]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                
                if nexts[i] == N-1:
                    continue
                if A_lst[p2][nexts[p2]] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    nexts[p1] += 1
                    nexts[p2] += 1
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if len(A_lst[p1]) == 0:
                        more_play[p1] = False
                    if len(A_lst[p2]) == 0:
                        more_play[p2] = False
                    roop_count += 1########
            if roop_count > 10**6:########
                return -1#########
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)
more_play = [True]*(N+1)
nexts = [0]*(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, more_play, nexts)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
l = [0] * N
ans = 0
count = 0
check = [False] * N
tmpl = []

while(count <= N - 1):
    check = [False] * N
    for i in range(N):
        if l[i] < N - 1:
            to = A[i][l[i]] - 1
            if (not check[to]) and (not check[i]):
                if A[to][l[to]] - 1 == i:
                    l[i] += 1
                    l[to] += 1
                    check[to] = True
                    check[i] = True
                if l[i] == N - 1:
                    count += 1
                if l[to] == N - 1:
                    count += 1
    ans += 1
    if tmpl == l:
        print(-1)
        exit()
    tmpl = l[:]
    # print(l, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = int(0)
A =[[0 for i in range(N)] for j in range(N)]
Lcandi = []
count =int(0)
Ln = int(0)
Lm = int(N*(N-1)//2)

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

while Ln<Lm:
    Lcandi = []
    Lnc = int(0)
    for i in range(N):
        if len(A[i]) != 0:
            if i+1 < A[i][0]:
                if not ([i+1,A[i][0]]) in Lcandi:
                    Lcandi.append([i+1, A[i][0]])
                else:
                    A[A[i][0]-1].remove(i+1)
                    A[i].remove(A[i][0])
                    Lnc +=1

            else:
                if not ([A[i][0],i+1]) in Lcandi:
                    Lcandi.append([A[i][0],i+1])
                else:
                    z=int(0)
                    z=A[i][0]
                    A[z-1].remove(i+1)
                    A[i].remove(A[i][0])
                    Lnc +=1

    if Lnc ==0:
        print("-1")
        exit()
    Ln += Lnc
    count +=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
alist=[]
nowlist=[]
klist=[]
incre=0
error=0
day=0
 
for i in range(n):
    alist.append(list(map(int, input().split())))
 
for i in range(n):
    nowlist.append(0)
 
while error==0 and incre<n*(n-1):
    koho=[]
    for i in range(n):
        if nowlist[i]<n-1:
            small=sorted([i+1, alist[i][nowlist[i]]])
            koho.append(small)
    koho=sorted(koho)
    swit=0
    for i in range(len(koho)-1):
        if koho[i]==koho[i+1]:
            nowlist[koho[i][0]-1]+=1
            nowlist[koho[i][1]-1]+=1
            incre+=2
            swit=1
    day+=1
    if swit==0:
        day=-1
        error=1
    #print(nowlist)
 
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
index = [0]*(N+1)
ans = -2
for k in range(30000):
    today = set()
    flag = 0
    for j in range(N):
        if j+1 in today:
            continue
        if index[j+1] >= N-1:
            continue
        #print(j, index[j+1])
        opponent = A[j][index[j+1]]
        if A[opponent-1][index[opponent]] == j+1:
            if opponent not in today:
                index[opponent] += 1
                index[j+1] += 1
                today.add(opponent)
                today.add(j+1)
                flag = 1
    if flag == 0:
        if sum(index) == N*(N-1):
            ans = k
            break
        else:
            ans = -1
            break
    #print(index)

if ans == -2:
    print(N*(N-1)//2)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
t = [[[0,0],0]]
for i in range(n):
    p = readl()
    t.append([p, 0, 0])
t.append([[-1],0])
day = 0
nn = n - 1
cnt = 0
while(1):
    day += 1
    flg = False
    for i in range(1, n + 1):
        if t[i][1] == nn:
            continue
        p = t[i][0][t[i][1]]
        if t[p][1] == nn:
            continue
        if t[p][0][t[p][1]] == i and t[i][2] != day and t[p][2] != day:
            t[i][1] += 1
            t[p][1] += 1
            t[i][2] = day
            t[p][2] = day
            flg = True
        if t[i][1] == nn:
            cnt += 1
        if t[p][1] == nn:
            cnt += 1
    if cnt >= n:
        break
    if not(flg):
        print(-1)
        exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
total = N*(N-1)//2
flag = 1
cnt = 0
days = 0
while flag:
  flag = 0
  for i in range(N):
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        flag = 1
        cnt += 1
  else:
    if flag == 1:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = {j:iter(map(int, input().split())) for j in range(1,N+1)}
    res = 0
    B = {j:next(A[j]) for j in A}
    I = set(range(1,N+1))
    while A:
        B_ = dict()
        I_ = set() 
        checked = False
        for j in I:
            if B[B[j]] == j:
                try:
                    B_[j] = next(A[j])
                except StopIteration:
                    A.pop(j)
                    I_.add(j)
                checked = True
        if checked:
            res += 1
            for j in I_:
                B.pop(j)
            B.update(B_)
            I -= I_
        elif A:
            res = -1
            break

    return str(res)

if __name__ == '__main__':
    print(solve())

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 [j for j, i in enumerate(l) if l[j]!=N-1 ]:
        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:
import sys
import time

def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1.7):
            print('-1')
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()

Submission status: Time Limit Exceeded

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

cnt = 0
check = []
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in range(1,n):
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][0]
        if temp <= i:
            continue
        if li[temp-1][0] == i and temp not in check:
            del li[i-1][0]
            del li[temp-1][0]
            play += 1
            check.append(temp)
    cnt += 1
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    a = [int(j) - 1 for j in input().split()]
    A[i] += reversed(a)

empty = [[] for i in range(N)]
ans = 0
for _ in range(N * (N - 1) // 2):
    flag = False
    game_flag = [False] * N
    for i in range(N):
        if game_flag[i] == False and A[i] != []:
            j = A[i][-1]
            if game_flag[j] == False and A[j] != [] and A[j][-1] == i:
                flag = game_flag[i] = game_flag[j] = True
                A[i].pop()
                A[j].pop()

    ans += 1
    if A == empty:
        break
    elif flag == False:
        ans = -1
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def league():
    i  = lambda: int(input())
    li = lambda: list(map(int, input().split()))
        
    N = i()
    A = [li() for _ in range(N)]
    
    day = 0
    while True:
        day += 1
        vsp = []
        for i in range(N):
            p = i
            if i in vsp:
                continue
            if len(A[p]) == 0:
                continue
            vp = A[p][0]-1
            while p != A[vp][0]-1:
                p = vp
                vp = A[p][0]-1
                if vp == i:
                    return '-1'
            if vp in vsp or p in vsp:
                continue
            vsp += [p, vp]
            A[p] = A[p][1:]
            A[vp] = A[vp][1:]
        if sum([len(a) for a in A]) == 0:
            return day

print(league())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
def main():
  a=int(input())
  b=[[]for i in range(a)]
  for i in range(a):
    b[i]=deque(list(map(int,input().split())))
  c=[[]for i in range(a)]
  ans=0
  d=[0 for i in range(a)]
  while sum(len(v) for v in b)!=0:
    f=[0 for i in range(a)]
    ans+=1
    T=0
    for i in range(a):
      if d[i]==0 and f[i]==0 and len(b[i])>0:
        e=b[i][0]-1
        if e in c[i]:
          c[i].pop(c[i].index(e))
          T=1
          b[e].popleft()
          b[i].popleft()
          d[i]=0
          d[e]=0
          f[i]=1
          f[e]=1
        else:
          c[e].append(i)
          d[i]=1
    if T==0:
      print(-1)
      exit()
      
      
  print(ans)  
if __name__ == '__main__':  
  main()

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()
        A_list = [LI() for i in range(N)]
        #  for i in range(N):
        #      A_list.append(LI())
        #  perr(A_list)
    new_A_list = {}
    for aidx in range(N):
        new_A_list[aidx] = tuple(i-1 for i in A_list[aidx])
    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 = {}
    position_sum = 0
    done_sum = (N-1)*N
    #  all_done_players = set()
    N_1 = N - 1
    for _ in range(10**7):
        #  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_1):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if done_player_list.get(i):
                continue

            #  if i in all_done_players:
            if current_position_list.get(i) == N-1:
                # この選手はすべての試合を終了している
                continue

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

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

            # iの試合相手の次の相手が選手iなら成立する
            if A_list.get(opponent_idx)[current_position_list.get(opponent_idx)] == i:
                #  print('試合した', i, opponent_idx)
                # 試合可能
                #  done_player_list.extend([i, opponent_idx])
                #  done_player_list += (opponent_idx, i)
                done_player_list[i] = True
                #  done_player_list.add(opponent_idx)
                done_player_list[opponent_idx] = True
                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 = {}
        current_day += 1

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

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())

n2 = []

for i1 in range(n1):
    n2.append([int(i) for i in input().split()])

n3 = [0] * n1
r1 = 0
a1 = 0

for i2 in range(500000):
    r1 += 1
    d1 = {}
    for i3 in range(n1 - 1):
        if n3[i3] >= n1 - 1:
            continue
        t2 = n2[i3][n3[i3]] - 1
        if d1.get(i3, 0) == 0:
            if d1.get(t2, 0) == 0:
                if n2[t2][n3[t2]] == (i3 + 1) :
                    if i3 < t2:
                        n3[i3] += 1
                        n3[t2] += 1
                        d1[i3] = 1
                        d1[t2] = 1
                        a1 += 1

    if a1  >= (n1 * (n1 - 1)) // 2:
        break
    if len(d1) == 0:
        r1 = -1
        break

print(r1)

Submission status: Time Limit Exceeded

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

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
for day in range(1, 900000):
    finish = [0]*(n+1)
    possible = False
    for me in range(1, n+1):
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                possible = True
                count += 1
            else:
                continue

    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
match_players = {i: [int(x)-1 for x in input().split()] for i in range(n)}
isdones = [False] * n


daycnt = 0
while not all(isdones):
  daycnt += 1
  played_idxs = []
  for i in range(n):
    if i in played_idxs:
      continue
    if isdones[i]:
      continue
    target_idx = match_players[i][0]
    if match_players[target_idx] == i:
      played_idxs.append(target_idx)
      del match_players[i][0]
      if len(match_players[i]) == 0:
        isdones[i] = True
      del match_players[target_idx][0]
      if len(match_players[target_idx]) == 0:
        isdones[target_idx] = True

print(daycnt)