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():
  from collections import deque
  n = int(input())
  a = [deque([int(i) for i in input().split()]) for j in range(n)]
  c = 0
  gamesNum = 0
  empty = False

  while not empty:
    flag = [1] * n
    for i in range(n):
      if flag[i] and len(a[i]):
        opponent = a[i][0] - 1
        if flag[opponent] and len(a[opponent]) and a[opponent][0] - 1 == i:
          flag[i] = 0
          flag[opponent] = 0
          gamesNum += 1
          a[i].popleft()
          a[opponent].popleft()

    if gamesNum:
      c += 1
      gamesNum = 0
    else:
      c = -1
      break

    for i in range(n):
      if len(a[i]):
        break
      if i == n-1:
        empty = True

  print(c)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

N=int(input())
L=[[]]

for i in range(N):
    a=deque(map(int,input().split()))
    L.append(a)
#print(L)

day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in range(1,N+1):
        #print(L[j],j)
        if len(L[j])==0 or j in D:
            continue
        elif L[L[j][0]][0]==j and L[j][0] not in D:
            D[j]=1
            D[L[j][0]]=1
            X=L[j][0]
            L[j].popleft()
            L[X].popleft()
            CNT+=1
    if CNT==0:
        print(-1)
        exit()
    cnt+=CNT
    day+=1
#print(L)
#print(cnt)
print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    N=int(input())
    A = [deque(map(int, input().split())) for _ in range(N)]

    days = 0
    changed = True
    played = set()
    while changed:
        played.clear()
        changed = False
        for i in range(N-1):
            if len(A[i]) == 0:
                continue
            a1 = A[i][0]
            if len(A[a1-1]) == 0:
                continue
            a2 = A[a1-1][0]
            if a1 in played or a2 in played:
                continue
            if a2-1 == i:
                A[a2-1].popleft()
                A[a1-1].popleft()
                played.add(a2)
                played.add(a1)
                changed = True
        if changed:
            days+=1

    for a in A:
        if len(a) > 0:
            print(-1)
            break
    else:
        print(days)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    for _ in range(N):
        A.append(list(map(int,input().split())))
    # next_pos = [A[i].pop(0) for i in range(N)]
    next_pos = []
    for i in range(N):
        next_pos.append(A[i].pop(0))
    ans = 0
    # check = [0 for _ in range(N)]
    check = []
    for _ in range(N):
        check.append(0)
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now == -1:
                continue
            if now in already:
                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] = 0
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = 0
                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:
import copy
n=int(input())
a=[[int(i)-1 for i in input().split()] for _ in range(n)]
day_check=[False for _ in range(n)]
day_cnt=0
match_cnt=0
while match_cnt<n*(n-1)//2:
    day_cnt+=1
    today_check=copy.copy(day_check)
    for i in range(n):
        if not a[i]:
            continue
        if today_check[i]:
            continue
        m=a[i][0]
        if a[m][0]==i and not today_check[m]:
            match_cnt+=1
            today_check[i]=True
            today_check[m]=True
            a[i].pop(0)
            a[m].pop(0)
    if not any(today_check):
        print(-1)
        exit()
print(day_cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

now = []
for i in range(n):
    now.append(a[i].popleft()-1)
    a[i].append(0)
# print(a)
# print(now)

ans = 0
battle = 0
max_battle = n*(n-1)//2
while battle < max_battle:
    checked = [False]*n
    nogame = True
    for i in range(n-1, -1, -1):
        x = i
        y = now[i]
        if checked[i] or checked[y] or now[i]==-1:
            continue
        checked[i] = True
        if now[y]==i:
            checked[y] = True
            now[x] = a[x].popleft()-1
            now[y] = a[y].popleft()-1
            battle += 1
            nogame = False
            # print(i, now)

    if nogame:
        print(-1)
        exit()
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

def main():
    cnt = N*(N-1) // 2
    status = [0]*(N+1)
    day = 0
    while cnt > 0:
        pre = cnt
        cur = [True]*(N+1)
        for i in range(1,N+1):
            if status[i] < N - 1:
                cmp = A[i-1][ status[i] ]
                if status[cmp] < N - 1:
                    cmpcmp = A[cmp-1][ status[cmp] ]
                    if cmpcmp == i and cur[i] and cur[cmp]:
                        status[i] += 1
                        status[cmp] += 1
                        cnt -= 1
                        cur[i] = False
                        cur[cmp] = False
        day += 1
        if pre == cnt:
            day = -1
            break
    print(day)
    return
main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
nt = []
for i in range(n):
  tmp = list(map(int, input().split()))
  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:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [dict() for _ in range(N)]
    for i in range(N):
        l = [int(a) - 1 for a in input().split()]
        for j in range(N-1): A[i][j] = l[j]

    #print(A)
    day = 0
    match = dict()
    for i in range(N): match[i] = 0

    #print(match)
    while True:
        onmatch = set()
        for i in range(N - 1):
            if i not in onmatch and match[i] < N - 1:
                vs = A[i][match[i]]
                op = match[vs]
                if op < N - 1:
                    if A[vs][op] == i and vs not in onmatch:
                        onmatch |= {i, vs}
                        match[i] += 1
                        match[vs] += 1
        if onmatch: day += 1
        else: break
    #print(match)

    for i in range(N):
        if match[i] < N - 1:
            print(-1)
            break
    else: print(day)

    return 0

if __name__ == "__main__": solve()

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]==sleep[n]==False]:
        if matched[n]:
            continue
        op = An[n][deg[n]]
        if matched[op - 1]:
            sleep[n] = True
            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:
import sys
input = sys.stdin.readline


class player:
    def __init__(self, rivals):
        self.rivals = rivals
        self.index = 0

    def get(self):
        return self.rivals[self.index]

    def next(self):
        self.index += 1

        if self.index >= len(self.rivals):
            return False
        else:
            return True


n = int(input())

players = [None]
for _ in range(n):
    tmps = list(map(int, input().split()))
    players.append(player(tmps))


max_match = int(n*(n-1)/2)
flag = [True]*(n+1)
flag[0] = False

matching = False

for i in range(1, max_match+1):
    tmp_flag = [True]*(n+1)

    for p in range(1, n+1):
        if flag[p] and tmp_flag[p]:
            r = players[p].get()
            if flag[r] and tmp_flag[r]:
                if p == players[r].get():
                    if not players[r].next():
                        flag[r] = False
                    tmp_flag[r] = False

                    if not players[p].next():
                        flag[p] = False

                    matching = True

            tmp_flag[p] = False

    s = sum(flag)
    if s == 0 or not matching:
        break

if s == 0:
    print(i)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

td = []
ans = 0
skip = 0
execflg = False
while 1:
        for idx, val in enumerate(A):
                if not val:
                        skip += 1
                        continue
                oppidx = val[0] - 1
                opp = A[oppidx][0]
                if idx in td or oppidx in td:
                        continue
                
                if opp == idx + 1:
                        execflg = True
                        A[idx].pop(0)
                        A[oppidx].pop(0)
                        td.append(idx)
                        td.append(oppidx)
        else:
                if execflg:
                        td=[]
                        ans += 1
                        execflg = False
                        skip = 0
                else:
                        if skip == N:
                                print(ans)
                        else:
                                print(-1)
                        exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
league = {}
match = {}
for i in range(n):
    league[i+1] = list(map(int, input().split()))
    match[i+1] = league[i+1].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)
    if not tmp:
        print(-1)
        exit()
    for i in tmp:
        if not league[i]:
            cnt += 1
            match[i] = 0
        else:
            match[i] = league[i].pop()
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
input = sys.stdin.readline
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a[:]
    

def f():
    IDX = {i: 0 for i in range(N)}
    day = 0
    end = 0
    while True:
        NEXT_IDX = {}
        flag = True
        for player, i in IDX.items():
            if i > N-2:
                continue
            enemy = A[player][i]
            if  A[enemy-1][IDX[enemy-1]] == player+1:
                next_idx = IDX[player]+1
                flag = False
                if next_idx == N-1:
                    end += 1
                else:
                    NEXT_IDX[player] = next_idx
            else:
                NEXT_IDX[player] = IDX[player]
        if flag:
            return(-1)
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX.copy()
print(f())

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 = tuple()
    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-1):
            #  print('--- in for---- current position list', current_position_list)
            # 選手iが試合できるか見る
            if i in done_player_list:
                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 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 += (opponent_idx, 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 = tuple()
        current_day += 1

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

Submission status: Time Limit Exceeded

Solution code:
#
import sys

def input(): return sys.stdin.readline().strip()

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

    while True:
        match = set()
        for i in range(n):
            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:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    MAX_PAIR_CNT = N*(N-1)//2
    lst = [list(map(int, input().split())) for _ in range(N)]

    days = 0
    pair_cnt = 0
    while(True):
        check_list = [True]*N
        days += 1
        for i in range(N):
            if not check_list[i]: continue
            if len(lst[i]) == 0: continue
            other_idx = lst[i][0]-1
            if not check_list[other_idx]: continue

            if lst[other_idx][0] == i+1:
                lst[i] = lst[i][1:]
                lst[other_idx] = lst[other_idx][1:]
                check_list[i] = False
                check_list[other_idx] = False
        # ペアを作れなければ-1を返す
        if all(check_list):
            print(-1)
            exit()
        else:
            pair_cnt += check_list.count(False) // 2
            if pair_cnt == MAX_PAIR_CNT:
                print(days)
                exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        if len(j) > 0:
            new = tuple(sorted([i, j[0]]))
            cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


match2rank = dict()
ij2num = dict()
i2queue = [[]]
for i in range(n):
  i2queue.append(list())
  for num in map(int, input().split()):
    i2queue[i].append(num - 1)


cnt = 0
while True:
  used = set()
  for i, q1 in enumerate(i2queue):
    if not q1: continue
    n1 = q1[0]
    n2 = i2queue[n1][0]

    if (n2 == i) and n1 not in used and n2 not in used:
      used.update([q1.pop(0), i2queue[n1].pop(0)])
  if not used:
    break
  cnt += 1

for q in i2queue:
  if q:
    print(-1)
    break
else:
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
for j in range(N*(N-1)//2):
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())

AA = [deque(list(map(int, input().split()))) for _ in range(N)]
# print(AA)
next_play = []
today_plan = [0] * N

next_play = [AA[i][0] for i in range(N)]


ans = 0
while True:
    for i in range(N):
        if today_plan[i] == -1:
            continue
        if next_play[next_play[i] - 1] == -1 or next_play[i] == -1:
            continue
        aite = next_play[i]

        if (i+1) == next_play[aite-1] and today_plan[aite-1] != -1:
            today_plan[i], today_plan[aite-1] = -1, -1
            AA[i].popleft()
            AA[aite - 1].popleft()

            if len(AA[i]) != 0:
                next_play[i] = AA[i][0]
            else:
                next_play[i] = -1
            if len(AA[aite - 1]) != 0:
                next_play[aite - 1] = AA[aite - 1][0]
            else:
                next_play[aite - 1] = -1

    if sum(today_plan) == 0:
        print(-1)
        exit()
    else:
        today_plan = [0] * N
    ans += 1
    if next_play == [-1] * N:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3): 
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if i<ai_next and amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append( [ int(n) for n in input().split() ] )

empty = [ [] for i in range(N) ]
day = 0
while(True):
    day += 1
    v = list(range(N))
    for p in range(N):
        if (not p in v) or len(A[p]) == 0:
            continue
        q = A[p][0]-1
        if p in v  and  q in v  and  A[q][0]-1 == p:
            v.remove(p)
            v.remove(q)
            del A[p][0]
            del A[q][0]
        
    if A == empty:
        print(day)
        break
        
    if len(v) == N:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(sys.stdin.readline().rstrip())
AList=[]
doneList=[False]*N
for i in range(N):
  AListTmp=list(map(int,sys.stdin.readline().split()))
  AList.append(AListTmp[::-1])

gameDays=0
maxGame=(N*(N-1))//2
gameCount=0
while(True):
  gameDays+=1
  doneList=[False]*N
  minimumDone=False
  for i in range(N):
    if doneList[i]==False:
      # player1
      player1=i
      if len(AList[player1]) == 0:
        continue
      # player2
      player2=AList[i][-1]-1
      if len(AList[player2]) == 0:
        print(-1)
        exit()
      if AList[player2][-1]-1 == player1 and doneList[player2] == False:
        doneList[player1]=True
        doneList[player2]=True
        AList[player1].pop()
        AList[player2].pop()
        gameCount +=1
        minimumDone=True
        #print("{} day, {} {}".format(gameDays,player1,player2))
  if minimumDone==False:
    print(-1)
    exit()
  if gameCount >= maxGame:
    break
    
print(gameDays)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
As = [[]]
for i in range(N):
    As.append(list(map(int, input().split())))

Cs = [0] * (N + 1)
Ks = [False] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
tab = set()
while sw:
    c = 0
    wa = []
    for i in range(1, N + 1):
        if Ks[i]:
            continue
        if Cs[i] == N - 1:
            continue
        a = 0
        b = 0
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                print(d)
                break
            Cs[a] += 1
            Cs[b] += 1
            # tab.remove((a, b))
            wa.append(a)
            wa.append(b)
        else:
            tab.add((a, b))
            Ks[i] = True
    for i in wa:
        Ks[i] = False
    d += 1
    if c == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

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

def main():
	n = int(input().strip())
	dqlist = [deque([-1])]
	for _ in range(n):
		v = list(map(int, input().strip().split()))
		dqlist.append(deque(v))
	day = 0
	while True:
		picked = [0] * (n+1)
		changed = False
		for i in range(1, n+1):
			if picked[i] == 1:
				continue
			if len(dqlist[i]) == 0:
				continue
			if dqlist[dqlist[i][0]][0] == i:
				if picked[dqlist[i][0]] == 1:
					continue
				# OK
				changed = True
				c = dqlist[i].popleft()
				dqlist[c].popleft()
				picked[i] = 1
				picked[c] = 1
		if changed == False:
			finFlag = True
			for i in range(1, n+1):
				if len(dqlist[i]) > 0:
					finFlag = False
			if finFlag:
				print(day)
				return
			else:
				print(-1)
				return
		day += 1

if __name__ == '__main__':
	main()

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)]
  c = [0]*n
  d = 0
  m = list(range(n))
  
  while m:
    candidate = set()
    for i in m:
      if i in candidate:
        continue
      j = a[i][c[i]]-1
      if a[j][c[j]]-1 == i:
        candidate.add(i)
        candidate.add(j)

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


if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

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


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

day = 0
ok = 1
count = (N * (N - 1)) // 2
can = 1
while True:
    if not ok:
        day = -1
        print('ok')
        break
    if count == 0:
        break
    if can == 0:
        day = -1
        break
    played = [0] * (N + 1)
    k = 1
    k_seen = 1
    end_day = 0
    can = 0
    while True:
        if len(op[k]) > 0:
            opponent = op[k][0]
            if len(op[opponent]) > 0:
                if op[opponent][0] == k:
                    if played[k] == 0 and played[opponent] == 0:
                        count -= 1
                        can = 1
                        op[k].popleft()
                        op[opponent].popleft()
                    played[k] = 1
                    played[opponent] = 1
                    k_seen += 1
                    k = k_seen
                    while played[k] == 1:
                        k += 1
                        if k >= N:
                            day += 1
                            end_day = 1
                            break
                else:
                    played[k] = 1
                    if played[opponent] == 0:
                        k = opponent
                    else:
                        k_seen += 1
                        k = k_seen
                        while played[k] == 1:
                            k += 1
                            if k >= N:
                                day += 1
                                end_day = 1
                                break
            else:
                ok = 0
                break
        else:
            played[k] = 1
            k_seen += 1
            k = k_seen
            while played[k] == 1:
                k += 1
                if k >= N:
                    day += 1
                    end_day = 1
                    break
        if end_day == 1:
            break

print(day)