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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
            count[cur_match] = -1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter,deque

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque([key for key, val in count.items() if val == 0])
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
            count[cur_match] = -1
        que.extend(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    rem = n * (n - 1) // 2
    while rem:
        ans += 1
        today = [key for key, val in count.items() if val == 0]
        if not today:
            print(-1)
            return
        for cur_match in today:
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
            rem -= 1
            count[cur_match] = -1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    while count:
        ans += 1
        today = [key for key, val in count.items() if val == 0]
        if not today:
            print(-1)
            return

        for cur_match in today:
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
            del count[cur_match]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 2:
            ans = M
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 2:
            ans = M+1
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 2000:
            ans = M+1
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):

            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    if Lock[A[i][id[i]]-1] == i and i not in tmp:
                        Lock[A[i][id[i]]-1] = -1
                        id[A[i][id[i]]-1] += 1
                        tmp.add(A[i][id[i]]-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    flag = [True]*N
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    if Lock[A[i][id[i]]-1] == i and i not in tmp:
                        Lock[A[i][id[i]]-1] = -1
                        id[A[i][id[i]]-1] += 1
                        tmp.add(A[i][id[i]]-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    flag = [True]*N
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    if Lock[A[i][id[i]]-1] == i and i not in tmp:
                        Lock[A[i][id[i]]-1] = -1
                        id[A[i][id[i]]-1] += 1
                        tmp.add(A[i][id[i]]-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)


main()

Submission status: Time Limit Exceeded

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

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

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    while True:
        day += 1
        # print('-----',day)
        # print(al)
        # already_fights = [False]*(n+1)
        already_fights = set()
        update_flag = False
        for i in range(1,n+1):
            al_i = al[i]
            if not al_i or i in already_fights: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or i_next_rival in already_fights: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights.add(i)
                already_fights.add(i_next_rival)
                # already_fights[i] = True
                # already_fights[i_next_rival] = True
                cnt += 1
                update_flag = True
            else:
                continue
        # print(al)

        if not update_flag:
            print(-1)
            exit()

        if cnt == max_cnt:
            break

    print(day)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    while True:
        day += 1
        # print('-----',day)
        # print(al)
        already_fights = [False]*(n+1)
        update_flag = False
        for i in range(1,n+1):
            al_i = al[i]
            if not al_i or already_fights[i]: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or already_fights[i_next_rival]: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights[i] = True
                already_fights[i_next_rival] = True
                cnt += 1
                update_flag = True
            else:
                continue
        # print(al)

        if not update_flag:
            print(-1)
            exit()

        if cnt == max_cnt:
            break

    print(day)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    # print(al)

    day = 0
    cnt = 0
    max_cnt = n*(n-1)//2
    while True:
        day += 1
        # print('-----',day)
        # print(al)
        already_fights = [False]*(n+1)
        update_flag = False
        for i in range(1,n+1):
            al_i = al[i]
            if not al_i or already_fights[i]: continue
            i_next_rival = al_i[0]

            al_rival_i = al[i_next_rival]
            if not al_rival_i or already_fights[i_next_rival]: continue
            i_next_rival_rival = al_rival_i[0]

            if i_next_rival_rival == i:
                al[i].popleft()
                al[i_next_rival].popleft()
                already_fights[i] = True
                already_fights[i_next_rival] = True
                cnt += 1
                update_flag = True
            else:
                continue
        # print(al)

        if not update_flag:
            print(-1)
            exit()

        if cnt == max_cnt:
            break

    print(day)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# print(al)

day = 0
cnt = 0
max_cnt = n*(n-1)//2
while True:
    day += 1
    # print('-----',day)
    # print(al)
    already_fights = [False]*(n+1)
    update_flag = False
    for i in range(1,n+1):
        al_i = al[i]
        if not al_i or already_fights[i]: continue
        i_next_rival = al_i[0]

        al_rival_i = al[i_next_rival]
        if not al_rival_i or already_fights[i_next_rival]: continue
        i_next_rival_rival = al_rival_i[0]

        if i_next_rival_rival == i:
            al[i].popleft()
            al[i_next_rival].popleft()
            already_fights[i] = True
            already_fights[i_next_rival] = True
            cnt += 1
            update_flag = True
        else:
            continue
    # print(al)

    if not update_flag:
        print(-1)
        exit()

    if cnt == max_cnt:
        break

print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = [deque(map(int, input().split())) for i in range(n)]
lis = deque([-1]*n) #次誰と試合するか
num = n*(n-1)//2 
match = 0 #現在の試合数
ans = 0 #何日目か

for i in range(n):
  lis[i]=a[i].popleft()-1

while match < num:
  ans+=1
  flg = True
  day = [0]*n #その日に試合したか
  for i, j in enumerate(lis):
    if day[i] == 1:
      continue
    if lis[j]==i and day[j]==0:
      flg = False
      match+=1
      day[i]=1
      day[j]=1
      if len(a[i])>0: 
        lis[i]=a[i].popleft()-1
      else:
        lis[i]=-1
      if len(a[j])>0:
        lis[j]=a[j].popleft()-1
      else:
        lis[j]=-1
  if flg:
    print(-1)
    quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = [deque(map(int, input().split())) for i in range(n)]
lis = [-1]*n #次誰と試合するか
num = n*(n-1)//2 
match = 0 #現在の試合数
ans = 0 #何日目か

for i in range(n):
  lis[i]=a[i].popleft()-1

while match < num:
  ans+=1
  flg = True
  day = [0]*n #その日に試合したか
  for i, j in enumerate(lis):
    if day[i] == 1:
      continue
    if lis[j]==i and day[j]==0:
      flg = False
      match+=1
      day[i]=1
      day[j]=1
      if len(a[i])>0: 
        lis[i]=a[i].popleft()-1
      else:
        lis[i]=-1
      if len(a[j])>0:
        lis[j]=a[j].popleft()-1
      else:
        lis[j]=-1
  if flg:
    print(-1)
    quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = [deque(map(int, input().split())) for i in range(n)]
lis = [-1]*n #次誰と試合するか
num = n*(n-1)//2 
match = 0 #現在の試合数
ans = 0 #何日目か

for i in range(n):
  lis[i]=a[i].popleft()-1

while match < num:
  ans+=1
  flg = True
  #print("day:"+str(ans))
  day = [0]*n #その日に試合したか
  for i, j in enumerate(lis):
    if lis[j]==i and day[i]==0 and day[j]==0:
      #print(str(i+1)+" vs "+str(str(j+1)))
      flg = False
      match+=1
      day[i]=1
      day[j]=1
      if len(a[i])>0: 
        lis[i]=a[i].popleft()-1
      else:
        lis[i]=-1
      if len(a[j])>0:
        lis[j]=a[j].popleft()-1
      else:
        lis[j]=-1
  #print(lis)
  if flg:
    print(-1)
    quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False
    while True:
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if t > N * (N-1):
                fail = True
                break

            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]

            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
            break
        t += 1
        if t > N * (N-1):
            fail = True
            break
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False
    _i = 0
    while _i < 100 * N:
        _i += 1
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if t > N * (N-1):
                fail = True
                break

            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
            break
        t += 1
        if t > N * (N-1):
            fail = True
            break
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False

    while True:
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if t > N * (N-1):
                fail = True
                break

            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
            break
        t += 1
        if t > N * (N-1):
            fail = True
            break
    if fail:
        print("-1")
    else:
        print(t)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    n, *aa = [deque(map(int, l.split())) for l in open(0)]

    n = n[0]
    days = 0
    rem = set(range(n))
    while 1:
        today = set()
        days += 1
    #     print(days, aa)
        new_rem = set()
        for i in rem:
#             print(f'{i=}')
            if i not in today:
                j = aa[i][0]-1
#                 print(f'{j=}')
                if j not in today and i == aa[j][0]-1:
                    today.add(i)
                    today.add(j)
                    
        changed = False
#         print(f'{rem=}, {today},{aa=}')
        for i in rem:
            if i in today:
                changed = True
                aa[i].popleft()
            if len(aa[i]):
                new_rem.add(i)
#         print(f'{new_rem=},{aa=}')
        rem = new_rem
        if not changed:
            return -1
        if not len(new_rem):
            return days
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def all_done(arr, N):
    for a in arr:
        if a != N-1:
            return False
    return True

def main():
    N = I()
    G = []
    for i in range(N):
        G.append(LI_())
    t = 0
    next_ix = [0] * N
    fail = False

    while True:
        if fail:
            break
        if all_done(next_ix, N):
            break
        playing = set()
        for i in range(N):
            if t > N * (N-1):
                fail = True
                break

            if i in playing:
                continue
            if next_ix[i] >= N-1:
                continue
            j = G[i][next_ix[i]]
            if next_ix[j] >= N-1:
                fail = True
                break

            if j in playing:
                continue
            if G[j][next_ix[j]] != i:
                continue
            else:
                playing.add(j)
                playing.add(i)
                next_ix[i] += 1
                next_ix[j] += 1
        if len(playing) == 0:
            fail = True
        t += 1
        if t > N * (N-1):
            fail = True
            break
    if fail:
        print("-1")
    else:
        print(t)
main()