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
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
    n = int(input())
    A = [list(map(int,input().split())) for _ in range(n)]

    cnt = [0]*(n+1)

    league = [[[n,n] for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n-1):
            enemy = A[i][j] - 1
            league[i][enemy][0] = j
            league[enemy][i][1] = j

    memo = [[1e100]*(n-1) for _ in range(n)]
    check = set()

    def dfs(i,k):
        ' i人目のk試合目が行われる日程 '
        if i*n + k + 1 in check and memo[i][k] == 1e100:
            print(-1)
            exit(0)
        check.add(i*n + k + 1)
        j = A[i][k] - 1
        l = league[i][j][1]
        if k == l == 0:
            memo[i][k] = 1
            memo[j][l] = 1
            return 1
        elif k == 0:
            memo[i][k] = dfs(j,l - 1) + 1
            memo[j][l] = memo[i][k]
            return memo[i][k]
        elif l == 0: 
            memo[i][k] = dfs(i,k - 1) + 1
            memo[j][l] = memo[i][k]
            return memo[i][k]
        else:
            memo[i][k] = max(dfs(i,k-1),dfs(j,l - 1)) + 1
            memo[j][l] = memo[i][k]
            return memo[i][k]

    ans = 0
    for i in range(n):
        ans  = max(ans, dfs(i,n-2))
    print(ans)

main()

Submission status: Time Limit Exceeded

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

from collections import deque

def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = deque()
    for i in range(n):
        ai = list(map(int, input().split()))
        for j in range(n - 1):
            x = min(i, ai[j] - 1)
            y = max(i, ai[j] - 1)
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1] - 1)
                yp = max(i, ai[j - 1] - 1)
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = deque()
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        if res+1 > dp[x]:
            dp[x] = res+1
        #dp[x] = max(dp[x], res+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1]*allv
done = [False]*allv
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    if res > ans:
        ans = res
    #ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], res+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1]*allv
done = [False]*allv
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 5
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(-1)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def main():
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > 10**6:
			print(-1)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def main():
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
			break
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > 10**7:
			print(-1)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
def main():
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
			break
		ans += 1

		if count == n*(n-1)//2:
			break
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
a = []
for _ in range(n):
	a.append(tuple(map(int,input().split())))
a = tuple(a)

play = [0 for _ in range(n)]
flag = [True for _ in range(n)]
count = 0
ans = 0
while True:
	break_flag = True
	for i in range(n):
		if flag[i]:
			num = a[i][play[i]]-1
			if flag[num] and a[num][play[num]]-1 == i:
				play[num] += 1
				play[i] += 1
				flag[num] = False
				flag[i] = False
				break_flag = False
				count += 1
	if break_flag:
		print(-1)
		sys.exit()
		break
	ans += 1
	if count == n*(n-1)//2:
		break
	for i in range(n):
		if play[i] < n-1:
			flag[i] = True
		else:
			flag[i] = False

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

Submission status: Time Limit Exceeded

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

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

play = [0 for _ in range(n)]
flag = [True for _ in range(n)]
count = 0
ans = 0
while True:
	break_flag = True
	for i in range(n):
		if flag[i]:
			num = a[i][play[i]]-1
			if flag[num] and a[num][play[num]]-1 == i:
				play[num] += 1
				play[i] += 1
				flag[num] = False
				flag[i] = False
				break_flag = False
				count += 1
	if break_flag:
		print(-1)
		sys.exit()
		break
	ans += 1
	if count == n*(n-1)//2:
		break
	for i in range(n):
		if play[i] < n-1:
			flag[i] = True
		else:
			flag[i] = False

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
while True:
    if day >= N*(N-1)//2+10 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=N*(N-1)//2+10:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
while True:
    if day >= N*(N-1)//2+10 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=N*(N-1)//2+10:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
l = [0 for i in range(n)]
ans = 0
for i in range(n):
    a_ = list(map(int, input().split()))[::-1]
    a_ = [x-1 for x in a_]
    a.append(a_)
rem = n*(n-1)
while True:
    tmp = False
    ans += 1
    l = list()
    for i in range(n):
        if a[i] and a[a[i][-1]] and a[a[i][-1]][-1] == i:
            tmp = True
            rem -= 1
            l.append(i)
    for i in range(len(l)):
        a[l[i]].pop()
    if not tmp:
        ans = -1
        break
    if rem == 0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
l = [0 for i in range(n)]
ans = 0
for i in range(n):
    a_ = list(map(int, input().split()))
    a_ = [x-1 for x in a_]
    a.append(a_)
for _ in range(n*(n-1)//2):
    ans += 1
    l_tmp = list(l)
    for i in range(n):
        if l_tmp[i] == n-1:
            continue
        if l_tmp[a[i][l_tmp[i]]] == n-1:
            continue
        if a[a[i][l_tmp[i]]][l_tmp[a[i][l_tmp[i]]]] == i:
            l[i] += 1
    if l == [n-1 for i in range(n)]:
        break
if l != [n-1 for i in range(n)]:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
a = []
l = [0 for i in range(n)]
ans = 0
for i in range(n):
    a_ = list(map(int, input().split()))
    a_ = deque([x-1 for x in a_])
    a.append(a_)
for _ in range(n*n):
    ans += 1
    l = []
    for i in range(n):
        if len(a[i]) == 0:
            continue
        if len(a[a[i][0]]) == 0:
            continue
        if a[a[i][0]][0] == i:
            l.append(i)
    for i in range(len(l)):
        a[l[i]].popleft()
    if a == [deque([]) for i in range(n)]:
        break
if a != [deque([]) for i in range(n)]:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
l = [0 for i in range(n)]
ans = 0
for i in range(n):
    a_ = list(map(int, input().split()))
    a_ = [x-1 for x in a_]
    a.append(a_)
for _ in range(n*n):
    ans += 1
    l_tmp = list(l)
    for i in range(n):
        if l[i] == n-1:
            continue
        if a[a[i][l_tmp[i]]][l_tmp[a[i][l_tmp[i]]]] == i:
            l[i] += 1
    if l == [n-1 for i in range(n)]:
        break
if l != [n-1 for i in range(n)]:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
G = {(i,j):[0,[]] for i in range(1,N) for j in range(i+1,N+1)}
for i in range(N):
    a = A[i][0]
    for j in range(1,N-1):
        b = A[i][j]
        G[(min(i+1,a),max(i+1,a))][1].append((min(i+1,b),max(i+1,b)))
        G[(min(i+1,b),max(i+1,b))][0] += 1
        a = b
hist = {(i,j):0 for i in range(N) for j in range(i+1,N+1)}
heap = deque([])
for i in range(1,N):
    for j in range(i+1,N+1):
        if G[(i,j)][0]==0:
            heap.append(((i,j),1))
            hist[(i,j)] = 1
cnt = 0
while heap:
    (i,j),d = heap.popleft()
    cnt = max(cnt,d)
    for k,l in G[(i,j)][1]:
        if hist[(k,l)]==0:
            G[(k,l)][0] -= 1
            if G[(k,l)][0]==0:
                heap.append(((k,l),d+1))
                hist[(k,l)] = 1
tot = 0
for i in range(1,N):
    for j in range(i+1,N+1):
        tot += hist[(i,j)]
if tot==(N*(N-1))//2:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = 1
    count = [0]*n
    check = set()
    game = []
    for i in range(n):
        if count[i] >= n-1 or i in check:
            continue
        ind = l[i][count[i]]-1
        if ind in check:
            continue
        if l[ind].index(i+1) == count[ind]:
            check |= set([i,ind])
            game.append([i,ind])
            count[i] += 1
            count[ind] += 1
    while True:
        gamepre = game
        check = set()
        game = []
        for i,j in gamepre:
            ci = True
            cj = True
            if count[i] >= n-1 or i in check:
                ci = False
            if count[j] >= n-1 or j in check:
                cj = False
            if ci:
                ci = True
                ind = l[i][count[i]]-1
                if ind in check:
                    ci = False
                if ci and l[ind].index(i+1) == count[ind]:
                    check |= set([i,ind])
                    game.append([i,ind])
                    count[i] += 1
                    count[ind] += 1
            if cj:
                cj = True
                ind = l[j][count[j]]-1
                if ind in check:
                    cj = False
                if cj and l[ind].index(j+1) == count[ind]:
                    check |= set([j,ind])
                    game.append([j,ind])
                    count[j] += 1
                    count[ind] += 1
        if not check:
            if sum(count) != n*(n-1):
                print(-1)
                exit()
            else:
                print(ans)
                exit()
        ans += 1
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    v = n*(n-1)//2
    E = [[] for i in range(v)]
    dic = {}
    c = 0
    for i in range(n):
        for j in range(n-1):
            a,b = i,l[i][j]-1
            if a > b:
                a,b = b,a
            if (a,b) in dic:
                l[i][j] = dic[(a,b)]
            else:
                dic[(a,b)] = c
                l[i][j] = dic[(a,b)]
                c += 1
        for j in range(n-2):
            E[l[i][j]].append(l[i][j+1])

    def dfs(i):
        if visit[i]:
            if dis[i] == -1:
                return -1
            else:
                return dis[i]
        visit[i] = True
        d = 1
        for nex in E[i]:
            res = dfs(nex)
            if res == -1:
                return -1
            d = max(d,res+1)

        dis[i] = d
        return d
    ans = 0
    done = []
    for i in range(n):
        if l[i][0] in done:
            continue
        visit = [False]*v
        dis = [-1]*v
        count = dfs(l[i][0])
        if count == -1:
            print(-1)
            exit()
        else:
            ans = max(ans,count)
        done.append(l[i][0])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = 0
    count = [0]*n

    while True:
        check = set()
        for i in range(n):
            if count[i] >= n-1 or i in check:
                continue
            ind = l[i][count[i]]-1
            if ind in check:
                continue
            if l[ind].index(i+1) == count[ind]:
                check |= set([i,ind])
                count[i] += 1
                count[ind] += 1
        if not check:
            if sum(count) != n*(n-1):
                print(-1)
                exit()
            else:
                print(ans)
                exit()
        ans += 1
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = 0
    count = [0]*n

    while True:
        check = set()
        for i in range(n):
            if count[i] >= n-1:
                continue
            ind = l[i][count[i]]-1
            if l[ind].index(i+1) == count[ind]:
                if (not i in check) and (not ind in check): 
                    check.add(i)
                    check.add(ind)
                    count[i] += 1
                    count[ind] += 1
        if not check:
            if sum(count) != n*(n-1):
                print(-1)
                exit()
            else:
                print(ans)
                exit()
        ans += 1
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
ans = 0
count = [0]*n

while True:
    check = set()
    for i in range(n):
        if count[i] >= n-1:
            continue
        ind = l[i][count[i]]-1
        if l[ind].index(i+1) == count[ind]:
            if (not i in check) and (not ind in check): 
                check.add(i)
                check.add(ind)
                count[i] += 1
                count[ind] += 1
    if not check:
        if sum(count) != n*(n-1):
            print(-1)
            exit()
        else:
            print(ans)
            exit()
    ans += 1

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
	
n = int(input())
idlist = [[0 for _ in range(n)] for _ in range(n)]
x = 0
for i in range(n):
	for j in range(n):
		if i < j:
			x += 1
			idlist[i][j] = x
a = [list(map(int, input().split())) for _ in range(n)]
gid = [[0 for _ in range(n-1)] for _ in range(n)]
for i in range(n): #試合idのリスト
	for j in range(n-1):
		if a[i][j]-1 > i:
			gid[i][j] = idlist[i][a[i][j]-1]
		else:
			gid[i][j] = idlist[a[i][j]-1][i]

#print(idlist) #test
#print(gid) #test

l = n*(n-1)//2 + 1
branch = [[] for _ in range(l)]
for i in range(n):
	for j in range(n-2):
		branch[gid[i][j]].append(gid[i][j+1])

#print(branch) #test

reached = [False for _ in range(l)]
calculated = [False for _ in range(l)]
dp = [1 for _ in range(l)]

def dfs(v):
	if reached[v]:
		if not calculated[v]:
			return -1
	reached[v] = True
	for u in branch[v]:
		w = dfs(u)
		if w == -1:
			return -1
		dp[v] = max(dp[v], w+1)
	calculated[v] = True
	return dp[v]

ans = 0
for i in range(1, l):
	q = dfs(i)
	if q == -1:
		ans = -1
		break
	else:
		ans = max(ans, q)
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
idlist = [[0 for _ in range(n)] for _ in range(n)]
x = 0
for i in range(n):
	for j in range(n):
		if i < j:
			x += 1
			idlist[i][j] = x
a = [list(map(int, input().split())) for _ in range(n)]
gid = [[0 for _ in range(n-1)] for _ in range(n)]
for i in range(n): #試合idのリスト
	for j in range(n-1):
		if a[i][j]-1 > i:
			gid[i][j] = idlist[i][a[i][j]-1]
		else:
			gid[i][j] = idlist[a[i][j]-1][i]

#print(idlist) #test
#print(gid) #test

l = n*(n-1)//2 + 1
branch = [[] for _ in range(l)]
for i in range(n):
	for j in range(n-2):
		branch[gid[i][j]].append(gid[i][j+1])

#print(branch) #test

reached = [False for _ in range(l)]
calculated = [False for _ in range(l)]
dp = [1 for _ in range(l)]

def dfs(v):
	if reached[v]:
		if not calculated[v]:
			return -1
	reached[v] = True
	for u in branch[v]:
		w = dfs(u)
		if w == -1:
			return -1
		dp[v] = max(dp[v], w+1)
	calculated[v] = True
	return dp[v]

ans = 0
for i in range(1, l):
	q = dfs(i)
	if q == -1:
		ans = -1
		break
	else:
		ans = max(ans, q)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
import collections
edge=collections.defaultdict(list)
idg=collections.defaultdict(int)
for i in range(1,n+1):
    l=list(map(int,input().split()))
    for j,k in zip(l,l[1:]):
        if i>k:
            x=(k,i)
        else:
            x=(i,k)
        if i>j:
            y=(j,i)
        else:
            y=(i,j)
        edge[y].append(x)
        idg[x]+=1
s=set()
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if idg[(i,j)]==0:
            s.add((i,j))
ans=0
i=0
while s:
    i+=len(s)
    l=s
    s=set()
    for j in l:
        for k in edge[j]:
            idg[k]-=1
            if idg[k]==0:
                s.add(k)
    ans+=1
if i<n*(n-1)//2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
edge={}
idg={}
for i in range(1,n+1):
    l=list(map(int,input().split()))
    for j,k in zip(l,l[1:]):
        try:
            edge[tuple(sorted([i,j]))].append(tuple(sorted([i,k])))
        except:
            edge[tuple(sorted([i,j]))]=[tuple(sorted([i,k]))]
        try:
            idg[tuple(sorted([i,k]))]+=1
        except:
            idg[tuple(sorted([i,k]))]=1
s=set()
for i in range(1,n+1):
    for j in range(i+1,n+1):
        try:
            idg[(i,j)]
        except:
            s.add((i,j))
ans=0
i=0
while s:
    i+=len(s)
    l=s
    s=set()
    for j in l:
        try:
            for k in edge[j]:
                idg[k]-=1
                if idg[k]==0:
                    s.add(k)
        except:
            continue
    ans+=1
if i<n*(n-1)//2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
import collections
edge=collections.defaultdict(list)
idg=collections.defaultdict(int)
for i in range(1,n+1):
    l=list(map(int,input().split()))
    for j,k in zip(l,l[1:]):
        edge[tuple(sorted([i,j]))].append(tuple(sorted([i,k])))
        idg[tuple(sorted([i,k]))]+=1
s=set()
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if idg[(i,j)]==0:
            s.add((i,j))
ans=0
i=0
while s:
    i+=len(s)
    l=s
    s=set()
    for j in l:
        for k in edge[j]:
            idg[k]-=1
            if idg[k]==0:
                s.add(k)
    ans+=1
if i<n*(n-1)//2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import collections
edge=collections.defaultdict(list)
idg=collections.defaultdict(int)
for i in range(1,n+1):
    l=list(map(int,input().split()))
    for j,k in zip(l,l[1:]):
        edge[tuple(sorted([i,j]))].append(tuple(sorted([i,k])))
        idg[tuple(sorted([i,k]))]+=1
s=set()
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if idg[(i,j)]==0:
            s.add((i,j))
ans=0
i=0
while i<n*(n-1)//2 and s:
    i+=len(s)
    l=s
    s=set()
    for j in l:
        for k in edge[j]:
            idg[k]-=1
            if idg[k]==0:
                s.add(k)
    ans+=1
if i<n*(n-1)//2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}

for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
q=set([])
flag={n:0 for n in node}
for key in node:
    if not _from[key]:
        q.add(key)
sub=set([])
while q:
    while q:
        x=q.pop()
        for n in _to[x]:
            flag[n]+=1
            if flag[n]==len(_from[n]):
                sub.add(n)
        if not q:
            q=sub
            sub=set([])
            day+=1
            break
able=True
for n in node:
    if flag[n]!=len(_from[n]):
        able=False
if able:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}


for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
conduct=set([])
subconduct=set([])
q=set([])
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.add(key)
sub=set([])
while q:
    while q:
        x=q.pop()
        for n in _to[x]:
            if conduct>=_from[n]:
                subconduct.add(n)
                sub.add(n)
        if not q:
            q=sub
            sub=set([])
            for i in subconduct:
                conduct.add(i)
            subconduct=set([])
            day+=1
            break

if conduct==set(node):
    print(day)
else:
    print(-1)