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:
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 m in player_in_this_game: #既に試合が組まれている
      pass
    elif la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun:
        if 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

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

canUse = set(range(N))

ans = 0
while any([len(i) > 0 for i in A]):
    # print("\nDay", ans)
    ans += 1
    canUseNew = set()
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            A[first].pop()
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print(-1)
        sys.exit(0)
    canUse = canUseNew

print(ans)

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): #選手ごとに判定
    la = len(a[m])
    nokori_games += la #自分の残り試合予定数を足す
    if m in player_in_this_game:
      pass
    elif la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun and teki - 1 not in player_in_this_game: 
      #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        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
print(-1)
sys.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)]

f = True
day = 1
while(f):
  if day > 4000:
    print(-1)
    sys.exit()
  done = set()
  nokori_games = 0
  
  for m in range(n):
    la = len(a[m])
    nokori_games += la
    if m in done:
      pass
    elif la:
      teki = a[m][0]
      jibun = m + 1
      if a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
      elif not len(a[teki - 1]):
        print(-1)
        sys.exit()
  if nokori_games:
    if not len(done):
      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)]

f = True
day = 1
while(f):
  if day > 10000:
    print(-1)
    sys.exit()
  done = set()
  nokori_games = 0
  
  for m in range(n):
    la = len(a[m])
    nokori_games += la
    if m in done:
      pass
    elif la:
      teki = a[m][0]
      jibun = m + 1
      if a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
      elif not len(a[teki - 1]):
        print(-1)
        sys.exit()
  if nokori_games:
    if not len(done):
      print(-1)
      sys.exit()
  else:
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
t = [0] * N
ans = 0
e = [False] * N
v = [True] * N
while any(v):
    v = [False] * N
    for i in range(N):
        if e[i] is True or v[i] is True:
            continue
        j = A[i][t[i]]
        if e[j] is True or v[j] is True:
            continue
        if A[j][t[j]] == i:
            t[i] += 1
            t[j] += 1
            v[i] = True
            v[j] = True
            if t[i] == N - 1:
                e[i] = True
            if t[j] == N - 1:
                e[j] = True
    ans += 1
if not all(e):
    print(-1)
else:
    print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
r={}
for i in range(n):
  temp=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]!=[] 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].pop(0)
        r[i].pop(0)
        #print(r)      
    i+=1
  if flag==1:
    count+=1
    #print("######",count,temp)
  exit1=0
  for item in r.values():
    if item != []:
      exit1=1
      
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
t = [0] * N
ans = 0
e = [False] * N
v = [True] * N
while not all(e) and any(v):
    v = [False] * N
    for i in range(N):
        if v[i] is True:
            continue
        if t[i] > N - 2:
            continue
        j = A[i][t[i]]
        if v[j] is True:
            continue
        if t[j] > N - 2:
            continue
        if A[j][t[j]] == i:
            t[i] += 1
            t[j] += 1
            v[i] = True
            v[j] = True
            if t[i] == N - 1:
                e[i] = True
            if t[j] == N - 1:
                e[j] = True
    ans += 1
if not all(e):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
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]:
      if check[n]:
        print(-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

taisen = list(itertools.combinations(range(n), 2))
taisen_dic = {}
for i in range(len(taisen)):
    taisen_dic[taisen[i]] = i

B = [[0] * (n-1) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        key0, key1 = min(i, A[i][j]), max(i, A[i][j])
        B[i][j] = taisen_dic[(key0, key1)]

#print(B)

nn = len(taisen)

G = [[] for i in range(nn)]



for i in range(n):
    for j in range(n-2):
        G[B[i][j]].append(B[i][j+1])

#print(G)

S = [[i, 0] for i in range(nn)]
D = [-1] * nn

dis = 0
while len(S) > 0 and dis <= nn:
    now = S.pop()
    now0 = now[0]
    dis = now[1]
    if dis > D[now0]:
        D[now0] = dis
        for i in G[now0]:
            if dis+1 > D[i]:
                S.append([i, dis+1])
                #print(S)

if dis > nn:
    print(-1)
else:
    print(max(D) + 1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

taisen = list(itertools.combinations(range(n), 2))
taisen_dic = {}
for i in range(len(taisen)):
    taisen_dic[taisen[i]] = i

B = [[0] * (n-1) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        key0, key1 = min(i, A[i][j]), max(i, A[i][j])
        B[i][j] = taisen_dic[(key0, key1)]

#print(B)

nn = len(taisen)

G = [[] for i in range(nn)]



for i in range(n):
    for j in range(n-2):
        G[B[i][j]].append(B[i][j+1])

#print(G)

S = [[i, 0] for i in range(nn)]
D = [-1] * nn

dis = 0
while len(S) > 0 and dis <= nn:
    now = S.pop()
    now0 = now[0]
    dis = now[1]
    if dis > D[now0]:
        D[now0] = dis
        for i in G[now0]:
            S.append([i, dis+1])
            #print(S)

if dis > nn:
    print(-1)
else:
    print(max(D) + 1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
r={}
for i in range(n):
  temp=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]!=[] 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].pop(0)
        r[i].pop(0)
        #print(r)      
    i+=1
  if flag==1:
    count+=1
    #print("######",count,temp)
  exit1=0
  for item in r:
    if r[item]!=[]:
      exit1=1
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
t = [0] * N
ans = 0
e = [False] * N
for _ in range((N * (N - 1)) // 2):
    v = [False] * N
    for i in range(N):
        if v[i] is True:
            continue
        if t[i] > N - 2:
            continue
        j = A[i][t[i]]
        if v[j] is True:
            continue
        if t[j] > N - 2:
            continue
        if A[j][t[j]] == i:
            t[i] += 1
            t[j] += 1
            v[i] = True
            v[j] = True
            if t[i] == N - 1:
                e[i] = True
            if t[j] == N - 1:
                e[j] = True
    ans += 1

    if all(e):
        print(ans)
        exit()

    if not any(v):
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    stamina=[1]*N
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
t = [0] * N
ans = 0
for _ in range((N * (N - 1)) // 2):
    v = [False] * N
    for i in range(N):
        if t[i] > N - 2 or v[i] is True:
            continue
        j = A[i][t[i]]
        if t[j] > N - 2 or v[j] is True:
            continue
        if A[j][t[j]] == i:
            t[i] += 1
            t[j] += 1
            v[i] = True
            v[j] = True
    ans += 1

    f = True
    for tt in t:
        if tt != N - 1:
            f = False
            break
    if f is True:
        print(ans)
        exit()

    if not any(v):
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
r={}
for i in range(n):
  temp=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]!=[] and i not in temp:
      if r[r[i][0]][0]==i  and r[i][0] not in temp:
        flag=1
        temp.add(i)
        temp.add(r[i][0])
        r[r[i][0]].pop(0)
        r[i].pop(0)
        #print(r)      
    i+=1
  if flag==1:
    count+=1
    #print("######",count,temp)
  exit1=0
  for item in r:
    if r[item]!=[]:
      exit1=1
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

taisen = list(itertools.combinations(range(n), 2))
taisen_dic = {}
for i in range(len(taisen)):
    taisen_dic[taisen[i]] = i

B = [[0] * (n-1) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        key0, key1 = min(i, A[i][j]), max(i, A[i][j])
        B[i][j] = taisen_dic[(key0, key1)]

#print(B)

nn = len(taisen)

P = [0] * nn

for k in range(nn):
    #print(P)
    for i in range(n):
        for j in range(n-2):
            P[B[i][j+1]] = max(P[B[i][j+1]], P[B[i][j]] + 1)

P_n = P[:]

for k in range(1):
    for i in range(n):
        for j in range(n-2):
            P[B[i][j+1]] = max(P[B[i][j+1]], P[B[i][j]] + 1)


if P_n != P:
    print(-1)
else:
    print(max(P) + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
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][match[i]]-1
      if check[i] and check[vs]:
        if  a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
          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]:
      if check[n]:
        print(-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
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][match[i]]-1
      if check[i] and check[vs]:
        if  a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
          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 len(jyunban)==0:
      if check[n]:
        print(-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
        
print(day)

Submission status: Time Limit Exceeded

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

match=[0]*(n+1)
jyunban=deque(range(n))
jyunban_n=deque()

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][match[i]]-1
      if check[i] and check[vs]:
        if  a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
          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 len(jyunban)==0:
      if check[n]:
        print(-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
#  print (jyunban)
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
n=0
first_fight = set([i for i in range(N)])
record = set()
first = True

while True:
    change=False
    stamina=[1]*N
    if first is True:
        pre_fight = first_fight
    else:
        pre_fight = record
        record = set()
    for g in pre_fight:
        if A[g]!=deque() and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].popleft()
                A[_pop-1].popleft()
                stamina[g]=0
                stamina[_pop-1]=0
                record.add(g)
                record.add(_pop-1)
                change=True
                n+=1
    first=False
    ans+=1
    if change is False:
        break
    if n==N*(N-1)//2:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
r={}
for i in range(n):
  temp=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]!=[] and i not in temp:
      if r[r[i][0]][0]==i  and r[i][0] not in temp:
        flag=1
        temp.add(i)
        temp.add(r[i][0])
        r[r[i][0]].remove(i)
        r[i].remove(r[i][0])
        #print(r)      
    i+=1
  if flag==1:
    count+=1
    #print("######",count,temp)
  exit1=0
  for item in r:
    if r[item]!=[]:
      exit1=1
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

Submission status: Time Limit Exceeded

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

count=0

while 1:
  i=1
  flag=0
  temp=[]
  while i<n+1:
    if r[i]!=[] and i not in temp:
      if r[r[i][0]][0]==i  and r[i][0] not in temp:
        flag=1
        temp.append(i)
        temp.append(r[i][0])
        r[r[i][0]].remove(i)
        r[i].remove(r[i][0])
        #print(r)      
    i+=1
  if flag==1:
    count+=1
    #print("######",count,temp)
  exit1=0
  for item in r:
    if r[item]!=[]:
      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

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for n in range(N)]
first_fight = set([i for i in range(N)])
record = set()

#前日に試合をした選手のみにマッチングを確認する(これで最悪O(n^2))。
#そうしないと、「while True」の部分で最悪n(n-1)/2の計算量がかかり、O(n^3)となって詰む
first = True

while True:
    change=False
    stamina=[1]*N
    if first is True:
        pre_fight = first_fight
    else:
        pre_fight = record
        record = set()
    for g in pre_fight:
        if A[g]!=deque() and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].popleft()
                A[_pop-1].popleft()
                stamina[g]=0
                stamina[_pop-1]=0
                change=True
                record.add(g)
                record.add(_pop-1)
    first=False
    ans+=1
    if change is False:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for n in range(N)]
first_fight = set([i for i in range(N)])
record = set()

#前日に試合をした選手のみマッチングを確認する(これで最悪O(n^2))。
#そうしないと、「while True」の部分で最悪n(n-1)/2の計算量がかかり、O(n^3)となって詰む
while True:
    first = True
    change=False
    stamina=[1]*N
    if first is True:
        pre_fight = first_fight
    else:
        pre_fight = record
    for g in pre_fight:
        if A[g]!=deque() and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].popleft()
                A[_pop-1].popleft()
                stamina[g]=0
                stamina[_pop-1]=0
                change=True
                record.add(g)
    first=False
    record = set()
    ans+=1
    if change is False:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import time
from collections import deque
import sys
import copy
n=int(input())
t1=time.time()
maxmatch=n*(n-1)
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

day=0

match=[0]*(n+1)
jyunban=deque(range(n))
jyunban_n=deque()

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][match[i]]-1
      if check[i] and check[vs]:
        if  a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
          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 len(jyunban)==0:
      if check[n]:
        print(day,-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
#  print (jyunban)
        
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for n in range(N)]

while True:
    change=0
    stamina=[1]*N
    for g in range(N):
        if A[g]!=deque() and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].popleft()
                A[_pop-1].popleft()
                stamina[g]=0
                stamina[_pop-1]=0
                change=1
    ans+=1
    if change==0:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for n in range(N)]

while True:
    change=0
    stamina=[1]*N
    for g in range(N):
        if A[g]!=deque() and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].popleft()#popはゴミ
                A[_pop-1].popleft()
                stamina[g]=0
                stamina[_pop-1]=0
                change+=1
    ans+=1
    if change==0:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

ans=0
empty = [[] for n in range(N)]

for i in range(N*(N-1)//2):
    change=0
    stamina=[1]*N
    for g in range(N):
        if A[g]!=[] and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].pop(0)
                A[_pop-1].pop(0)
                stamina[g]=0
                stamina[_pop-1]=0
                change+=1
    ans+=1
    if change==0:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
class DirectedGraph:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.is_asyclic = False
        self.max_path_len = None

    def topological_sort(self):
        indegree = [0] * self.n
        for i, vs in enumerate(self.adj):
            for dest in vs:
                indegree[dest] += 1
        zero_v = []
        for v, indeg in enumerate(indegree):
            if indeg == 0:
                zero_v.append(v)
        max_path_len = 1
        tp_sorted = []
        to_be_added = []
        while True:
            while zero_v:
                v = zero_v.pop()
                tp_sorted.append(v)
                for dest in self.adj[v]:
                    indegree[dest] -= 1
                    if indegree[dest] == 0:
                        to_be_added.append(dest)
            if len(to_be_added) > 0:
                zero_v += to_be_added
                to_be_added = []
                max_path_len += 1
            else:
                break
        if len(tp_sorted) == self.n:
            self.is_asyclic = True
            self.max_path_len = max_path_len
            return tp_sorted
        else:
            self.is_asyclic = False
            return None

if __name__ == "__main__":
    n = int(input())
    dic = {}
    itr = 0
    for i in range(n):
        for j in range(i+1, n):
            dic[i*n + j] = itr
            itr += 1
    edge = [[] for _ in range(n * (n-1) // 2)]
    for i in range(n):
        a = [int(item) - 1 for item in input().split()]
        for j1, j2 in zip(a, a[1:]):
            if i < j1:
                u = i * n + j1 
            else:
                u = j1 * n + i 
            if i < j2:
                v = i * n + j2 
            else:
                v = j2 * n + i 
            edge[dic[u]].append(dic[v])

    DG = DirectedGraph(edge)
    tps = DG.topological_sort()

    if DG.is_asyclic:
        print(DG.max_path_len)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

ans=0

for i in range(N*(N-1)//2):
    stamina=[1]*N
    for g in range(N):
        if A[g]!=[] and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].pop(0)
                A[_pop-1].pop(0)
                stamina[g]=0
                stamina[_pop-1]=0
    ans+=1
    if A==[[] for n in range(N)]:
        print(ans)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

n = int(input())
orders = [[x - 1 for x in list(map(int, input().split()))] for _ in range(n)]

d = defaultdict(list)
e = defaultdict(list)

for i in range(n):
	for j in range(n - 2):
		a1, a2 = min(i, orders[i][j]), max(i, orders[i][j])
		b1, b2 = min(i, orders[i][j + 1]), max(i, orders[i][j + 1])
		d[(a1, a2)].append((b1, b2))
		e[(b1, b2)].append((a1, a2))
		if j == n - 3:
			d[(b1, b2)].append((-1, -1))
			e[(-1, -1)].append((b1, b2))

visited = [[0 for _ in range(n)] for _ in range(n)]
cnt_dict = defaultdict(int)

ans = []
def visit(cur):
	a, b = cur
	if visited[a][b] == -1:
		print(-1)
		sys.exit()
	elif visited[a][b] == 0:
		visited[a][b] = -1
		if e[cur]:
			cnt = max([visit(x) for x in e[cur]])
		else:
			cnt = 0
		visited[a][b] = 1
		ans.append(cur)
		cnt_dict[cur] = max(cnt_dict[cur], cnt + 1)
		return cnt + 1
	else:
		return cnt_dict[cur]

print(visit((-1, -1)) - 1)

Submission status: Time Limit Exceeded

Solution code:
import time
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()
    now=time.time()
    if (now-start)>1.8:
        print(m)
        exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

n = int(input())
orders = [[x - 1 for x in list(map(int, input().split()))] for _ in range(n)]

d = defaultdict(list)
e = defaultdict(list)

for i in range(n):
	for j in range(n - 2):
		a1, a2 = min(i, orders[i][j]), max(i, orders[i][j])
		b1, b2 = min(i, orders[i][j + 1]), max(i, orders[i][j + 1])
		d[(a1, a2)].append((b1, b2))
		e[(b1, b2)].append((a1, a2))

visited = [[0 for _ in range(n)] for _ in range(n)]
cnt_dict = defaultdict(int)

ans = []
def visit(cur):
	a, b = cur
	if visited[a][b] == -1:
		print(-1)
		sys.exit()
	elif visited[a][b] == 0:
		visited[a][b] = -1
		if e[cur]:
			cnt = max([visit(x) for x in e[cur]])
		else:
			cnt = 0
		visited[a][b] = 1
		ans.append(cur)
		cnt_dict[cur] = max(cnt_dict[cur], cnt + 1)
		return cnt + 1
	else:
		return cnt_dict[cur]

max_cnt = 0
for i in range(n):
	for j in range(i + 1, n):
		if visited[i][j] == 0:
			max_cnt = max(visit((i, j)), max_cnt)
print(max_cnt)