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 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)

N = _I()
A_list = []
for i in range(N):
    A_list.append(LI())
#  perr(A_list)
new_A_list = []
for A in A_list:
    new_A_list.append([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_player_idx = 0
current_opponent_idx = None
current_day = 0
is_ok = False
# 各選手の試合状況
current_position_list = [0 for i in range(N)]
done_player_list = []
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):
        # 全試合終了
        break

    for i in range(N):
        #  print('--- in for---- current position list', current_position_list)
        # 選手iが試合できるか見る
        if i in done_player_list:
            continue

        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.append(opponent_idx)
            done_player_list.append(i)
            current_position_list[i] += 1
            current_position_list[opponent_idx] += 1
            # 試合がまだ可能であるというフラグをつける
            is_ok = True

    if not is_ok:
        # 1試合も成立しなかったらストップする
        print(-1)
        exit()

    done_player_list = []
    current_day += 1

print(current_day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for _ in range(n):
    a.append([int(i) - 1 for i in input().split()])

day = 0
ind = [0] * n
while True:
    day += 1
    used = [0] * n
    for i in range(n):
        if ind[i] < n-1 and ind[a[i][ind[i]]] < n-1 and not used[i] and not used[a[i][ind[i]]] and a[a[i][ind[i]]][ind[a[i][ind[i]]]] == i:
            used[i] = 1
            used[a[i][ind[i]]] = 1
            ind[a[i][ind[i]]] += 1
            ind[i] += 1
    if sum(ind) == n*(n-1):
        print(day)
        break
    if sum(used) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

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

a_i = [0] * n

day = 0
while True:
    matches = []
    has_match = False
    for i in range(n):
        if a_i[i] == n - 1:
            continue
        match = {i+1, a[i][a_i[i]]}
        if match in matches:
            lst = list(match)
            a_i[lst[0] - 1] += 1
            a_i[lst[1] - 1] += 1
            has_match = True
        else:
            matches.append(match)
    if has_match:
        day += 1
        if a_i.count(n - 1) == n:
            break
    else:
        day = -1
        break

print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[-1,0]
while count!=n*(n-1)//2 and day<=10**6:
  if check[len(check)-2]==check[len(check)-1]:
    print(-1)
    sys.exit()
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check.append(count)
if day>10**6:
  print(-1)
  sys.exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  import sys
  import math
  import collections

  sys.setrecursionlimit(10**7)

  n = int(input())
  a = [list(map(int,input().split())) for _ in range(n)]
  c = [0]*n
  d = 0
  
  while sum(c) < (n-1)*n:
    candidate = []
    for i in range(n):
      if i in candidate or c[i] > n-2:
        continue
      j = a[i][c[i]]-1
      if a[j][c[j]]-1 == i:
        candidate += [i]
        candidate += [j]
    if candidate:
      for i in candidate:
        c[i] += 1
      d+=1
    else:
      print(-1)
      quit()
      
  print(d)


if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

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

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

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

day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in range(1,N+1):
        if L[j]==[] 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]
            del L[j][0]
            del L[X][0]
            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:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
now=[[0,0] for i in range(n)]
day=0

while 1:
    day+=1
    siaisuu=0
    for i in range(n):
        if now[i][0]==n-1:
            continue
        # print(i)
        nex=a[i][now[i][0]]
        # print(day)
        # print(now)
        # print(nex)
        # print(a[nex-1][now[nex-1]])
        if i+1==a[nex-1][now[nex-1][0]] and now[i][1] != day and now[nex-1][1] != day:
            siaisuu+=1
            now[i][0]+=1
            now[i][1],now[nex-1][1]=day,day
            now[nex-1][0]+=1
    if siaisuu==0:
        break

for i in range(n):
    if now[i][0]!=n-1:
        print(-1)
        quit()

print(day-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
fin = [False] * N
An = [''] * N
for n in range(N):
    An[n] = deque([int(x) for x in input().split()])

days = 0

while False in fin:
    days += 1
    matched = [False] * N
    flag = False
    for n in [n for n in range(N) if fin[n]==False]:
        if matched[n]:
            continue
        op = An[n][0]
        if not matched[op - 1] and An[op - 1][0] == n + 1:
            flag = True
            An[n].popleft()
            An[op - 1].popleft()
            matched[n] = True
            matched[op - 1] = True
            if len(An[n]) == 0:
                fin[n] = True
            if len(An[op - 1]) == 0:
                fin[op - 1] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def solve():
  ## input
  N = int(input())
  An = [[i-1 for i in list(map(int, input().split()))] for _ in range(N)]  

  ## solve
  ret = 0
  Pn = [0 for _ in range(N)]
  rev = 0
  while rev < N-1:
    dct = defaultdict(lambda:set([]))
    game = 0
    rev = N
    for i in range(N):
      if Pn[i] >= N-1:
        continue
      else:
        j = An[i][Pn[i]]
        if i in dct[j]:
          dct[j].remove(i)
          game,Pn[i],Pn[j] = [game+1,Pn[i]+1,Pn[j]+1]
          rev = min(rev,Pn[i],Pn[j])
        else:
          dct[i].add(j)
    if game > 0:
      ret += 1
    else:
      return -1
  return ret

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ind = [0 for i in range(n)]
ind_copy = ind.copy()

a = np.array(a)
a = a - 1

ans = 0
while True:
    kanou = 0
    ans += 1
    for i in range(n):
        if ind[i] <= n-2:
            player = a[i][ind[i]]
        else:
            continue
        if ind[player] <= n-2:
            player_vs = a[player][ind[player]]
        else:
            continue
        if i == player_vs:
            kanou = 1
            ind_copy[i] = ind[i] + 1
            ind_copy[player] = ind[player] + 1
    if kanou == 0:
        hantei = 0
        for i in range(n):
            if ind[i] < n-2:
                hantei = 1
        if hantei == 1:
            ans = -1
        break
    ind = ind_copy.copy()

if ans != -1:
    print(ans - 1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n = int(input())

e = [[] for _ in range(n)]
for i in range(n):
    a = map(int, input().split())
    for aa in a:
        aa -= 1
        e[i].append((i, aa))

inds = [0] * n
st = set(e[i][0] for i in range(n))
cnt = 0
while st:
    flg = False
    nst = set()
    for tpl in st.copy():
        x, y = tpl
        if x > y: continue
        if (y, x) in st:
            # print(st, x, y, inds)
            flg = True
            inds[x] += 1
            inds[y] += 1
            st.discard(tpl)
            st.discard((y, x))
            if inds[x] < n - 1:
                nst.add(e[x][inds[x]])
            if inds[y] < n - 1:
                nst.add(e[y][inds[y]])
            # print(nst)
    # print(st, nst, inds, flg)
    if not flg:
        print(-1)
        exit()

    cnt += 1
    st.update(nst)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = []
fight = n * (n-1) // 2

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

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

while True:
  do_Flag = []
  
  for index, x in enumerate(s):
    if s_pos[index] >= n-1:
      continue
    a = x[s_pos[index]] - 1
    b = s[a][s_pos[a]] - 1
    if b == index:
      do_Flag.append(index)
    
  for i in do_Flag:
    s_pos[i] += 1
  if len(do_Flag) > 0:
    count += len(do_Flag) // 2
    if count >= fight:
      print(ans)
      break
    ans += 1
  else:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:

from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

#N = list(map(int, input().split()))

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


N = int(input())
A = []
day = [0]*N
for i in range(N):
	A.append(deque(map(int, input().split())))
num = 0
while True:
	judge = 0
	for i in range(N):
		if len(A[i]) > 0:
			j = A[i][0] - 1
			if len(A[j]) > 0:
				if A[j][0] == i + 1:
					A[i].popleft()
					A[j].popleft()
					shiai = max(day[i], day[j]) + 1
					day[i] = shiai
					day[j] = shiai
					num += 1
					judge = 1
					if len(A[i]) == 0:
						break
	if judge == 0:
		break

if num == N*(N - 1)//2:
	print(max(day))
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) - 1 for a in input().split()] for _ in range(N)]
    for i in range(N): 
        A[i].append(N)
        A[i].append(N)
    A.append([N for i in range(N + 1)])
    #print(A)
    day = 0
    match = [0 for i in range(N)]
    match.append(N)
    #print(match)
    while True:
        onmatch = set()
        for i in range(N):
            if i not in onmatch:
                vs = A[i][match[i]]
                if A[vs][match[vs]] == i and vs not in onmatch:
                    onmatch |= {i, vs}
        if onmatch:
            day += 1
            for i in onmatch: match[i] += 1
        else: break
    #print(match)

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

    return 0

if __name__ == "__main__": solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n):
  l1=list(map(int,input().split()))
  l1=l1[::-1]
  l[i+1]=l1
b=True
day=0
while b and l!=[[] for i in range(n+1)]:
  day+=1
  todaygame=[1 for i in range(n+1)]
  for i in range(1,n+1):
    if l[i]==[]:
      pass
    elif l[l[i][-1]]==[]:
      pass
    elif l[l[i][-1]][-1]==i:
      if todaygame[i]==1  and todaygame[l[i][-1]]==1:
        todaygame[i]=0
        todaygame[l[i][-1]]=0
        del l[l[i][-1]][-1]
        del l[i][-1]
  if todaygame==[1 for i in range(n+1)]:
    b=False
  else:
    todaygame=[1 for i in range(n+1)]
if b:
  print(day)
else:
  print(-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
league=[]
for _ in range(n):
    a=list(map(int,input().split()))
    league.append(a[::-1])

total_match=n*(n-1)//2
match=0
day=0

while match<total_match:
    day+=1
    today_match=[]

    for i in range(n):
        if i in today_match:
            continue
        if league[i]:
            m=league[i][-1]-1
            if m in today_match:
                continue
            if league[m] and league[m][-1]-1==i:
                today_match.extend((league[i].pop()-1, league[m].pop()-1))
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2

print(day)

Submission status: Time Limit Exceeded

Solution code:
def dec(s):
  n = int(s)
  return n - 1

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

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
    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:
    ans = -1
    break
  else:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

league = [ [ int(v)-1 for v in input().split() ] for i in range(n) ]
done = [ 0 for i in range(n) ]

def day():
    day_match = 0
    match = [ 0 for i in range(n) ]
    for i in range(n):
        for j in range(i+1,n):
            if league[i][done[i]] == j and league[j][done[j]] == i and match[i] == 0 and match[j]== 0:
                league[i][done[i]] = i
                league[j][done[j]] = j
                match[i] = 1
                match[j] = 1
                day_match += 1
                if done[i] < n-2:
                    done[i] += 1
                if done[j] < n-2:
                    done[j] += 1
    return day_match

cal_match = (n*n-n) // 2
total_match = 0
cont = 1
d = 0
while cont:
    d += 1
    one_day_match = day()
    total_match += one_day_match

    if one_day_match == 0:
        cont = 0
        print(-1)
    elif total_match == cal_match:
        cont = 0
        print(d)

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()
  m=[0]*n
  _m=copy.deepcopy(m)

  l=[]
  for _ in range(n):
    _l=LI()
    _l.reverse()
    l.append(_l)

  c=n*(n-1)
  ans=1
  while True:
    m=copy.deepcopy(_m)
    _c=c
    for i in range(n):
      if c<=0:
        return ans

      if m[i]!=0:
        continue

      if len(l[i])!=0:
        a=l[i][-1]-1
        if len(l[a])!=0:
          if l[a][-1]==i+1:
            if m[a]==0 and m[i]==0:
              l[a].pop()
              l[i].pop()
              m[a]=1
              m[i]=1
            else:
              continue
            c-=2
          else:
            continue
        else:
          continue
      else:
        continue
    if _c==c:
      return -1
    ans+=1

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque([int(_)-1 for _ in input().split()]) for __ in range(n)]
f=[0 for _ in range(n)]
m=n*(n-1)//2
d=0
while True:
    for i in range(n):
        if a[i] != deque([]):
            k=a[i][0]
            if f[i]==0 and f[k]==0:
                if a[k][0]==i:
                    f[i]=1
                    f[k]=1
                    m-=1
                    a[k].popleft()
                    a[i].popleft()
    if 1 not in f:
        print(-1)
        break
    else:
        f=[0 for _ in range(n)]
        d+=1
        if m==0:
            print(d)
            break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
count=[[0]*(n-1) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=0
	count+=1
	taisenzumi=[]
	for i in range(n):
		if i in taisenzumi:continue
		if data[i]:
			aite=data[i][0]
			# print(data[i],aite)
			if (aite-1) in taisenzumi:continue
			# print(data[i],aite)
			if data[aite-1][0]==i+1:
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi.append(aite-1)
				taisenzumi.append(i)
				last-=2
				flag=1
			else:continue
	if not flag:
		break
else:
	print(count)
	exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

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

cnt = 0
finished = set()
while True:
	impossible = True
	skip = copy.deepcopy(finished)
	#print(orders)
	for i in range(n):	
		if i not in skip and orders[i][0] - 1 not in skip and orders[orders[i][0] - 1][0] - 1 == i:				
			a = i
			b = orders[i][0] - 1
			impossible = False
			skip.add(a)
			skip.add(b)
			orders[orders[i][0] - 1].popleft()
			orders[i].popleft()

			if len(orders[i]) == 0:
				finished.add(a)
			if len(orders[b]) == 0:
				finished.add(b)
	cnt += 1

	if len(finished) == n:
		print(cnt)
		break

	if impossible:
		print(-1)
		break

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 match != [n - 1 for i in range(n)]:
    flag = False
    add = [False for i in range(n)]
    for i in range(n):
        if match[i] <= n - 2:
            j = a[i][match[i]] - 1
            if a[j][match[j]] - 1 == i:
                add[i] = True
                add[j] = True
                flag = True
    if flag == True:
        match = [match[i] + int(add[i]) for i in range(n)]
        day += 1
    else:
        break
else:
    print(day)
    sys.exit()
print(-1)

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())


#ベルマンフォード(始点と終点が決まってる時)
def BellmanFord(Start,Goal):
    Costs=[INF]*N
    Costs[Start] = 0
    upd8s = [True]*N
    for i in range(2*N): #2N回ループ(負閉路の検出までみる)
        will_upd8s = [False]*N
        for s in range(N):
            if not upd8s[s]: continue    #前回更新してないので見ない
            for t,c in lines[s]:
                if c + Costs[s] < Costs[t]:
                    Costs[t] = Costs[s]+c
                    will_upd8s[t] = True #更新した点だけ次に見る
                    if i >= N:
                        Costs[t] = -INF

        if i == N-1: #Nループ目のGoalのCostを記録
            tmp = Costs[Goal]

        upd8s = will_upd8s[:]

    if tmp != Costs[Goal]:
        return -INF
    else:
        return Costs[Goal]


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

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


next = [[-1]*N for _ in range(N)]
for x in range(N):
    AA = AAA[x]
    for y,A in enumerate(AA):
        next[x][A-1] = y

lines = defaultdict(set)

for x in range(N):
    for y in range(N-1):
        tx = AAA[x][y] - 1
        ty = next[tx][x]
        lines[calc(x,y)].add((calc(tx,ty),0))

for x in range(N):
    for y in range(N-2):
        lines[calc(x,y)].add((calc(x,y+1),-1))

S = N*(N-1)+1
T = S + 1

for x in range(N):
    lines[S].add((calc(x,0),0))
    lines[calc(x,N-2)].add((T,0))

N = T+1
ret = -BellmanFord(S,T)

if ret == INF:
    print(-1)
else:
    print(ret+1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

e = [[] for _ in range(n)]
for i in range(n):
    a = map(int, input().split())
    for aa in a:
        aa -= 1
        e[i].append((i, aa))

inds = [0] * n
st = set(e[i][0] for i in range(n))
cnt = 0
while st:
    flg = False
    nst = set()
    for tpl in st.copy():
        x, y = tpl
        if x > y: continue
        if (y, x) in st:
            # print(st, x, y, inds)
            flg = True
            inds[x] += 1
            inds[y] += 1
            st.discard(tpl)
            st.discard((y, x))
            if inds[x] < n - 1:
                nst.add(e[x][inds[x]])
            if inds[y] < n - 1:
                nst.add(e[y][inds[y]])
            # print(nst)
    # print(st, nst, inds, flg)
    if not flg:
        print(-1)
        exit()

    cnt += 1
    st.update(nst)
print(cnt)

Submission status: Time Limit Exceeded

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

ans=0
cnt=0
for j in range(n*n//2+1):
    f=0
    q=[]
    for i in range(n):        
        if len(a[i])>0 and len(a[a[i][0]-1])>0 and i+1==a[a[i][0]-1][0] and i<a[i][0]-1:
            #a[a[i][0]-1].pop(0)
            #a[i].pop(0)
            q.append(i)
            q.append(a[i][0]-1)
            f+=1    
            cnt+=1
    if len(q)>0:
        for k in q:
            a[k].pop(0)
            
            
    if f==0 and cnt<n*(n-1)//2:
        print(-1)
        exit()
    elif f>0:
        ans+=1
    else:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
def notempty(b):
    return any(map(lambda x: len(x), b))


n = int(input())
a = [list(reversed(list(map(lambda x:int(x) - 1, input().split()))))
     for _ in range(n)]
cnt = 0
while notempty(a):
    flg = 0
    cnt += 1
    li = [True] * n
    for i in range(n):
        if len(a[i]) and li[i] and len(a[[i][-1]]) and li[a[i][-1]] and a[a[i][-1]][-1] == i:
            5
            tmp = a[i][-1]
            a[i].pop()
            a[tmp].pop()
            li[i], li[tmp] = False, False
            flg = 1
    if not flg:
        print(-1)
        exit(0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
import collections
plan = {}
for i in range(n):
    plan[i+1] = collections.deque(list(map(int, input().split())))

remain = [player for player in range(1,n+1)]
cnt = 0
while remain != []:
    visit = [p for p in remain]
    flag = True
    done = []
    for p_check in visit:
        if p_check in done:
            continue
        done.append(p_check)
        if plan[p_check][0] not in done and plan[plan[p_check][0]][0] == p_check:
            done.append(plan[p_check][0])
            plan[plan[p_check][0]].popleft()
            if len(plan[plan[p_check][0]]) == 0: remain.remove(plan[p_check][0])
            plan[p_check].popleft()
            if len(plan[p_check]) == 0: remain.remove(p_check)
            flag = False 
    if flag:
        cnt = -1
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n=int(input()[:-1])
    a=[list(map(int, input().split()))[::-1] for _ in range(n)]
    all_g=n*(n-1)//2
    g=0
    d=0
    while 1:
        d+=1
        finish=set()
        for i in range(n):
            if i in finish:continue
            if a[i]==[]:continue
            ii=a[i][-1]-1
            if a[ii][-1]-1==i:
                g+=1
                finish.add(ii)
                finish.add(i)
        if g==all_g:
            print(d)
            break
        if not finish:
            print(-1)
            break
        for ii in finish:
            a[ii].pop()

main()

Submission status: Time Limit Exceeded

Solution code:
def main():    
    n = int(input())
    a = [list(reversed(list(map(int,input().split())))) for _ in range(n)]
    ans = 0
    r = list(range(n))
    while True:
        pop_list = []
        pap = pop_list.append
        for i in r:
            for j in r:
                if i < j and a[i] and a[j]:
                    if a[i][-1]-1 == j and a[j][-1]-1 == i:
                        pap(i)
                        pap(j)
        if not pop_list:
            ans = -1
            break
        for i in pop_list:
            _ = a[i].pop(-1)
            if not a[i]:
                r.remove(i)
        ans += 1
        if not r:
            break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[-1,0]
while count!=n*(n-1)//2:
  if check[len(check)-2]==check[len(check)-1]:
    print(-1)
    sys.exit()
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check.append(count)
print(day)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

n= int(sys.stdin.readline())
a= [ None for _ in range(n) ]
for i in range(n):
    a[i]= deque( [ int(x)-1 for x in sys.stdin.readline().split() ] )
#
tot= (n*(n-1))//2
now= 0
c= 0
while True:
    flags= [ None for _ in range(n) ]
    for i in range(n):
        if flags[i]!=None: continue
        ai = a[i]
        if len(ai)==0: continue
        j  = ai[0]
        aj = a[j]
        if aj[0]==i:
            flags[i]= True
            flags[j]= True
            now+= 1
    #
    if not any(flags): break
    for i in range(n):
        if flags[i]: a[i].popleft()
    #
    c+= 1
    if now==tot: break
#
if now==tot: print( c )
else: print( -1 )

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def main():
  inp = sys.stdin.readline
  n = int(inp())
  target_num = n*(n-1)//2

  all_set = set()
  all_add = all_set.add
  a = [None] * n
  for i in range(n):
    a[i] = deque(map(int, inp().split()))
  ans = 0

  while True:
    cur_set = set()
    flag = False
    for i in range(n):
      if len(a[i]):
        tup = (min(i+1, a[i][0]), max(i+1, a[i][0]))
      else:
        continue
      if tup not in cur_set:
        cur_set.add(tup)
      elif tup in cur_set:
        all_add(tup)
        t1, t2 = tup
        a[t1-1].popleft()
        a[t2-1].popleft()
        flag = True
    ans += 1
    if len(all_set)==target_num:
      break
    if not flag:
      print(-1)
      exit()

  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

    now = [0] * N
    day = 0
    while True:
        had_game = False
        all_finish = True
        can_game = [True] * N
        for i in range(N):
            if now[i] < N-1 and can_game[i]:
                all_finish = False
                want = a[i][now[i]] - 1
                if can_game[want]:
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        can_game[i] = False
                        can_game[want] = False
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()