Problem:


Score : 500 points

Problem Statement

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

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

Each player plays at most one matches in a day.

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

Constraints

3 \leq N \leq 1000

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

A_{i, j} \neq i

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

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

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

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

Sample Output 2

4

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

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

Day 2: Player 1 vs Player 3

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

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


n=int(input())
r={}
for i in range(n):
  temp=deque(list(map(int,input().split())))
  r[i+1]=temp
#print(r)

count=0


temp=set([int(i) for i in range(1,n+1) ])
mugen=int(1000*1000/2)
for k in range(0,mugen):
  flag=0
  temp2=set([])
  for i in temp:
    if r[i]!=deque([]) and i not in temp2:
      no=r[i][0]
      if r[no][0]==i  and no not in temp2:
        flag=1
        temp2.add(i)
        temp2.add(no)
        r[no].popleft()
        r[i].popleft()      
    i+=1
  temp=temp2
  #print(temp2)
  if flag==1:
    count+=1
    #print("######",count,temp,r)
  exit1=0
  hoge=r.values()
  for item in hoge:
    if item != deque([]):
      exit1=1
      
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


n=int(input())
r={}
for i in range(n):
  temp=deque(list(map(int,input().split())))
  r[i+1]=temp
#print(r)

count=0


temp=set([int(i) for i in range(1,n+1) ])
while 1:
  flag=0
  temp2=set([])
  for i in temp:
    if r[i]!=deque([]) and i not in temp2:
      no=r[i][0]
      if r[no][0]==i  and no not in temp2:
        flag=1
        temp2.add(i)
        temp2.add(no)
        r[no].popleft()
        r[i].popleft()      
    i+=1
  temp=temp2
  #print(temp2)
  if flag==1:
    count+=1
    #print("######",count,temp,r)
  exit1=0
  hoge=r.values()
  for item in hoge:
    if item != deque([]):
      exit1=1
      
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

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

        #print(match,dp[match])
        caluculated.add(match)
        return dp[match]

    ans = 0
    for match in matches:
        #print("\n",match)
        res = dfs(match)
        #print(res)
        ans = max(ans,res)
    print(ans)




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

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

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

    print(day)"""

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


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


n=int(input())
r={}
for i in range(n):
  temp=deque(list(map(int,input().split())))
  r[i+1]=temp
#print(r)

count=0


temp=set([int(i) for i in range(1,n+1) ])
while 1:
  flag=0
  temp2=set([])
  for i in temp:
    if r[i]!=deque([]) and i not in temp2:
      no=r[i][0]
      if r[no][0]==i  and no not in temp2:
        flag=1
        temp2.add(i)
        temp2.add(no)
        r[no].popleft()
        r[i].popleft()      
    i+=1
  temp=temp2
  #print(temp2)
  if flag==1:
    count+=1
    #print("######",count,temp,r)
  exit1=0
  for item in r.values():
    if item != deque([]):
      exit1=1
      
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
indexes = [0] * (N+1)
matches = [[0] * (N-1)] + [list(map(int, input().split())) for _ in range(N)]
cnt = 0
while True:
  play = False
  playing = {}
  check_cnt = 0
  for idx, match in enumerate(matches):
    if idx == 0:
      continue
    else:
      if indexes[idx] == N-1:
        check_cnt += 1
        continue
      opponent = match[indexes[idx]]
      if idx == matches[opponent][indexes[opponent]] and not idx in playing and not opponent in playing:
        play = True
        indexes[idx] += 1
        indexes[opponent] += 1
        playing[idx] = 1
        playing[opponent] = 1
  if play:
    cnt += 1
  else:
    if check_cnt == N:
      print(cnt)
      break
    else:
      print(-1)
      break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N = int(input())
    A = [None] + [deque(map(int, input().split())) for i in range(N)]
    
    ans = 0
    finish = False
    base_used = {i for i in range(1, N+1)}
        
    while not finish and base_used:
        finish = True
        ans += 1
        used = set()
        delete_used = set()
        
        for n in base_used:
            if n in delete_used:
                continue
            
            a = A[n][0]
            if not a in used and not n in used and A[a][0] == n:
                for x in [n, a]:
                    used.add(x)
                    A[x].popleft()
    
                    if not A[x]:
                        delete_used.add(x)
                finish = False     
        base_used -= delete_used
        
    if base_used:
        ans = -1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


n=int(input())
r={}
for i in range(n):
  temp=deque(list(map(int,input().split())))
  r[i+1]=temp
#print(r)

count=0

while 1:
  i=1
  flag=0
  temp=set([])
  while i<n+1:
    if r[i]!=deque([]) and i not in temp:
      no=r[i][0]
      if r[no][0]==i  and no not in temp:
        flag=1
        temp.add(i)
        temp.add(no)
        r[no].popleft()
        r[i].popleft()      
    i+=1
  if flag==1:
    count+=1
    #print("######",count,temp,r)
  exit1=0
  for item in r.values():
    if item != deque([]):
      exit1=1
      
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if m in player_in_this_game or teki_idx in player_in_this_game:
        #自分または相手に既に試合が組まれている
        pass
      elif a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
for _ in r5000:
  rn = range(n)
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if m in player_in_this_game or teki_idx in player_in_this_game:
        #自分または相手に既に試合が組まれている
        pass
      elif a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
for _ in r5000:
  rn = range(n)
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if m in player_in_this_game or teki - 1 in player_in_this_game:
        #自分または相手に既に試合が組まれている
        pass
      elif a[teki - 1][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki - 1].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki - 1) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()

Submission status: Time Limit Exceeded

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


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

        if v not in edge:
            edge[v] = []
        edge[v].append(u)

        if u not in redge:
            redge[u] = 0
        redge[u] += 1

s2 = set()
for k in s:
    if k not in redge:
        s2.add(k)
s = s2

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

for v in redge:
    print(-1)
    exit()
print(res)

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
for _ in r5000:
  player_in_this_game = set()
  rn = range(n)
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if m in player_in_this_game or teki - 1 in player_in_this_game:
        #自分または相手に既に試合が組まれている
        pass
      elif a[teki - 1][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki - 1].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki - 1) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
# match of  a vs b
def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

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

# NEXT[ match(a,b) ]  must be held after  match(a,b)
NEXT = [ [] for i in range(N*N) ]
# How many matches must be held before  match(a,b)
before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        # i vs A[i][j+1]  must be held after  i vs A[i][j]
        NEXT[ match(i,A[i][j]) ].append( match(i,A[i][j+1]) )
        before[ match(i,A[i][j+1]) ] += 1
        
q  = []
q0 = []

for i in range(N):
    for j in range(i+1,N):
        if before[ match(i,j) ] == 0:
            q.append( match(i,j) )
            
day = 0

while True:
    day += 1
    for M in q:
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.append(m)
        NEXT[M] = []
    q = q0
    q0 = []
    #print(NEXT)
    #print(before)
    if q == []:
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import queue

# match of  a vs b
def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

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

# NEXT[ match(a,b) ]  must be held after  match(a,b)
NEXT = [ [] for i in range(N*N) ]
# How many matches must be held before  match(a,b)
before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        # i vs A[i][j+1]  must be held after  i vs A[i][j]
        NEXT[ match(i,A[i][j]) ].append( match(i,A[i][j+1]) )
        before[ match(i,A[i][j+1]) ] += 1
        
q  = queue.Queue()
q0 = queue.Queue()

for i in range(N):
    for j in range(i+1,N):
        if before[ match(i,j) ] == 0:
            q.put( match(i,j) )
            
day = 0

while True:
    day += 1
    while not q.empty():
        M = q.get()
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.put(m)
        NEXT[M] = []
    q = q0
    q0 = queue.Queue()
    #print(NEXT)
    #print(before)
    if q.empty():
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

match=[0]*(n+1)

while True:
  day+=1
  check=[True]*n
  for i in range(n):
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=False
        check[vs]=False
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import queue

# match of  a vs b
def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

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

# NEXT[ match(a,b) ]  must be held after  match(a,b)
NEXT = [ [] for i in range(N*N) ]
# How many matches must be held before  match(a,b)
before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        # i vs A[i][j+1]  must be held after  i vs A[i][j]
        NEXT[ match(i,A[i][j]) ].append(match(i,A[i][j+1]))
        before[match(i,A[i][j+1])] += 1
        
q  = queue.Queue()
q0 = queue.Queue()

for i in range(N):
    for j in range(i+1,N):
        if before[match(i,j)] == 0:
            q.put(match(i,j))
            
day = 0

while True:
    day += 1
    while not q.empty():
        M = q.get()
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.put(m)
        NEXT[M] = []
    while not q0.empty():
        M = q0.get()
        q.put(M)
    #print(NEXT)
    #print(before)
    if q.empty():
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

day=0

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  b=list(map(int,input().split()))
  a.append(list(reversed(b)))
day=0
 
match=[0]*(n+1)
jyunban=[i for i in range(n)]
jyunban_n=[]
 
while match[n]<maxmatch:
  jyunban_n.clear()
  day+=1
  check=[True]*(n+1)
  for i in jyunban:
    if match[i]==n-1 or check[i]==False:
      continue
    else:
      vs=a[i][-1]-1
      if check[i] and check[vs]:
        if a[vs][-1]-1==i:
          a[i].pop(-1)
          a[vs].pop(-1)
          match[i]+=1
          match[vs]+=1
          match[n]+=2
          check[i]=False
          check[vs]=False
          check[n]=False
          jyunban_n.append(i)
          jyunban_n.append(vs)
      
    if i==jyunban[-1] and check[n]:
      print(-1)
      sys.exit()
  jyunban=jyunban_n[:]
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  b=list(map(int,input().split()))
  a.append(list(reversed(b)))
day=0
 
match=[0]*(n+1)
jyunban=[i for i in range(n)]
jyunban_n=[]
 
while match[n]<maxmatch:
  jyunban_n.clear()
  day+=1
  check=[True]*(n+1)
  for i in jyunban:
    if match[i]==n-1 or check[i]==False:
      continue
    else:
      vs=a[i][-1]-1
      if check[i] and check[vs]:
        if  a[i][-1]-1==vs and a[vs][-1]-1==i:
          a[i].pop(-1)
          a[vs].pop(-1)
          match[i]+=1
          match[vs]+=1
          match[n]+=2
          check[i]=False
          check[vs]=False
          check[n]=False
          jyunban_n.append(i)
          jyunban_n.append(vs)
      
    if i==jyunban[-1] and check[n]:
      print(-1)
      sys.exit()
  jyunban=jyunban_n[:]
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
def return_if_the_all_the_elements_are_n(lst):
    for i in range(1,n):
        if lst[0]=="n" and lst[0]==lst[i]:pass
        else:return 0
    return 1
    
def return_soushisouai(A,n):
    desired_opponets=[]
    for i in range(n):
        if len(A[i])!=0:desired_opponets.append(A[i][0])
        else:desired_opponets.append("n")
        
    for i in range(len(desired_opponets)):
        for j in range(len(desired_opponets)-i):
            if desired_opponets[i]=="o":
                break
            
            if desired_opponets[i]==i+j+1 and desired_opponets[i+j]==i+1:
                desired_opponets[i]="o"
                desired_opponets[i+j]="o"
                break
            
            else:pass
    if "o" not in desired_opponets:
        if return_if_the_all_the_elements_are_n(desired_opponets):return"end"
        else:return "no match"
    else:return desired_opponets
    
n = int(input())
A=[]
for i in range(n):
    A.append(list(map(int,input().split())))
  
  
day=0
while(True):
    match = return_soushisouai(A,n)
    #print(A,match)
    if match=="no match":
        print(-1)
        sys.exit()
    elif match=="end":break
    else:
        day+=1
        for i in range(n):
            if match[i]=="o":del A[i][0]
print(day)

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
for ii in r5000:
  player_in_this_game = set()
  rn = range(n)
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if m in player_in_this_game or teki - 1 in player_in_this_game:
        #自分または相手に既に試合が組まれている
        pass
      elif a[teki - 1][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki - 1].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki - 1) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
for ii in r5000:
  player_in_this_game = set()
  rn = range(n)
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun:
        if m in player_in_this_game or teki - 1 in player_in_this_game:
          #自分または相手に既に試合が組まれている
          pass
        else: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
          a[m].popleft() #自分の予定を消す
          a[teki - 1].popleft() #相手の予定を消す
          player_in_this_game.add(m) #自分を試合中にする
          player_in_this_game.add(teki - 1) #相手を試合中にする
          nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
for ii in range(5000):
  player_in_this_game = set()
 
  for m in range(n): #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun:
        if m in player_in_this_game or teki - 1 in player_in_this_game:
          #自分または相手に既に試合が組まれている
          pass
        else: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
          a[m].popleft() #自分の予定を消す
          a[teki - 1].popleft() #相手の予定を消す
          player_in_this_game.add(m) #自分を試合中にする
          player_in_this_game.add(teki - 1) #相手を試合中にする
          nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

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

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

day = 1
for ii in range(3500):
  player_in_this_game = set()
  nokori_games = 0
  
  for m in range(n): #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    nokori_games += la #自分の残り試合予定数を足す
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun:
        if m in player_in_this_game or teki - 1 in player_in_this_game:
          #自分または相手に既に試合が組まれている
          pass
        else: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
          a[m].popleft() #自分の予定を消す
          a[teki - 1].popleft() #相手の予定を消す
          player_in_this_game.add(m) #自分を試合中にする
          player_in_this_game.add(teki - 1) #相手を試合中にする
          nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1