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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        s, t = edge
        self.E[s].append(t)
        self.E[t].append(s)

        pass


def solve(N: int, A: "List[List[int]]"):
    a_head = [0]*N
    day = -1
    while True:
        day += 1
        g = Graph(N)
        flag = False
        # 構成
        for i, h in enumerate(a_head):
            if h == N-1:
                continue
            if A[i][h]-1 in g.E[i]:
                a_head[i] += 1
                a_head[g.E[i][0]] += 1
                flag = True
                # print(day, i, g.E[i][0])
            else:
                g.add_edge([i, A[i][h]-1])
            # print("E", g.E)
        if flag == False:
            break
    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        print(day)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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: 
      A[A[p][0]].pop(0)
      A[p].pop(0)
      cnt += 1
  if tmp == cnt:
    ans = -2
    break
  else:
    ans += 1
print(ans + 1)

Submission status: Wrong Answer

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

ans = -1
for idx, a_0_i in enumerate(A[0]):
    plyr_1_wish_day = idx
    plyr_other_wish_day = A[a_0_i - 1].index(1)
    if plyr_other_wish_day > plyr_1_wish_day:
        print(-1)
        break
    else:
        ans = max(plyr_1_wish_day, plyr_other_wish_day)
else:
    print(ans + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
ans = 1
cur = [0] * n
while all(x != n - 1 for x in cur):
    ok = False
    used = [False] * n
    for i in range(n):
        if cur[i] >= n - 1:
            continue
        j = a[i][cur[i]]
        if cur[j] >= n - 1:
            continue
        if not used[i] and not used[j] and i == a[j][cur[j]]:
            ok = True
            cur[i] += 1
            used[i] = True
            cur[j] += 1
            used[j] = True
    if ok:
        ans += 1
    else:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

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]*n
day=0
while 1:
    day+=1
    siaisuu=0
    for i in range(n):
        if now[i]==n-1:
            continue
        # print(i)
        nex=a[i][now[i]]
        # print(nex)
        # print(now)
        # print(a[nex-1][now[nex-1]])
        if i+1==a[nex-1][now[nex-1]] and i+1<nex:
            siaisuu+=1
            now[i]+=1
            now[nex-1]+=1
    if siaisuu==0:
        break

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

print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

# check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
check = [0] * N #i番目の次の相手のindex

ans = 0
i = 0
tmp = 0
while tmp < N + 5:
    if i == N:
        ans += 1
        i = 0
    if check[i] >= N - 1:
        i += 1
        tmp += 1
        continue
    b = A[i][check[i]]
    # print (b)
    if A[b - 1][check[b - 1]] - 1 == i: #試合できる時
        check[i] += 1
        check[b - 1] += 1
        tmp = 0
    i += 1
    tmp += 1
    # print (check)

# print (check)
for i in check:
    if i != N - 1:
        print (-1)
        exit()

print (ans)

Submission status: Wrong Answer

Solution code:
def topological_sort(E, D):
    D = D[:]
    n = len(E)
    Q = [i for i in range(n) if D[i] == 0]
    L = []
    while Q:
        p = Q.pop()
        L.append(p)
        for vf in E[p]:
            D[vf] -= 1
            if not D[vf]:
                Q.append(vf)
    
    if len(L) != n:
        return False
    return L

N = int(input())

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

Aidx = [None]*N

for i in range(N):
    d = [None]*N
    for j in range(N-1):
        aj = A[i][j]
        d[aj] = j
    Aidx[i] = d[:]

L = N*N
Edge = [[] for _ in range(L)]
Dim = [0]*L

for i in range(N):
    for j in range(i+1, N):
        t = i*N+j
        a = Aidx[i][j]
        if a != N-2:
            ki = A[i][a+1]
            if i > ki:
                ki, i = i, ki
            Edge[t].append(i*N + ki)
            Dim[i*N + ki] += 1
        b = Aidx[j][i]
        if b != N-2:
            kj = A[j][b+1]
            if kj > j:
                kj, j = j, kj
            Edge[t].append(kj*N + j)
            Dim[kj*N + j] += 1

order = topological_sort(Edge, Dim)

if order == False:
    print(-1)
else:
    ans = 1
    used = set()
    for k in order:
        i, j = divmod(k, N)
        if i >= j:
            continue
        if i in used or j in used:
            ans += 1
            used = set([i, j])
        else:
            used.add(i)
            used.add(j)
    print(ans)

Submission status: Wrong Answer

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

    now = [0] * N
    while True:
        nothing = True
        all_finish = True
        for i in range(N):
            if now[i] < N-1:
                all_finish = False
                want = a[i][now[i]] - 1
                if a[want][now[want]] - 1 == i:
                    now[want] += 1
                    now[i] += 1
                    nothing = False
        if all_finish:
            print(N)
            break
        if nothing:
            print(-1)
            break
    # print(now)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n = int(input())
a = [list(map(int, input().split()))[::-1] for _ in range(n)]
opponent = [-1 for _ in range(n)]
match = 0
day = 0
while match < n*(n-1)//2:
	approved = False
	for i in range(n):
		if a[i] != [] and opponent[i] == -1:
			opponent[i] = a[i].pop()-1
	#print(opponent)
	for i in range(n):
		if opponent[opponent[i]] == i:
			approved = True
			match += 1
			opponent[opponent[i]] = -1
			opponent[i] = -1
	if not approved:
		print(-1)
		sys.exit()
	day += 1
print(day)

Submission status: Wrong Answer

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

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

k = 0
while 1:
    used = set()
    for i,q in enumerate(A):
        if not q: continue
        if i in used: continue
        j = q[0]
        if j in used: continue
        if A[j][0] == i:
            A[j].popleft()
            A[i].popleft()
            used.add(i)
            used.add(j)
    if not used:
        print(-1)
        exit()
    if k >= N-1 and all(len(q)==0 for q in A):
        print(k+1)
        exit()
    k += 1

Submission status: Wrong Answer

Solution code:
#E問題
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
"""
for i in range(N):
    for j in range(N-1):
        A[i][j]-=1
"""
flag = 0
M = (N*(N+1))//2
for j in range(N-1):
    SUM = 0
    for i in range(N):
        SUM+=A[i][j]
    if SUM == M:
        flag = 1
        break
if flag == 1:
    print(-1)
else:
    print(N)

Submission status: Wrong Answer

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

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

for k in range(5000):
    used = set()
    for i,q in enumerate(A):
        if not q: continue
        if i in used: continue
        j = q[0]
        if j in used: continue
        if A[j][0] == i:
            A[j].popleft()
            A[i].popleft()
            used.add(i)
            used.add(j)
    if not used:
        print(-1)
        exit()
    if k >= N-1 and all(len(q)==0 for q in A):
        print(k+1)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N = int(input())
L = [deque([int(v) - 1 for v in input().split()]) for _ in range(N)]

t = (N ** 2 - N) // 2
ans = 1

def dfs():
    f = False
    for i in range(N):
        if len(L[i]) == 0:
            continue
        l = L[i].popleft()
        r = L[l].popleft()

        if i == r:
            f = True
        else:
            L[i].appendleft(l)
            L[l].appendleft(r)

    if f:
        global ans
        ans += 1
        dfs()

dfs()

le = max([len(v) for v in L])
if le == 0:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

n = int(input())
a = [list(map(int, input().split()))[::-1] for _ in range(n)]
opponent = [-1 for _ in range(n)]
match = 0
day = 0
while match < n*(n-1)//2:
	for i in range(n):
		if a[i] != [] and opponent[i] == -1:
			opponent[i] = a[i].pop()-1
	#print(opponent)
	for i in range(n):
		if opponent[opponent[i]] == i:
			match += 1
			opponent[opponent[i]] = -1
			opponent[i] = -1
	if opponent.count(-1)  == 0:
		print(-1)
		sys.exit()
	day += 1
print(day)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[List[int]]"):
    ret = 1
    p = [0] * N
    while True:
        used = [False] * N
        found = False
        for i in range(N):
            if p[i] < N - 1:
                pair = A[i][p[i]] - 1
                if not used[pair] and p[pair] < N - 1 and A[pair][p[pair]] - 1 == i:
                    used[i] = True
                    used[pair] = True
                    p[i] += 1
                    p[pair] += 1
                    found = True
        if not found:
            for i in range(N):
                if p[i] < N - 1:
                    print(-1)
                    return
            break
        ret += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ [ int(next(tokens)) for _ in range(N-1) ] for _ in range(N) ]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ABC139 E
from collections import deque

N=int(input())
match=[deque(list(map(int,input().split()))) for _ in [0]*N]

isFin=[]
finNum=0
index_queue=deque(list(range(N)))
day=1
while 1:
    todayFin=set(isFin)
    next_index_list=[]
    today_match=0
    while index_queue:
        i=index_queue.popleft()
        if not i in todayFin:
            opp=match[i][0]-1
            if not opp in todayFin:
                if match[opp][0]==(i+1):
                    # i+1とopp+1が試合をする
                    match[i].popleft()
                    match[opp].popleft()
                    todayFin.add(i)
                    todayFin.add(opp)
                    today_match+=1
                    next_index_list.append(i)
                    next_index_list.append(opp)
                    # 人i+1,opp+1が試合を終了したかどうか
                    if not match[i]:
                        isFin.append(i)
                        finNum+=1
                    if not match[opp]:
                        isFin.append(opp)
                        finNum+=1
    for i in next_index_list:
        index_queue.append(i)
    if today_match==0:
        # 条件の会う相手がいない
        day=-1
        break
    if finNum==N:
        # 全試合終了
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
# ABC139 E
from collections import deque

N=int(input())
match=[deque(list(map(int,input().split()))) for _ in [0]*N]

isFin=[]
finNum=0
index_list=list(range(N))
day=1
while 1:
    todayFin=set(isFin)
    next_index_list=[]
    today_match=0
    for i in index_list:
        if not i in todayFin:
            opp=match[i][0]-1
            if not opp in todayFin:
                if match[opp][0]==(i+1):
                    # i+1とopp+1が試合をする
                    match[i].popleft()
                    match[opp].popleft()
                    todayFin.add(i)
                    todayFin.add(opp)
                    today_match+=1
                    next_index_list.append(i)
                    next_index_list.append(opp)
                    # 人i+1,opp+1が試合を終了したかどうか
                    if not match[i]:
                        isFin.append(i)
                        finNum+=1
                    if not match[opp]:
                        isFin.append(opp)
                        finNum+=1
    index_list=next_index_list[:]
    if today_match==0:
        # 条件の会う相手がいない
        day=-1
        break
    if finNum==N:
        # 全試合終了
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input())

sched = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    sched.append(tmp)

index = {i:0 for i in range(N)}
# print(index)
ans = 0
while True:
    used = set()
    for i in range(N):
        if i in used or index[i] == N - 1:
            continue
        # print(i, index[i])
        pair = sched[i][index[i]] - 1
        if pair in used:
            continue
        if sched[pair][index[pair]] - 1 == i:
            index[i] += 1
            index[pair] += 1
            used.add(i)
            used.add(pair)
            
    if not used:
        break
    ans += 1

for i in range(N):
    if index[i] != N - 1:
        print(-1)
        sys.exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC139 E
from collections import deque

N=int(input())
match=[deque(list(map(int,input().split()))) for _ in [0]*N]

isFin=[]
finNum=0
day=1
while 1:
    todayFin=set(isFin)
    today_match=0
    for i in range(N):
        if not i in todayFin:
            opp=match[i][0]-1
            if not opp in todayFin:
                if match[opp][0]==(i+1):
                    # i+1とopp+1が試合をする
                    match[i].popleft()
                    match[opp].popleft()
                    todayFin.add(i)
                    todayFin.add(opp)
                    today_match+=1
                    # 人i+1,opp+1が試合を終了したかどうか
                    if not match[i]:
                        isFin.append(i)
                        finNum+=1
                    if not match[opp]:
                        isFin.append(opp)
                        finNum+=1
    if today_match==0:
        # 条件の会う相手がいない
        day=-1
        break
    if finNum==N:
        # 全試合終了
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
# ABC139 E

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

isFin=[]
finNum=0
day=1
while 1:
    todayFin=set(isFin)
    today_match=0
    for i in range(N):
        if not i in todayFin:
            opp=match[i][-1]-1
            if not opp in todayFin:
                if match[opp][-1]==(i+1):
                    # i+1とopp+1が試合をする
                    match[i].pop()
                    match[opp].pop()
                    todayFin.add(i)
                    todayFin.add(opp)
                    today_match+=1
                    # 人i+1,opp+1が試合を終了したかどうか
                    if not match[i]:
                        isFin.append(i)
                        finNum+=1
                    if not match[opp]:
                        isFin.append(opp)
                        finNum+=1
    if today_match==0:
        # 条件の会う相手がいない
        day=-1
        break
    if finNum==N:
        # 全試合終了
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
# ABC139 E

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

isFin=[0]*N
finNum=0
day=1
while 1:
    todayFin=isFin[:]
    today_match=0
    for i in range(N):
        if not todayFin[i]:
            opp=match[i][-1]-1
            if not todayFin[opp]:
                if match[opp][-1]==(i+1):
                    # i+1とopp+1が試合をする
                    match[i].pop()
                    match[opp].pop()
                    todayFin[i]=1
                    todayFin[opp]=1
                    today_match+=1
                    # 人i+1,opp+1が試合を終了したかどうか
                    if not match[i]:
                        isFin[i]=1
                        finNum+=1
                    if not match[opp]:
                        isFin[opp]=1
                        finNum+=1
    if today_match==0:
        # 条件の会う相手がいない
        day=-1
        break
    if finNum==N:
        # 全試合終了
        break
    day+=1
print(day)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000)

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

    #AR[i][j] => iにとって選手jとの試合が何番目か
    AR = [[]]
    for i in range(1,N+1):
        AR.append([0]*(N+1))
        for j in range(1,N):
            b = A[i][j]
            AR[i][b] = j

    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            edges[(i,j)] = []
            jForI = AR[i][j]
            if jForI < N-1:
                nxForI = A[i][jForI+1]
                edges[(i,j)].append((min(i,nxForI),max(i,nxForI)))
            iForJ = AR[j][i]
            if iForJ < N-1:
                nxForJ = A[j][iForJ+1]
                edges[(i,j)].append((min(j,nxForJ),max(j,nxForJ)))
    del A
    del AR

    steps = {}
    def dfs(i,j):
        #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
        if (i,j) not in steps:
            steps[(i,j)] = 0
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b)+1)
            steps[(i,j)] = res
        elif steps[(i,j)] == 0:
            print(-1)
            exit()
        return steps[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j))
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000)

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

    #AR[i][j] => iにとって選手jとの試合が何番目か
    AR = [[]]
    for i in range(1,N+1):
        AR.append([0]*(N+1))
        for j in range(1,N):
            b = A[i][j]
            AR[i][b] = j

    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            edges[(i,j)] = []
            jForI = AR[i][j]
            if jForI < N-1:
                nxForI = A[i][jForI+1]
                edges[(i,j)].append((min(i,nxForI),max(i,nxForI)))
            iForJ = AR[j][i]
            if iForJ < N-1:
                nxForJ = A[j][iForJ+1]
                edges[(i,j)].append((min(j,nxForJ),max(j,nxForJ)))

    steps = {}
    def dfs(i,j):
        #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
        if (i,j) not in steps:
            steps[(i,j)] = 0
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b)+1)
            steps[(i,j)] = res
        elif steps[(i,j)] == 0:
            print(-1)
            exit()
        return steps[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j))
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

#AR[i][j] => iにとって選手jとの試合が何番目か
AR = [[]]
for i in range(1,N+1):
    AR.append([0]*(N+1))
    for j in range(1,N):
        b = A[i][j]
        AR[i][b] = j

edges = {}
for i in range(1,N+1):
    for j in range(i+1,N+1):
        edges[(i,j)] = []
        jForI = AR[i][j]
        if jForI < N-1:
            nxForI = A[i][jForI+1]
            edges[(i,j)].append((min(i,nxForI),max(i,nxForI)))
        iForJ = AR[j][i]
        if iForJ < N-1:
            nxForJ = A[j][iForJ+1]
            edges[(i,j)].append((min(j,nxForJ),max(j,nxForJ)))

steps = {}
def dfs(i,j):
    #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
    if (i,j) not in steps:
        steps[(i,j)] = 0
        res = 1
        for a,b in edges[(i,j)]:
            res = max(res,dfs(a,b)+1)
        steps[(i,j)] = res
    elif steps[(i,j)] == 0:
        print(-1)
        exit()
    return steps[(i,j)]

ans = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        ans = max(ans,dfs(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import math
import itertools
from collections import deque
import copy

# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    L = [[] for _ in range(N + 1)]

    for j in range(N):
        a = list(map(int, input().split()))
        L[j + 1] = deque(a)

    f_original = [False] * (N + 1)
    f = [False] * (N + 1)
    k =0

    pre_revise =set(range(N+1))
    current_revise =set(range(N+1))
    while k<500001: # １日分の作業

        f =[False] * (N + 1)
        pre_revise =copy.copy(current_revise)
        current_revise =set()

        for i in pre_revise: #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and f[can] is False and f[i] is False:
                L[i].popleft()
                L[can].popleft()
                f[i] = True
                f[can] = True
                current_revise.add(i)
                current_revise.add(can)
        k += 1
        if f == f_original:
            break

    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import math
import itertools
from collections import deque


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    L = [[] for _ in range(N + 1)]

    for i in range(N):
        a = list(map(int, input().split()))
        L[i + 1] = deque(a)

    f_original = [False] * (N + 1)
    f = [False] * (N + 1)
    k = 0
    while k<500000: # １日分の作業
        f =[False] * (N + 1)
        for i in range(1, N + 1): #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and f[can] is False and f[i]is False:
                L[i].popleft()
                L[can].popleft()
                f[i] = True
                f[can] = True
        k += 1
        if f == f_original:
            break

    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import math
import itertools
from collections import deque


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    L = [[] for _ in range(N + 1)]

    for i in range(N):
        a = list(map(int, input().split()))
        L[i + 1] = deque(a)

    f_original = [False] * (N + 1)
    f = [False] * (N + 1)
    k = 0
    while True: # １日分の作業
        f =[False] * (N + 1)
        for i in range(1, N + 1): #一人分の作業
            if not L[i]:
                continue
            can = L[i][0]
            if L[can][0] == i and f[can] is False and f[i]is False:
                L[i].popleft()
                L[can].popleft()
                f[i] = True
                f[can] = True
        k += 1
        if f == f_original:
            break

    for i in range(N + 1):
        if len(L[i])>0:
            print(-1)
            exit()

    print(k-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = defaultdict(set)

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v].add(u)
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = len(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                # if v in done:
                #     continue
                rg[v].remove(u)
                if len(rg[v]) == 0:
                    ns.append(v)
                    done += 1
        s = ns

    if done != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = defaultdict(set)

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v].add(u)
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = set(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                if v in done:
                    continue
                rg[v].remove(u)
                if len(rg[v]) == 0:
                    ns.append(v)
                    done.add(v)
        s = ns

    if len(done) != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()