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:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)
ans = 0

first = a_list[:, 0]
target = n_index[first[first] == n_index].tolist()
a_index[target] += 1
for i in range(N * (N-1) // 2):
    next_target = []
    for t in target:
        if t in next_target:
            continue
        cand = a_list[t, a_index[t]]
        if a_list[cand, a_index[cand]] == t:
            next_target.append(t)
            next_target.append(cand)

    target = next_target.copy()
    a_index[target] += 1
    ans += 1
    if len(target) == 0:
        break

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

n = int(input())
game = [0]

for _ in range(n):
    comp = list(map(int, input().split()))[::-1]
    game.append(comp)

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

        you = game[me][-1]
        if you in finish or game[you] == []:
            continue
        else:
            if game[you][-1] == me:
                finish.add(game[you].pop())
                finish.add(game[me].pop())
                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:
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 reversed(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:
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            if L[miru-1][dp[miru-1]][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  if cnt >= 350000:
      dp = [n-1]*n
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys

n= int(sys.stdin.readline())
a= [ None for _ in range(n) ]
for i in range(n):
    a[i]= [ int(x)-1 for x in sys.stdin.readline().split() ]
#
tot= (n*(n-1))//2
now= 0
c= 0
idx= [ 0 for _ in range(n) ]
for _ in range(tot):
    lst= []
    for i in range(n):
        if i in lst: continue
        if idx[i]==n-1: continue
        j = a[i][idx[i]]
        aj = a[j]
        if aj[idx[j]]==i: lst+= [i,j]
    #
    nn= len(lst)//2
    if nn==0: break
    for i in lst: idx[i]+=1
    #
    c+= 1
    now+= nn
    if now==tot: break
#
if now==tot: print( c )
else: print( -1 )

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []

for _ in range(N):
  a = list(map(int, input().split()))
  A.append([x - 1 for x in a])

ans = 0
cnt = 0 #消化した試合数
M = N * (N - 1) // 2 #最大試合数
while cnt < M:
  tmp = cnt
  q = [i for i in range(N)] #今日の対戦可能者
  while len(q) > 0:
    p = q.pop(0)
    if len(A[p]) == 0:
      continue

    #消化可能な試合があれば, cnt+=1, qから対戦する選手を消去, Aからも該当試合を消去 
    if A[A[p][0]][0] == p and A[p][0] in q:
      q.remove(A[p][0])
      A[A[p][0]].pop(0)
      A[p].pop(0)
      cnt += 1
  if tmp == cnt: #1試合も進まない日があった場合、不可能
    ans = -1
    break
  else:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    input = sys.stdin.readline
    N = int(input())
    A = []

    def intm1(a):
        return int(a) - 1

    A = [list(map(intm1, input().split())) for _ in range(N)]

    B = [0] * N

    nokori = N*(N-1)
    day = 0

    while nokori > 0:
        day += 1
        ng = [False] * N
        upd = False
        for i in range(N):
            if ng[i] or B[i] == N-1:
                continue
            j = A[i][B[i]]
            if B[j] < N-1 and A[j][B[j]] == i and not ng[j]:
                ng[A[i][B[i]]] = True
                ng[A[j][B[j]]] = True
                B[i] += 1
                B[j] += 1
                upd = True
                nokori -= 2
        if not upd:
            break

    print(day if nokori == 0 else -1)

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()
        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:
            if current_position_list[i] == N-1:
                # この選手はすべての試合を終了している
                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:
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
  limit=500000
  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>limit:
      return -1


  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

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

def f():
    IDX = [0] * N
    day = 0
    end = 0
    while 1:
        NEXT_IDX = IDX[:]
        flag = True
        for player, i in enumerate(IDX):
            #print(player, i)
            if i > N-2:
                continue
            #print(player, i)
            enemy = A[player][i]

            if  A[enemy-1][IDX[enemy-1]] == player+1:
                NEXT_IDX[player] += 1
                flag = False
                #print(player, NEXT_IDX)
                if NEXT_IDX[player] == N-1:
                    end += 1
        if flag:
            #print(end, NEXT_IDX)
            return(-1)
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX[:]
print(f())

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.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:
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
        while True:
            f = True
            for a in A:
                if len(a) > 0:
                    f = False
            if f:
                break

            for i in range(N):
                if len(A[i]) == 0:
                    continue
                if i + 1 not in already_p and A[i][0] not in already_p and A[A[i][0] - 1][0] == i + 1:
                    already_p.add(i + 1)
                    already_p.add(A[i][0])
                    A[A[i][0] - 1] = A[A[i][0] - 1][1:]
                    A[i] = A[i][1:]
            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:
from collections import deque
N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = deque(a[:])
count = 0
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  for k in dic.keys():
    k = int(k)
    if dic[k]==deque([]):
      nokori += 1
      continue
    p2 = dic[k][0]
#    print(k,p2)
    if log[p2-1]==1:
      continue
    if dic[p2]==deque([]):
      print(-1)
      break
    if dic[p2][0]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].popleft()
      b = dic[p2].popleft()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
      
  if nokori == N:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

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

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = [0 for i in range(n)]
#F = [[0 for i in range(n)] for j in range(2*n*n)]

n1n = n*(n-1)

d = 0
for ii in range(n*n*2):
    F = [0 for i in range(n)]
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        if F[i] == 0 and S[i] <= n-2:
            aite = A[i][S[i]]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
        if co == n-1:
            break
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

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


def get_num(i):
    return A[i][P[i]] - 1


def update(mem, K):
    for i in mem:
        P[i] += 1
        if P[i] == N - 1:
            K.remove(i)


def f():
    K = {i for i in range(N)}
    mem = set()
    for t in range(N * (N - 1) // 2 + 1):
        if len(K) == 0:
            return t

        for i in K:
            if i in mem:
                continue

            j = get_num(i)
            if j in mem:
                continue

            if i == get_num(j):
                mem.add(i)
                mem.add(j)

        if len(mem) == 0:
            return -1

        update(mem, K)
        mem = set()

    return -2

print(f())

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import copy
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
while count != fin:
    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
    ans += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    import sys
    N = int(input())
    A = []
    for i in range(N):
        row = list(map(int, sys.stdin.readline().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:
import pprint

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

day = 0

while True:
    end = 1
    game = list()
    for i in range(n):
        if a[i] != []:
            end = 0
            if a[a[i][0]-1] != []:
                if a[a[i][0]-1][0]-1 == i:
                    game.append(i)
    if end == 0:
        if game == []:
            print(-1)
            exit()
        else:
            for i in game:
                a[i].pop(0)
    else:
        print(day)
        exit()
    day += 1

Submission status: Time Limit Exceeded

Solution code:
n  = int(input())
xs = []
ys = [0] * n
fs = [False] * n
r  = n * (n - 1) // 2
c  = 0
for _ in range(0, n):
	ts = [int(x) for x in input().split()]
	for i in range(0, n - 1):
		ts[i] -= 1
	xs.append(ts)
while 0 < r:
	fn = 0
	for i in range(0, n):
		if ys[i] < n - 1:
			a     = xs[i][ys[i]]
			fs[i] = (xs[a][ys[a]] == i)
	for i in range(0, n):
		if fs[i] == True:
			fn    += 1
			ys[i] += 1
		fs[i] = False
	if fn == 0:
		c = -1
		break
	else:
		r -= fn // 2
		c += 1
print(c)

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
for a in AA:
    next_play.append(a[0])


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

        if (i+1) == next_play[next_play[i]-1] and today_plan[aite-1] != -1:
            today_plan[i], today_plan[next_play[i]-1] = -1, -1
            AA[i].popleft()
            AA[next_play[i] - 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:
n = int(input())

s = {}
fight = n * (n-1)

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


ans = 1
count = 0
s_pos = [0 for i in range(n)]

while True:
  do_Flag = []
  flag = False
  pops = []
  for index, x in s.items():
    if s_pos[index] >= n-1:
      pops.append(index)
      continue
    a = x[s_pos[index]] - 1
    b = s[a][s_pos[a]] - 1
    if b == index:
      count += 1
      do_Flag.append(index)
      flag = True
    
  for j in pops:
    s.pop(j)
  
  for i in do_Flag:
    s_pos[i] += 1
  
  if flag:
    if count >= fight:
      print(ans)
      break
    ans += 1
  else:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import deque


def solve(N, A):
    day = 0
    total = (N * (N-1)) // 2
    players = set(range(N))
    while True:
        day += 1
        update = False
        today = set()
        loop_in_day = True
        while loop_in_day:
            loop_in_day = False
            for i in players.copy():
                if i in today:
                    continue
                if not A[i]:
                    players.remove(i)
                    continue
                opp = A[i][0] - 1
                if opp in today:
                    continue
                if A[opp][0] - 1 == i:
                    A[i].popleft()
                    A[opp].popleft()
                    today.add(i)
                    today.add(opp)
                    total -= 1
                    update = True
                    loop_in_day = True
                    if total == 0:
                        return day
        if not update:
            return -1


if __name__ == '__main__':
    N = int(input())
    A = []
    for _ in range(N):
        A.append(deque(map(int, input().split())))

    ans = solve(N, A)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
A = []

def intm1(a):
    return int(a) - 1

A = [list(map(intm1, input().split())) for _ in range(N)]

B = [0] * N

nokori = N*(N-1)
day = 0

while nokori > 0:
    day += 1
    ng = [False] * N
    upd = False
    for i in range(N):
        if ng[i] or B[i] == N-1:
            continue
        j = A[i][B[i]]
        if B[j] < N-1 and A[j][B[j]] == i and not ng[j]:
            ng[A[i][B[i]]] = True
            ng[A[j][B[j]]] = True
            B[i] += 1
            B[j] += 1
            upd = True
            nokori -= 2
    if not upd:
        break

print(day if nokori == 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = []
isAble = True
for i in range(N):
    A = list(map(int, input().split()))
    As.append(A)
pos = [0]*N
final = [N-1]*N
s = []
days = 0
isAble = True
while pos != final:
    days += 1
    s = []
    for i in range(N):
        if pos[i] != N-1:
            if i in s:
                pos[i] += 1
            else:
                b = As[i][pos[i]]-1
                if i == As[b][pos[b]]-1 and b not in s:
                    s.append(i)
                    s.append(b)
                    pos[i] += 1
    if len(s) == 0:
        isAble = False
        break
if isAble:
    print(days)
else:
    print(-1)

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
  limit=n*(n-1)//2
  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>limit:
      return -1


  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input()) # 数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

tmp_list = copy.deepcopy(List)
day = 0
flag = 1

while tmp_list != [[]]*N:
    done = [0]*N
    day += 1
    flag = 0
    
    for i in range(N-1):
        if done[i] == 0 and len(tmp_list[i]) != 0:
            next = tmp_list[i][0]-1
            if tmp_list[next][0] == i+1 and done[next] == 0:
                done[i] = 1
                done[next] = 1
                del tmp_list[i][0]
                del tmp_list[next][0]
                flag = 1
    if flag == 0:
        break

if flag == 0:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
items = []
from collections import deque

for i in range(N):
    items.append(deque(map(int, input().split())))

ans = 0
from collections import defaultdict

while True:
    used = set()
    flag = False
    all_done = True
    for j in range(N):
        if j + 1 in used:
            continue
        if len(items[j]) >= 1:
            t = items[j][0]
            if t not in used and len(items[t - 1]) >= 1 and j + 1 == items[t - 1][0]:
                used.add(j + 1)
                used.add(t)
                items[j].popleft()
                items[t - 1].popleft()
                flag = True
        if len(items[j]) != 0:
            all_done = False

    # for i in range(N):
    #     if len(items[i]) != 0:
    #         all_done = False
    if flag:
        ans += 1
        if all_done:
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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:
            if i+1>=alist[i][nowlist[i]]:
                small=[i+1, alist[i][nowlist[i]]]
            else:
                small=[alist[i][nowlist[i]], i+1]
            heapq.heappush(koho, small)
    koho=sorted(koho)
    swit=0
    before=[]
    while koho!=[]:
        now=heapq.heappop(koho)
        if now==before:
            nowlist[now[0]-1]+=1
            nowlist[now[1]-1]+=1
            incre+=2
            swit=1
        before=now
    day+=1
    if swit==0:
        day=-1
        error=1
 
print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


class Searchable_BIT():
    def __init__(self,N):
        self.N = N
        self.node = [0]*(self.N+1)
        self.cnt = 0

    def add(self,a): # 要素 x を追加
        x = a
        self.cnt += 1
        while x <= self.N:
            self.node[x] += 1
            x += x & -x

    def delete(self,x): # 要素 x を削除
        self.cnt -= 1
        while x <= self.N:
            self.node[x] -= 1
            x += x & -x

    def count(self,x): # x以下の要素数
        tmp = 0
        while x > 0:
            tmp += self.node[x]
            x -= x & -x
        return tmp

    def get_maxval(self):
        return self.get_lower_i(self.cnt)

    def get_lower_i(self,i): # i 番目に小さい要素を取得
        NG = -1
        OK = self.N
        while OK-NG > 1:
            mid = (OK+NG)//2
            #print(OK,NG,self.count(mid))
            if self.count(mid) >= i:
                OK = mid
            else:
                NG = mid
        return OK


def calc(x,y):
    return x*(N-1) + y

N = inp()
AA = [inpl() for _ in range(N)]

itrs = [0]*N

ans = 0
cnt = 0

while True:
    next = set()
    for x,itr in enumerate(itrs):
        if itr < N-1:
            t = AA[x][itr] - 1
            if AA[t][itrs[t]]-1 == x:
                next.add(x)

    for n in next:
        itrs[n] += 1
        if itrs[n] == N-1:
            cnt += 1

    ans += 1

    if cnt == N:
        print(ans)
        exit()

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

Submission status: Time Limit Exceeded

Solution code:
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 = True
                game_flag[i] = True
                game_flag[j] = True
                A[i].pop()
                A[j].pop()
    ans += 1
    if A == empty:
        break
    elif flag == False:
        ans = -1
        break

print(ans)