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
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return


# B
def B():
    a, b = LI()
    print(-(-(b - 1) // (a - 1)))
    return


# C
def C():
    N = I()
    H = LI()
    ans = 0
    cnt = 0
    for i in range(1, N):
        if H[i - 1] >= H[i]:
            cnt += 1
            ans = max(ans, cnt)
        else:
            cnt = 0
    print(ans)
    return


# D
def D():
    N = I()
    print(N * (N - 1) // 2)
    return


# E
def E():
    N = I()
    A = [[]] + [LI() for i in range(N)]
    B = [0 for i in range(N + 1)]
    cnt = 0
    while (1):
        C = [0 for i in range(N + 1)]
        for i in range(1, N + 1):
            if B[i] < N - 1:
                if B[A[i][B[i]]] < N - 1:
                    j = A[i][B[i]]
                    if i == A[j][B[j]]:
                        C[i] = 1
                        C[j] = 1
        for i in range(1, N + 1):
            if C[i] == 1:
                B[i] += 1
        cnt += 1
        if sum(B) == (N - 1) * N:
            print(cnt)
            return
        elif sum(C) == 0:
            print(-1)
            return


# F
def F():
    return


# Unittest
def resolve():
    E()
    return


# Solve
if __name__ == "__main__":
    E()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return


# B
def B():
    a, b = LI()
    print(-(-(b - 1) // (a - 1)))
    return


# C
def C():
    N = I()
    H = LI()
    ans = 0
    cnt = 0
    for i in range(1, N):
        if H[i - 1] >= H[i]:
            cnt += 1
            ans = max(ans, cnt)
        else:
            cnt = 0
    print(ans)
    return


# D
def D():
    N = I()
    print(N * (N - 1) // 2)
    return


# E
def E():
    N = I()
    A = [deque(LI()) for i in range(N)]
    cnt = 0
    while (1):
        B = [0 for i in range(N)]
        for i in range(N):
            if len(A[i]) != 0 and len(A[A[i][0] - 1]) != 0:
                if i + 1 == A[A[i][0] - 1][0]:
                    B[i] = 1
                    B[A[i][0] - 1] = 1
        for i in range(N):
            if B[i] == 1:
                A[i].popleft()
        cnt += 1
        if sum([len(A[i]) for i in range(N)]) == 0:
            print(cnt)
            return
        elif sum(B) == 0:
            print(-1)
            return


# F
def F():
    return


# Unittest
def resolve():
    E()
    return


# Solve
if __name__ == "__main__":
    E()

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
# 隣接リスト
graph = {i+1000*j:set() for i in range(n) for j in range(i+1,n)}
# 入次数を管理
st = {i+1000*j:0 for i in range(n) for j in range(i+1,n)}

#たどったかどうかチェック
check = {i+1000*j:True for i in range(n) for j in range(i+1,n)}

# 入次数が0の頂点の集まり
szero = []

#ソートされたやつたち
ans = []

for i in range(n):
    ls = list(map(int,input().split()))
    f = -1
    for p in ls:
        v = min(i,p-1) + 1000*(max(i,p-1))
        if f != -1:
            graph[f].add(v)
            st[v] += 1
        f = v

for v in st.keys():
    if st[v] == 0:szero.append(v)
count = 0
next_szero = []
while True:
    count += 1
    for i in szero:
        ans.append(i)
        for v in graph[i]:
            #if check[v]:check[v] = False
            #else:continue
            st[v] -= 1
            if st[v] == 0:
                next_szero.append(v)
    if len(next_szero) == 0:break
    szero = copy.deepcopy(next_szero)
    next_szero = []

if len(ans) != n*(n-1)//2:
    print(-1)
else:
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    while que:
        cou = int(0)
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            cou +=1
            if cou >n:
                return -1
#            if nowv == W[ne]:
                #ループが嫌な時
#                return -1
#            if W[ne] == -1:
            W[ne] = (nowv+1) % 2
            len[ne] = max(nowlen+1,len[ne])
            que.append(ne)
    return max(len)
#########################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
A = [LI() for _ in range(N)]
vlen = N*(N-1)//2
v = [[] for _ in range(vlen)]
match = [[-1]*N for _ in range(N)]
k = int(0)
for i in range(N):
    for j in range(i+1,N):
        match[i][j] = k
        match[j][i] = k
        k +=1

for i in range(N):
#    print(v)
    for j in range(N-2):
        v[match[i][A[i][j]-1]].append(match[i][A[i][j+1]-1])

anscandi =[0]*vlen
for i in range(vlen):
    anscandi[i] = bfs(vlen,i,v)
    if anscandi[i]==-1:
        ans = -1
        break
if ans==0:
    ans = max(anscandi)+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
day=0
while True:
    flag=0
    K=[0]*(N+1)
    for i in range(1,N+1):
        if (L[i] != []) & (K[i] == 0):
            if (L[L[i][0]][0]==i) & (K[L[i][0]] == 0):
                K[L[i][0]]=1
                K[i]=1
                del L[L[i][0]][0]
                del L[i][0]
                flag=1
    if  flag == 0:
        for i in range(1,N+1):
            if L[i] != []:
                day=-1
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
finished=[]
day=0
while True:
    for i in range(1,N+1):
        if L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                finished.append(i)
    for i in range(len(finished)): 
        del L[finished[i]][0]
    if  finished == []:
        for i in range(1,N+1):
            if L[i] != []:
                day=-1
        break
    finished=[]
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
finished=[]
day=0
while True:
    flag = 0
    for i in range(1,N+1):
        if L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                finished.append(i)
                flag = 1
    for i in range(len(finished)): 
        del L[finished[i]][0]
    finished=[]
    if flag == 0:
        for i in range(1,N+1):
            if L[i] != []:
                day=-1
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = [int(j) for j in input().split( ) ]
finished=[]
day=0
while True:
    flag = 0
    for i in range(1,N+1):
        if i in finished or L[i]==[]:
            continue
        else: 
            if L[L[i][0]][0]==i:
                finished.append(i)
                finished.append(L[i][0])
                
                flag = 1
    for i in range(len(finished)):
        j = finished[i]
        del L[j][0]
    finished=[]
    if flag == 0:
        for i in range(1,N+1):
            if L[i] != []:
                day=-1
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
N = int(input())

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

cnt = 0
goal = N*(N-1)//2
for day in count(1):
    used = [not bool(q) for q in queues]
    flag = False
    for i,u in enumerate(used):
        if not u:
            j = queues[i][-1]
            if not used[j] and queues[j][-1] == i:
                used[i] = True
                used[j] = True
                flag = True
                cnt += 1
                queues[i].pop()
                queues[j].pop()

    if cnt == goal:
        print(day)
        break
    elif not flag:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xss = [[int(x)-1 for x in input().split()] for _ in range(n)]

class Stack:
    def __init__(xs):
        self.__list = list(reversed(xs))

    def peak(self):
        return self.__list[-1]

    def pop(self):
        return self.pop()

def solve(n, xss):
    yss = [[-1] + list(reversed(xs)) for xs in xss]
    ans = 0
    while True:
        ms = list(matches(yss))
        if len(ms) == 0:
            if all(len(ys)==1 for ys in yss):
                return ans
            else:
                return -1
            return ans
        ans += 1
        for x, y in ms:
            yss[x].pop()
            yss[y].pop()

    for i in range(n):
        while len(yss[i]) > 0:
            match = find_first_match(yss, i)
            if match is None:
                return [-1]
            x, y = match
            ans

def matches(yss):
    firsts = [ys[-1] for ys in yss]
    for x, y in enumerate(firsts):
        if y!=-1 and x < y and firsts[y]==x:
            yield y, firsts[y]

print(solve(n, xss))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xss = [[int(x)-1 for x in input().split()] for _ in range(n)]

class Stack:
    def __init__(xs):
        self.__list = list(reversed(xs))

    def peak(self):
        return self.__list[-1]

    def pop(self):
        return self.pop()

def solve(n, xss):
    yss = [[-1] + list(reversed(xs)) for xs in xss]
    ans = 0
    while True:
        ms = list(matches(yss))
        if len(ms) == 0:
            if all(len(ys)==1 for ys in yss):
                return ans
            else:
                return -1
            return ans
        ans += 1
        for x, y in ms:
            yss[x].pop()
            yss[y].pop()

    for i in range(n):
        while len(yss[i]) > 0:
            match = find_first_match(yss, i)
            if match is None:
                return [-1]
            x, y = match
            ans

def matches(yss):
    firsts = [ys[-1] for ys in yss]
    for x, y in enumerate(firsts):
        if y!=-1 and x < y and firsts[y]==x:
            yield y, firsts[y]

print(solve(n, xss))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
import numpy as np
#0-indexed
N = int(input())
A = np.array(sys.stdin.read().split(), dtype=int).reshape((N, N - 1))
A -= 1
R = np.arange(N)
ans = 0
while True:
    I = (A[A[:, 0]][:, 0] == R) * (A[:, 0] != -1)
    if not I.any():
        break
    ans += 1
    A[I, :-1] = A[I, 1:]
    A[I, -1] = -1
if (A == -1).all():
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def is_okay(n, a, check):
    ans = 0
    while a != check:
        pair = []
        for i in range(n):
            if a[i]:
                if a[a[i][0]-1]:
                    if a[a[i][0]-1][0]-1 == i:
                        pair.append(i)
            
        if pair:
            ans += 1
            for index in pair:
                a[index].popleft()
        else:
            print(-1)
            return
            
    print(ans)
    return

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

Submission status: Time Limit Exceeded

Solution code:
def is_okay(n, a, check):
    ans = 0
    while a != check:
        pair = []
        for i in range(n):
            if a[i]:
                if a[a[i][0]-1]:
                    if a[a[i][0]-1][0]-1 == i:
                        pair.append(i)
            
        if pair:
            ans += 1
            for index in pair:
                del a[index][0]
        else:
            print(-1)
            return
            
    print(ans)
    return

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

Submission status: Time Limit Exceeded

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

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	ans = 0
	sum_ = 0
	fin = N*(N-1)*(N+1)//2
	while 1:
		delete = [0]*N
		for i in range(1, N):
			# print("i =", i)
			if len(A[i-1]) == 0 or delete[i-1] or delete[A[i-1][0]-1]:
				# print("continue")
				continue
			if i == A[A[i-1][0]-1][0]:
				# print("delete!")
				delete[i-1] = 1
				delete[A[i-1][0]-1] = 1
				tmp1 = i-1
				tmp2 = A[i-1][0]-1
				sum_ += A[tmp1].pop(0)
				sum_ += A[tmp2].pop(0)
		# print(delete)

		if sum(delete) == 0:
			print(-1)
			sys.exit(0)
			
		ans += 1
		if sum_ == fin:
			break
		
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	ans = 0
	sum_ = 0
	while 1:
		delete = [0]*(N+1)
		for i in range(1, N):
			if len(A[i-1]) == 0:
				continue
			if i == A[A[i-1][0]-1][0]:
				delete[i] = 1
				delete[A[i-1][0]] = 1
		if sum(delete) == 0:
			print(-1)
			sys.exit(0)

		for i in range(1, len(delete)):
			if delete[i] == 1:
				sum_ += A[i-1].pop(0)
		ans += 1
		if sum_ == N*(N-1)*(N+1)//2:
			break
		
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	ans = 0
	sum_ = 0
	flag = False
	while 1:
		delete = [0]*(N+1)
		for i in range(1, N):
			if len(A[i-1]) == 0:
				continue
			if i == A[A[i-1][0]-1][0]:
				delete[i] = 1
				delete[A[i-1][0]] = 1
				flag = True
		if flag == False:
			print(-1)
			sys.exit(0)

		for i in range(1, len(delete)):
			if delete[i] == 1:
				sum_ += A[i-1].pop(0)
		ans += 1
		if sum_ == N*(N-1)*(N+1)//2:
			break
		
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [LIST() for _ in range(N)]

ans = 0
sum_ = 0
while 1:
	delete = [0]*(N+1)
	for i in range(1, N):
		if len(A[i-1]) == 0:
			continue
		if i == A[A[i-1][0]-1][0]:
			delete[i] = 1
			delete[A[i-1][0]] = 1
	if sum(delete) == 0:
		print(-1)
		sys.exit(0)

	for i in range(1, len(delete)):
		if delete[i] == 1:
			sum_ += A[i-1].pop(0)
	ans += 1
	if sum_ == N*(N-1)*(N+1)//2:
		break
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())

A = np.zeros((N, N - 1), dtype = 'int')
for i in range(N):
    A[i] = np.array(list(map(int, input().split())))
A -= 1

game = [0]*N# game[i] = 選手iが何試合目まで終了したか

#success_flag = [N - 1]*N
total = N*(N -1)//2
games = 0
day = 0
#while game != success_flag:
while games < total:
    daygame_finish_flag = [False]*N
    game_over = True
    for i in range(N):
        if daygame_finish_flag[i] or game[i] == N - 1: #iがすでにその日試合をしていた場合もしくは全試合終わっている場合
            continue
        j = A[i][game[i]]
        if daygame_finish_flag[j]:
            continue
        if i == A[j][game[j]]:
            game_over = False
            daygame_finish_flag[i] = True
            daygame_finish_flag[j] = True
            game[i] += 1
            game[j] += 1
            games += 1
    if game_over:
        day = - 1
        break
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())

A = np.zeros((N, N - 1), dtype = 'int')
for i in range(N):
    A[i] = np.array(list(map(int, input().split())))
A -= 1

game = [0]*N# game[i] = 選手iが何試合目まで終了したか

success_flag = [N - 1]*N

day = 0
while game != success_flag:
    daygame_finish_flag = [False]*N
    game_over = True
    for i in range(N):
        if daygame_finish_flag[i] or game[i] == N - 1: #iがすでにその日試合をしていた場合もしくは全試合終わっている場合
            continue
        j = A[i][game[i]]
        if daygame_finish_flag[j]:
            continue
        if i == A[j][game[j]]:
            game_over = False
            daygame_finish_flag[i] = True
            daygame_finish_flag[j] = True
            game[i] += 1
            game[j] += 1
    if game_over:
        day = - 1
        break
    day += 1
print(day)

Submission status: Time Limit Exceeded

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


def main():
    N = int(input().strip())
    A = [[0]] * (N+1)
    for idx in range(1, N+1):
        A[idx] = list(reversed([int(x) for x in input().strip().split()]))

    ans = 0
    end_count = 0
    proc_count = 0
    while True:
        end_count = 0
        proc_count = 0
        for idx in range(1, N+1):
            if len(A[idx]) == 0:
                end_count += 1
                continue
            if A[A[idx][-1]][-1] == idx:
                A[A[idx][-1]][-1] = 0
                A[idx][-1] = 0
                proc_count += 1
        if end_count == N:
            print(ans)
            return
        if proc_count == 0:
            print(-1)
            return
        for idx in range(1, N+1):
            if len(A[idx]) != 0:
                if A[idx][-1] == 0:
                    A[idx].pop()
        ans += 1


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(0, N*N+1):
  done = [False] * N
  empty = True
  played = False
  for j, aa in enumerate(aaa):
    if len(aa) > 0:
      empty = False
      l = aa[-1]-1
      if (not (done[j] or done[l])) and len(aaa[l]) > 0 and aaa[l][-1] == j+1:
          aa.pop()
          aaa[l].pop()
          done[j], done[l] = True, True
          played = True
  if empty:
    print(i)
    break
  elif not played:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
import itertools

class DiGraph:
    # n is the number of N
    # E is a set of edges where each edge is a two tuple (u, v)
    def __init__(self, n, E = set()):
        self.N = n # number of vertices
        self.V = list(range(0, n)) # V = [0, 1, ..., n-1]
        self.AL = [set() for i in range(n)] # adjacency list
        for e in E:
            self.add_edge(e[0], e[1])

    def add_edge(self, u, v): # u is head, v is tail
        self.AL[u].add(v)

    def _is_cyclic_component(self, v, visited, in_rec_stack):
        visited[v] = True
        in_rec_stack[v] = True

        for w in self.AL[v]: # for all the neighbours
            if not visited[w]:
                if self._is_cyclic_component(w, visited, in_rec_stack):
                    return True
            elif in_rec_stack[w]:
                return True

        in_rec_stack[v] = False
        return False

    # works no matter whether the directed graph is strongly connected
    def is_cyclic(self):
        visited = [False] * self.N
        in_rec_stack = [False] * self.N
        for v in self.V:
            if not visited[v]:
                if self._is_cyclic_component(v, visited, in_rec_stack) == True:
                    return True
        return False

    def top_sort(self):
        visited = [False] * self.N
        ordering = [0] * self.N # topological ordering will be stored
        i = self.N - 1 # insert into the ordering array at this index

        for v in self.V:
            if not visited[v]:
                i = self._dfs(i, v, visited, ordering)
        return ordering

    def _dfs(self, i, v, visited, ordering):
        visited[v] = True
        for w in self.AL[v]: # for all the neighbours of v
            if not visited[w]:
                i = self._dfs(i, w, visited, ordering)
        ordering[i] = v
        return i - 1

    def longest_path_from(self, start_vertex):
        ordering = self.top_sort()
        dist = [None] * self.N  # longest distance
        dist[start_vertex] = 0
        max_dist = 0

        for v in ordering:
            if dist[v] != None: # v is reachable from start_vertex
                for w in self.AL[v]: # for all the neighbours of v
                    new_dist = dist[v] + 1
                    dist[w] = new_dist if dist[w] == None else max(dist[w], new_dist)
                    max_dist = max(max_dist, dist[w])
        return max_dist

# Input
N = int(input())
A = [None]
for i in range(1, N + 1):
    temp = [None] + [int(a) for a in input().split()]
    A.append(temp)


# convert A into a graph.
players = list(range(1, N + 1))

# List of vertices
# One vertex represents a combination of two players
V = [ set(v) for v in list(itertools.combinations(players, 2))]


G = DiGraph( N * (N - 1) // 2)
starting_vertices = set() # only need to examine longst path from these vertices

for i in range(1, N + 1): # for each player
    # for each game
    for j in range(1, N - 1):
        u = V.index({i, A[i][j]}) # convert a combination of two players to the index
        v = V.index({i, A[i][j + 1]})
        G.add_edge(u, v)
        if j == 1: # only the first game for each player
            starting_vertices.add(u)



if G.is_cyclic():
    result = -1
else:
    max_dist = 0
    for v in starting_vertices:
        max_dist = max(max_dist, G.longest_path_from(v))
    result = max_dist + 1

print(result)

Submission status: Time Limit Exceeded

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

games = dict()

next_player = [None] * (N+1)

for i in range(1, N+1):
    games[i] = deque([int(i) for i in input().split()])
    games[i].append(None)
    next_player[i] = games[i].popleft()

ans = 0
end = 0
while True:
    if end == N * (N-1):
        break
    # print(next_player)
    # print(games)
    # print(end)
    play = False
    change = []
    for i in range(1, N+1):
        if next_player[i] is None or i in change:
            continue
        if next_player[next_player[i]] == i:
            change.append(i)
            change.append(next_player[i])
            play = True
    if not play:
        ans = -1
        break
    for i in change:
        next_player[i] = games[i].popleft()
        end += 1
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

games = dict()

next_player = [None] * (N+1)

for i in range(1, N+1):
    games[i] = deque([int(i) for i in input().split()])
    games[i].append(None)
    next_player[i] = games[i].popleft()

ans = 0

while True:
    # print(next_player)
    # print(games)
    play = False
    change = []
    for i in range(1, N+1):
        if next_player[i] is None or i in change:
            continue
        if next_player[next_player[i]] == i:
            change.append(i)
            change.append(next_player[i])
            play = True
    if not play:
        ans = -1
        break
    for i in change:
        next_player[i] = games[i].popleft()
    ans += 1

    for i in range(N+1):
        if next_player[i] is not None:
            break
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

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

games = dict()

for i in range(1, N+1):
    games[i] = deque([int(i) for i in input().split()])
    games[i].append(None)

next_player = [None] * (N+1)
for i in range(1, N+1):
    next_player[i] = games[i].popleft()
ans = 0

while True:
    # print(next_player)
    # print(games)
    play = False
    change = []
    for i in range(1, N+1):
        if next_player[i] is None or i in change:
            continue
        if next_player[next_player[i]] == i:
            change.append(i)
            change.append(next_player[i])
            play = True
    if not play:
        ans = -1
        break
    for i in change:
        next_player[i] = games[i].popleft()
    ans += 1

    for i in range(N+1):
        if next_player[i] is not None:
            break
    else:
        break

print(ans)