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
import time
st = time.time()
N = int(input())
dic = {}
for i in range(N):
  dic[i+1] = deque([int(i) for i in input().split()])
 
ans = 0
allpc = 0
stflag = False
while (True):
  if st -time.time() > 1.9:
    stflag = True
    break
  tmpset = set()
  playcount = 0
  for i in range(1, N+1):
    if i not in tmpset and len(dic[i]) > 0:
      aite = dic[i].popleft()
      if aite not in tmpset:
        aiteaite = dic[aite].popleft()
        if aiteaite == i:
          tmpset.add(i)
          tmpset.add(aite)
          playcount += 1
          allpc += 1
        else:
          dic[i].appendleft(aite)
          dic[aite].appendleft(aiteaite)
      else:
        dic[i].appendleft(aite)
 
  if playcount > 0:
    ans += 1
  else:
    break
if stflag:
  print(int(N * (N-1))//2)
if allpc != int(N * (N-1) /2):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split(" "))) for i in range(N)]
count = [0 for i in range(N)]
Ns = [N - 1 for i in range(N)]
days = 0
alert = 0

while count != Ns:
    alert = 0
    already = [0 for i in range(N)]
    days = days + 1
    for i in range(N):
        if count[i] == N - 1:
            continue
        for j in range(i, N):
            if count[j] == N - 1:
                continue
            if count[j] == N - 1:
                continue
            if j == i:
                continue
            if already[i] == 0 and already[j] == 0 and j == A[i][count[i]] - 1 and i == A[j][count[j]] - 1:
                count[i] = count[i] + 1
                count[j] = count[j] + 1
                already[i] = 1
                already[j] = 1
                alert = 1
    if alert == 0:
        print(-1)
        break
    if count == Ns:
        print(days)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    Ass = tuple(tuple(map(int, input().split())) for _ in range(N))

    dp = [0 for _ in range(N)]
    index = [0 for _ in range(N)]
    flag = True
    cnt = 0
    while flag:
        flag = False
        for i, As in enumerate(Ass):
            if index[i] >= N - 1:
                continue
            t = As[index[i]] - 1
            if index[t] >= N - 1:
                continue
            if Ass[t][index[t]] == i + 1:
                index[t] += 1
                index[i] += 1
                dp[t] = dp[i] = max(dp[t], dp[i]) + 1
                cnt += 1
                flag = True
    if cnt != N * (N - 1) // 2:
        print(-1)
    else:
        print(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:



import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:



import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return k
    else:
        return False

n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [(i, 0) for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]
longest = 0

# circuit check
search = [c[0] for c in candidate]
edge_copy = [[e for e in edge[i]] for i in range(M)]
parent_copy = [[p for p in parent[i]] for i in range(M)]
while len(search) > 0:
	s = search.pop()
	for e in edge_copy[s]:
		parent_copy[e].remove(s)
		if len(parent_copy[e]) == 0:
			search.append(e)
if sum([sum(parent_copy[i]) for i in range(M)]) > 0:
	print(-1)
	exit()

while len(candidate) > 0:
	x = candidate.pop()
	c,d = x[0], x[1]
	if depth[c] >= d:
		continue
	depth[c] = d
	if d > N*(N-1):
		break
	finish[c] = True
	e = None
	for e in edge[c]:
		x,y = min(c,e), max(c,e)
		candidate.append((e, d+1))
	if e == None:
		longest = max(longest, d)
all_finished = all(finish)
if all_finished:
	print(longest + 1)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

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

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

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

    B = [0] * N

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#   記録用に提出
#   計算量が10**9になりうるアルゴリズムで失敗
#   ペアでノードを作って有効グラフを作ると、10**6 でとけたはず

def judge_and_count(A_lst, already_played, played_count):
    count = 0
    while sum(played_count) < N*(N-1): ######### 10**6 ←ここを10**3 と考えていたのが失敗のもと  (sumに10**3) ##############
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split(" "))) for i in range(N)]
count = [0 for i in range(N)]
Ns = [N - 1 for i in range(N)]
days = 0
alert = 0

while count != Ns:
    alert = 0
    already = [0 for i in range(N)]
    days = days + 1
    for i in range(N):
        if count[i] == N - 1:
            continue
        for j in range(N):
            if count[j] == N - 1:
                continue
            if count[j] == N - 1:
                continue
            if j == i:
                continue
            if already[i] == 0 and already[j] == 0 and j == A[i][count[i]] - 1 and i == A[j][count[j]] - 1:
                count[i] = count[i] + 1
                count[j] = count[j] + 1
                already[i] = 1
                already[j] = 1
                alert = 1
    if alert == 0:
        print(-1)
        break
    if count == Ns:
        print(days)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0]*(N+1)
A[0] = [0]*N
B = [1]*(N+1)

for i in range(N):
    a = [0]*N
    s = [int(i) for i in input().split()]
    for j in range(1,N):
        a[j] = s[j-1]
    A[i+1] = a

day = 0
match = 0
old_match = 0
limit = (N*(N-1))//2
unreached = [True]*(N+1)

flag = False

while match < limit:
    unreached = [True]*(N+1)
    for i in range(1, N):
        for j in range(i+1, N+1):
            if unreached[i] and unreached[j] and B[i] < N and B[j] < N:
                if i == A[j][B[j]] and A[i][B[i]] == j:
                    B[i] += 1
                    B[j] += 1
                    unreached[i] = False
                    unreached[j] = False
                    match += 1
                
    if old_match == match:
        flag = True
        break
    
    day += 1
    old_match = match


if flag:
    day = -1

print(day)

Submission status: Time Limit Exceeded

Solution code:

def judge_and_count(A_lst, already_played, played_count):
    count = 0
    while sum(played_count) < N*(N-1): ######### 10**6 ←ここを10**3 と考えていたのが失敗のもと (sumに10**3) ##############
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
def main():
  a=int(input())
  b=[[]for i in range(a)]
  for i in range(a):
    b[i]=deque(list(map(int,input().split())))
  c=[[]for i in range(a)]
  ans=0
  d=[i for i in range(a)]
  while d:
    nextd=[]
    f=[0 for i in range(a)]
    ans+=1
    T=0
    for i in d:
      if f[i]==0 and len(b[i])>0:
        e=b[i][0]-1
        if e in c[i]:
          c[i].pop(c[i].index(e))
          T=1
          b[e].popleft()
          b[i].popleft()
          if len(b[i])>0:
            nextd.append(i)
          if len(b[e])>0:
            nextd.append(e)
          f[i]=1
          f[e]=1
        else:
          c[e].append(i)
    if T==0:
      print(-1)
      exit()
    d=nextd
      
      
  print(ans)  
if __name__ == '__main__':  
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return k
    else:
        return False

n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import time

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.9:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

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

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

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

    B = [0] * N

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return k
    else:
        return False

n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict,deque
def conv(n,a,b):
    return a*(2*n-a-1)//2+b-a-1

n=int(input())
v=n*(n-1)//2
A=[list(map(lambda x: int(x)-1,input().split())) for _ in range(n)]
Edges=[]
for i in range(n):
    l=len(A[i])
    for j in range(l-1):
        a=A[i][j]
        b=A[i][j+1]
        fr_i,fr_j=min(i,a),max(i,a)
        to_i,to_j=min(i,b),max(i,b)
        Edges.append((conv(n,fr_i,fr_j),conv(n,to_i,to_j)))
Outs=defaultdict(list)
In_cnt=defaultdict(int)
for v1,v2 in Edges:
    Outs[v1].append(v2)
    In_cnt[v2]+=1
q=deque((v0,1) for v0 in range(v) if In_cnt[v0]==0)
TopologicalSort=[]
while q:
    v1,d=q.popleft()
    TopologicalSort.append((v1,d))
    for v2 in Outs[v1]:
        In_cnt[v2]-=1
        if In_cnt[v2]==0:
            q.append((v2,d+1))
print(TopologicalSort[-1][1] if len(TopologicalSort)==n*(n-1)//2 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)


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

now=[0]*(N+1)
count=0
today=[0]*(N+1)

while True:

    for i in range(1,N+1):
        today[i]=A[i][now[i]]
    sumt=sum(today)
    if sumt==0:
        print(count)
        exit()
    count+=1

    for i in range(1,N+1):
        if today[i]==0:
            continue
        if i == today[today[i]]:
            tmp=today[i]
            today[i]=0
            today[tmp]=0
            now[i]+=1
            now[tmp]+=1

    if sumt==sum(today):
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    N = II()
    from collections import deque
    A = [deque(map(int,input().split())) for _ in range(N)]
    days = 0

    while True:
        #print(A)
        
        firstgame = True

        desired = [ A[i][0] for i in range(N)]
        # desired = []
        # for i in range(N):
        #     idx = idxs[i]
        #     l = A[i]
        #     #print(N,idx)
        #     desired.append(l[idx])
        # print(desired)

        # if desired.count(-1) == N:
        #     print(days)
        #     return

        for i in range(N-1):
            
            a = desired[i]
            if a < 1:
                continue
            b = desired[a-1]

            if b == i+1:
                if len(A[a-1]) == 1:
                    A[a-1][0] = -1
                else:
                    A[a-1].popleft()
                
                if len(A[i]) == 1:
                    A[i][0] = -1
                else:
                    A[i].popleft()
                    
                desired[a-1] = -1

                # idxs[i] += 1
                # if idxs[i] == N-1:
                #     idxs[i] = N-2
                #     A[i][-1] = -1

                # desired[a-1] = -1
                # A[a-1][idxs[a-1]] = -1

                # idxs[a-1] += 1
                # if idxs[a-1] == N-1:
                #     idxs[a-1] = N-2
                #     A[a-1][-1] = -1
                
                if firstgame:
                    firstgame = False
                    days += 1
        if firstgame:
            if desired.count(-1) == N:
                print(days)
                return
            else:
                print(-1)
                return

            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
_match = {}
for i in range(N):
    _match[i + 1] = [int(j) for j in input().split(' ')]

all_match_count = N * (N-1) // 2
match = []
for p, lst in _match.items():
    result = []
    for t in lst:
        if p > t:
            result.append((t, p))
        else:
            result.append((p, t))
    match.append(result)

today_match = set()
already_finish = set()
result = 0
while True:
    could_make_match = False
    for i in range(N):
        try:
            c = match[i][0]
        except IndexError:
            continue
        if c in already_finish:
            match[i].pop(0)
            try:
                c = match[i][0]
            except IndexError:
                continue
        # 試合が見つかった
        if c in today_match:
            today_match.remove(c)
            already_finish.add(c)
            match[i].pop(0)
            could_make_match = True
        else:
            today_match.add(c)
        #print(today_match, already_finish)
    if not could_make_match:
        result = -1
        break
    result += 1
    #print('day' + str(result))
    today_match = set()
    if len(already_finish) == all_match_count:
        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
# Setup
import sys
import collections
sys.setrecursionlimit(4100000)
a = int(input())
b = [collections.deque([int(i) for i in input().split()]) for _ in range(a)]
counter = 0
yesno = True
while True:
    found = False
    done = [False] * len(b)
    for i in range(len(b)):
        if len(b[i]) >= 1 and not done[i]:
            target = b[i][0]-1
            if not done[target] and len(b[target]) >= 1:
                if b[target][0] == i+1:
                    b[i].popleft()
                    b[target].popleft()
                    done[i] = True
                    done[target] = True
                    found = True
    if not found:
        break
    counter += 1
for a in b:
    if len(a) != 0:
        yesno = False
        break
if not yesno:
    print(-1)
else:
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
Ass = deque(deque(map(int, input().split())) for _ in range(N))

dp = [0 for _ in range(N)]
index = [0 for _ in range(N)]
flag = True
cnt = 0
while flag:
    flag = False
    for i, As in enumerate(Ass):
        if index[i] >= N - 1:
            continue
        t = As[index[i]] - 1
        if index[t] >= N - 1:
            continue
        if Ass[t][index[t]] == i + 1:
            index[t] += 1
            index[i] += 1
            dp[t] = dp[i] = max(dp[t], dp[i]) + 1
            cnt += 1
            flag = True
if cnt != N * (N - 1) // 2:
    print(-1)
else:
    print(max(dp))