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:
# atcoder problems solving
# League
from collections import deque
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    graph = {(i, j): [] for i in range(1, N+1) for j in range(i+1, N+1)}
    indegree = {(i, j): 0 for i in range(1, N+1) for j in range(i+1, N+1)}

    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N-2):
            x, y = a[j], a[j+1]
            z, w = i+1, i+1
            graph[(min(z, x), max(z, x))].append((min(w, y), max(w, y)))
            indegree[(min(w, y), max(w, y))] += 1

    d = deque()
    e = deque()
    visited = {(i, j): False for i in range(1, N+1) for j in range(i+1, N+1)}

    cnt = 1
    match = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if indegree[(i, j)] == 0:
                d.append((i, j))
                visited[(i, j)] = True
                match += 1

    while d:
        while d:
            x = d.popleft()
            for node in graph[x]:
                indegree[node] -= 1
                if indegree[node] == 0:
                    e.append(node)
                    visited[node] = True
                    match += 1
        if e:
            d = e
            e = deque()
            cnt += 1

    if match == N*(N-1)//2:
        print(cnt)
    else:
        print(-1)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# atcoder problems solving
# League
import sys
input= sys.stdin.readline
from collections import deque
N = int(input())
graph = {(i, j): [] for i in range(1, N+1) for j in range(i+1, N+1)}
indegree = {(i, j): 0 for i in range(1, N+1) for j in range(i+1, N+1)}

for i in range(N):
    a = list(map(int, input().split()))
    for j in range(N-2):
        x, y = a[j], a[j+1]
        z, w = i+1, i+1
        graph[(min(z,x),max(z, x))].append((min(w,y),max(w, y)))
        indegree[(min(w,y),max( w,y))] += 1

d = deque()
e = deque()
visited = {(i, j): False for i in range(1, N+1) for j in range(i+1, N+1)}
cnt = 1
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if indegree[(i, j)] == 0:
            d.append((i, j))
            visited[(i, j)] = True
while d:
    while d:
        x = d.popleft()
        for node in graph[x]:
            indegree[node] -= 1
            if indegree[node] == 0:
                e.append(node)
                visited[node]=True
    if e:
        d = e
        e = deque()
        cnt += 1
flag = bool(all(visited[(i, j)] == True for i in range(1, N+1)
                for j in range(i+1, N+1)))

if flag:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#  atcoder problems solving
# League
from collections import deque
N = int(input())
graph = {(i, j): [] for i in range(1, N+1) for j in range(i+1, N+1)}
indegree = {(i, j): 0 for i in range(1, N+1) for j in range(i+1, N+1)}
# i<jを満たすノードを導入する
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(N-2):
        x, y = a[j], a[j+1]
        z, w = i+1, i+1
        graph[(min(z,x),max(z, x))].append((min(w,y),max(w, y)))
        indegree[(min(w,y),max( w,y))] += 1

d = deque()
e = deque()
visited = {(i, j): False for i in range(1, N+1) for j in range(i+1, N+1)}
cnt = 1
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if indegree[(i, j)] == 0:
            d.append((i, j))
            visited[(i, j)] = True
while d:
    while d:
        x = d.popleft()
        for node in graph[x]:
            indegree[node] -= 1
            if indegree[node] == 0:
                e.append(node)
                visited[node]=True
    if e:
        d = e
        e = deque()
        cnt += 1
flag = bool(all(visited[(i, j)] == True for i in range(1, N+1)
                for j in range(i+1, N+1)))

if flag:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque([]) for _ in range(n+1)]
for i in range(1,n+1):
    a[i].extend(list(map(int,input().split())))

ans=0
all_num=n*(n-1)//2
battled_num=0
while(True):
    used=[False for _ in range(n+1)]
    changeflag=False
    for i in range(1,n+1):
        if(len(a[i])==0):
            continue
        else:
            j=a[i][0]

            if(used[i] or used[j]):
                continue
            else:
                aj_first=a[j][0]

                if(i==aj_first):
                    a[i].popleft()
                    a[j].popleft()
                    used[i]=True
                    used[j]=True
                    battled_num+=1
                    changeflag=True

    if(battled_num>=all_num):
        ans+=1
        print(ans)
        break
    elif(not changeflag):
        print(-1)
        break
    else:
        ans+=1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = list(deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N))
# print(A)
ans = 0
change = True
while True:
    change = False
    match = [-1] * N
    for player in range(N):
        if not A[player]:
            continue
        enemy = A[player][0]
        match[player] = enemy
        if match[enemy] == player:
            A[player].popleft()
            A[enemy].popleft()
            change = True
    if not change:
        break
    ans += 1


if all(len(row) == 0 for row in A):
    print(ans)
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque([]) for _ in range(n+1)]
for i in range(1,n+1):
    a[i].extend(list(map(int,input().split())))

ans=0
while(True):
    used=[False for _ in range(n+1)]
    changeflag=False
    emptynum=0
    for i in range(1,n+1):
        if(len(a[i])==0):
            emptynum+=1
        else:
            j=a[i][0]

            if(used[i] or used[j]):
                continue
            else:
                aj_first=a[j][0]

                if(i==aj_first):
                    a[i].popleft()
                    a[j].popleft()
                    used[i]=True
                    used[j]=True
                    changeflag=True

    if(emptynum>=n):
        print(ans)
        break
    elif(not changeflag):
        print(-1)
        break
    else:
        ans+=1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = list(deque(map(int, input().split())) for _ in range(N))
for i in range(N):
    A[i] = deque(map(lambda x: x - 1, A[i]))
# print(A)
ans = 0
change = True
while True:
    change = False
    work = [-1] * N
    for i in range(N):
        if not A[i]:
            continue
        enemy = A[i][0]
        work[i] = enemy
        if work[enemy] == i:
            A[i].popleft()
            A[enemy].popleft()
            change = True
    if not change:
        break
    ans += 1


empty = True
for row in A:
    if row:
        empty = False
if not empty:
    print('-1')
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque([]) for _ in range(n)]
for i in range(n):
    a[i].extend(list(map(int,input().split())))

ans=0
while(True):
    used=[False for _ in range(n)]
    changeflag=False
    emptynum=0
    for i in range(n):
        if(len(a[i])==0):
            emptynum+=1
        else:
            ai_first=a[i].popleft()
            j=ai_first-1
            if(used[j]):
                a[i].appendleft(ai_first)
            else:
                aj_first=a[j].popleft()

                if(i!=aj_first-1 or used[aj_first-1]):
                    a[i].appendleft(ai_first)
                    a[j].appendleft(aj_first)
                else:
                    used[i]=True
                    used[j]=True
                    changeflag=True

    if(emptynum>=n):
        print(ans)
        break
    elif(not changeflag):
        print(-1)
        break
    else:
        ans+=1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = list(deque(map(int, input().split())) for _ in range(N))
for i in range(N):
    for j in range(N - 1):
        A[i][j] -= 1

ans = 0
change = True
while change:
    change = False
    work = [-1] * N
    for i in range(N):
        if not A[i]:
            continue
        enemy = A[i][0]
        work[i] = enemy
        if work[work[i]] == i:
            A[i].popleft()
            A[enemy].popleft()
            change = True
    if not change:
        break
    ans += 1


empty = True
for row in A:
    if row:
        empty = False
if not empty:
    print('-1')
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque([]) for _ in range(n)]
for i in range(n):
    a[i].extend(list(map(int,input().split())))

ans=0
while(True):
    used=[False]*n
    changeflag=False
    emptynum=0
    for i in range(n):
        if(len(a[i])==0):
            emptynum+=1
        else:
            ai_first=a[i].popleft()
            if(used[ai_first-1]):
                a[i].appendleft(ai_first)
            else:
                aj_first=a[ai_first-1].popleft()

                if(i!=aj_first-1 or used[aj_first-1]):
                    a[i].appendleft(ai_first)
                    a[ai_first-1].appendleft(aj_first)
                else:
                    used[i]=True
                    used[ai_first-1]=True
                    changeflag=True

    if(emptynum>=n):
        print(ans)
        break
    elif(not changeflag):
        print(-1)
        break
    else:
        ans+=1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from time import time

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

canBattle = [-1] * N
D = [0] * N

while True:
    if not A:
        print(max(D))
        exit()

    i, a = A.popleft()
    if not a:
        continue
    if canBattle[i] != -1:
        A.append((i, a))
        continue
    j = a.popleft()

    if canBattle[j] == i:
        d = max(D[i], D[j])
        D[i], D[j] = d + 1, d + 1
        canBattle[i] = -1
        canBattle[j] = -1
    else:
        canBattle[i] = j

    if a:
        A.append((i, a))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

input = sys.stdin.buffer.readline
n = int(input())
AA = [deque(list(map(int, input().split()))) for _ in range(n)]
max_n = n * (n - 1) // 2
cnt = 0
ans = -1
shuryo = False
for d in range(1, n * (n - 1) // 2 + 1):
    used = [False] * (n)
    update = False
    for i in range(n):
        if used[i] is True:
            continue
        if not AA[i]:
            continue
        aite = AA[i][0] - 1
        if used[aite] is True:
            continue
        if not AA[aite]:
            continue
        if AA[aite][0] - 1 == i:
            AA[i].popleft()
            AA[aite].popleft()
            used[aite] = True
            used[i] = True
            cnt += 1
            update = True
    if cnt == max_n:
        shuryo = True
        break
    if update is False:
        break
    if shuryo:
        break
if shuryo:
    ans = d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
AA = [deque(list(map(int, input().split()))) for _ in range(n)]
max_n = n * (n - 1) // 2
cnt = 0
ans = -1
shuryo = False
for d in range(1, n * n):
    used = [False] * (n)
    update = False
    for i in range(n):
        if used[i] is True:
            continue
        if not AA[i]:
            continue
        aite = AA[i][0] - 1
        if used[aite] is True:
            continue
        if not AA[aite]:
            continue
        if AA[aite][0] - 1 == i:
            AA[i].popleft()
            AA[aite].popleft()
            used[aite] = True
            used[i] = True
            cnt += 1
            update = True

        if cnt == max_n:
            shuryo = True
            break
    if update is False:
        break

    if shuryo:
        break
if shuryo:
    ans = d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
AA = [deque(list(map(int, input().split()))) for _ in range(n)]
max_n = n * (n - 1) // 2
cnt = 0
ans = -1
shuryo = False
for d in range(1, n * n):
    used = [False] * (n)
    for i in range(n):
        if used[i] is True:
            continue
        if not AA[i]:
            continue
        aite = AA[i][0] - 1
        if used[aite] is True:
            continue
        if not AA[aite]:
            continue
        if AA[aite][0] - 1 == i:
            AA[i].popleft()
            AA[aite].popleft()
            used[aite] = True
            used[i] = True
            cnt += 1

        if cnt == max_n:
            shuryo = True
            break

    if shuryo:
        break
if shuryo:
    ans = d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1.800:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1.900:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1950:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1900:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1950:
        print(N * (N - 1) // 2)
    if not isChanged:
        break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

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

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

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

canBattle = defaultdict(lambda: False)
D = [0] * N

for day in range(N**2):
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
calc=lambda u,v:min(u,v)*n+max(u,v)
edge=[[]for _ in range(n*n)]
for i in range(n):
  for j in range(1,n-1):
    u,v=calc(a[i][j-1]-1,i),calc(a[i][j]-1,i)
    edge[u].append(v)
from collections import deque
def find_loop(n,e):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  return t
d=find_loop(n*n,edge)
if len(d)!=n*n:exit(print(-1))
c=[1]*n*n
for i in d:
  for j in edge[i]:
    c[j]=c[i]+1
print(max(c))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
q = deque([])

# 選手iが試合ができるかをチェックして、できるならばキューに入れる
def check(i, q):
  if len(A[i]) == 0:
    return
  j = A[i][-1]
  if len(A[j]) == 0:
    return
  if A[j][-1] == i:
    if i > j:
      i, j = j, i
    q.append((i, j))
  return 

for i in range(N):
  check(i, q)

day = 0
while q:
  day += 1
  q = set(sorted(q))
  prev = deque([])
  prev, q = q, prev
  for i, j in prev:
    A[i].pop(-1)
    A[j].pop(-1)
  for i, j in prev:
    check(i, q)
    check(j, q)
  
for i in range(N):
  if len(A[i]) != 0:
    print(-1)
    exit()

print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import copy

def main():
  input = sys.stdin.readline
  n = int(input())
  a = [None]*n
  for i in range(n):
    a[i] = [int(x)-1 for x in input().split()]
  
  count = 0
  ans = 0
  bef_checked = [int(x) for x in range(n)]
  index = [0]*n
  while True:
    ans += 1
    check = copy.deepcopy(bef_checked)
    bef_checked = []
    already = set()
    flag = True
    for v in check:
      if v in already:
        continue
      flag = False
      v2 = a[v][index[v]]
      if v2 in already:
        continue
      if v != a[v2][index[v2]]:
        continue
      already = already|{v, v2}
      index[v] += 1
      index[v2] += 1
      if index[v] == n-1:
        count += 1
      else:
        bef_checked.append(v)
      if index[v2] == n-1:
        count += 1
      else:
        bef_checked.append(v2)
        
    if flag:
      print(-1)
      sys.exit()
    if count == n:
      break
  print(ans)

  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import copy

def main():
  input = sys.stdin.readline
  n = int(input())
  a = [None]*n
  for i in range(n):
    a[i] = [int(x)-1 for x in input().split()]
  
  count = 0
  ans = 0
  bef_checked = [int(x) for x in range(n)]
  index = [0]*n
  while True:
    ans += 1
    check = copy.deepcopy(bef_checked)
    bef_checked = []
    already = set()
    flag = True
    for v in check:
      if v in already:
        continue
      flag = False
      v2 = a[v][index[v]]
      if v2 in already:
        continue
      if v != a[v2][index[v2]]:
        continue
      already = already|{v, v2}
      index[v] += 1
      index[v2] += 1
      if index[v] == n-1:
        count += 1
      else:
        bef_checked.append(v)
      if index[v2] == n-1:
        count += 1
      else:
        bef_checked.append(v2)
        
    if flag:
      print(-1)
      sys.exit()
    if count == n:
      break
  
  print(ans)
  

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import copy

def main():
  input = sys.stdin.readline
  n = int(input())
  a = [None]*n
  for i in range(n):
    a[i] = [int(x)-1 for x in input().split()]
  
  count = 0
  ans = 0
  bef_checked = [int(x) for x in range(n)]
  index = [0]*n
  while True:
    ans += 1
    check = copy.deepcopy(bef_checked)
    bef_checked = []
    already = [False]*n
    flag = True
    for v in check:
      if already[v]:
        continue
      flag = False
      v2 = a[v][index[v]]
      if already[v2]:
        continue
      if v != a[v2][index[v2]]:
        continue
      already[v] = True
      already[v2] = True
      index[v] += 1
      index[v2] += 1
      if index[v] == n-1:
        count += 1
      else:
        bef_checked.append(v)
      if index[v2] == n-1:
        count += 1
      else:
        bef_checked.append(v2)
        
    if flag:
      print(-1)
      sys.exit()
    if count == n:
      break
  
  print(ans)
  

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import copy

def main():
  input = sys.stdin.readline
  n = int(input())
  a = [None]*n
  for i in range(n):
    a[i] = [int(x)-1 for x in input().split()]
  
  count = 0
  ans = 0
  bef_checked = [int(x) for x in range(n)]
  index = [0]*n
  while True:
    ans += 1
    check = copy.deepcopy(bef_checked)
    bef_checked = []
    already = [False]*n
    flag = True
    for v in check:
      if already[v]:
        continue
      flag = False
      v2 = a[v][index[v]]
      if already[v2]:
        continue
      if v != a[v2][index[v2]]:
        continue
      already[v] = True
      already[v2] = True
      index[v] += 1
      index[v2] += 1
      if index[v] == n-1:
        count += 1
      else:
        bef_checked.append(v)
      if index[v2] == n-1:
        count += 1
      else:
        bef_checked.append(v2)
        
    if flag:
      print(-1)
      sys.exit()
    if count == n:
      break
  
  print(ans)
  

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
table=[]
for i in range(N):
    d=deque()
    l=list(map(int,input().split()))
    for j in range(N-1):
        d.append(l[j]-1)
    table.append(d)
#print(table)
day=0
allnone=0
#print(1==None)
breakflag=0
flag=1
while breakflag==0:
    seen=[0]*N
    allnone=0
    breakflag = 1
    for i in range(N):
        if seen[i]==0:
            t1 = None
            t2 = None
            d1 = deque()
            d2 = deque()
            d1=table[i]
            if len(d1)>0:
                t1=d1.popleft()
                d2=table[t1]
            if len(d2)>0:
                t2=d2.popleft()
            #print(i,t1,t2)
            if t1!=None:
                if (i==t2)and(seen[t1]==0):
                    seen[i] = 1
                    seen[t1] = 1
                    breakflag = 0
                else:
                    table[i].appendleft(t1)
                    if t2 != None:
                        table[t1].appendleft(t2)
        #print(table,seen)
        #input()
    day=day+1
for i in range(N):
    if len(table[i])>0:
        flag=0
    break
if flag==0:
    print("-1")
else:
    print(day-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
table=[]
for i in range(N):
    d=deque()
    l=list(map(int,input().split()))
    for j in range(N-1):
        d.append(l[j]-1)
    table.append(d)
#print(table)
day=0
allnone=0
#print(1==None)
breakflag=0
flag=1
while breakflag==0:
    seen=[0]*N
    allnone=0
    breakflag = 1
    for i in range(N):
        t1 = None
        t2 = None
        d1 = deque()
        d2 = deque()
        d1=table[i]
        if len(d1)>0:
            t1=d1.popleft()
            d2=table[t1]
        if len(d2)>0:
            t2=d2.popleft()
        #print(i,t1,t2)
        if t1!=None:
            if (i==t2)and(seen[i]==0)and(seen[t1]==0):
                seen[i] = 1
                seen[t1] = 1
                breakflag = 0
            else:
                table[i].appendleft(t1)
                if t2 != None:
                    table[t1].appendleft(t2)

        #print(table,seen)
        #input()
    day=day+1
for i in range(N):
    if len(table[i])>0:
        flag=0
    break
if flag==0:
    print("-1")
else:
    print(day-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
table=[]
for i in range(N):
    d=deque()
    l=list(map(int,input().split()))
    for j in range(N-1):
        d.append(l[j]-1)
    table.append(d)
#print(table)
day=0
allnone=0
#print(1==None)
breakflag=0
flag=1
while breakflag==0:
    seen=[0]*N
    allnone=0
    breakflag = 1
    for i in range(N):
        t1 = None
        t2 = None
        d1 = deque()
        d2 = deque()
        d1=table[i]
        if len(d1)>0:
            t1=d1.popleft()
            d2=table[t1]
        if len(d2)>0:
            t2=d2.popleft()
        #print(i,t1,t2)
        if (i==t2):             #pairを作れる時
            if t1!=None:        #t1は値がある時
                if (seen[i]==0)and(seen[t1]==0):
                    seen[i]=1
                    seen[t1]=1
                    breakflag=0
                else:
                    table[i].appendleft(t1)
                    if t2 != None:
                        table[t1].appendleft(t2)
        else:
            if t1!=None:
                table[i].appendleft(t1)
                if t2!=None:
                    table[t1].appendleft(t2)
        #print(table,seen)
        #input()
    day=day+1
for i in range(N):
    if len(table[i])>0:
        flag=0
    break
if flag==0:
    print("-1")
else:
    print(day-1)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    dq = [LI() for _ in range(N)]
    p = [0] * N
    cnt = 0
    c = [0] * N
    while cnt < N*(N-1)//2:
        ud = False
        for i in range(N):
            if p[i] >= N-1: continue

            j = dq[i][p[i]]-1
            if dq[j][p[j]]-1 == i:
                c[i] = c[j] = max(c[i],c[j]) + 1
                p[i] += 1; p[j] += 1
                cnt += 1
                ud = True
        if ud:
            continue
        else:
            print(-1)
            return
    print(max(c))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    dq = [LI() for _ in range(N)]
    p = [0] * N
    ans = 0
    cnt = 0
    while cnt < N*(N-1)//2:
        ud = False
        used = [False] * N
        for i in range(N):
            if used[i] or p[i] >= N-1: continue

            j = dq[i][p[i]]-1
            if dq[j][p[j]]-1 == i and not used[j]:
                used[i] = used[j] = True
                p[i] += 1; p[j] += 1
                cnt += 1
                ud = True
        if ud:
            ans += 1
            continue
        else:
            print(-1)
            return
    print(ans)

if __name__ == '__main__':
    main()