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:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
cnt_max = {}
for i in range(n):
    cnt_max[i] = 0
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            flag = True
            tmp = memo[i]
            max_1 = max(cnt_max[i], cnt_max[a[i][tmp] - 1])
            cnt_max[i] = max_1 + 1
            cnt_max[a[i][tmp] - 1] = max_1 + 1
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print(-1)
                exit()
        break
ans = 0
for i in cnt_max:
    ans = max(cnt_max[i] , ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import exit
  n = int(input())
  a = [list(map(int, input().split())) for _ in range(n)]
  ilist = [0] * n
  days = 1
  while True:
    booked = [False] * n
    books = 0
    for i in range(n):
      if booked[i]:
        continue
      ii = ilist[i]
      if ii == n - 1:
        continue
      j = a[i][ii] - 1
      if booked[j]:
        continue
      if a[j][ilist[j]] - 1 != i:
        continue
      books += 1
      booked[i] = True
      booked[j] = True
      ilist[i] += 1
      ilist[j] += 1
    if books == 0:
      print(-1)
      exit()
    if all(i == n - 1 for i in ilist):
      break
    days += 1
  print(days)
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
ans = 0
B = [True]*N
while sum(B) > 0:
    ans += 1
    p = True
    C = B[:]
    for i in range(N):
        if C[i] and C[A[i][-1]-1] and A[A[i][-1]-1][-1]-1 == i:
            A[A[i][-1]-1].pop()
            C[A[i][-1]-1] = False
            if len(A[A[i][-1]-1]) == 0:
                B[A[i][-1]-1] = False
            A[i].pop()
            C[i] = False
            if len(A[i]) == 0:
                B[i] = False
            p = False
    if p:
        ans = -1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC139
def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = A[x : x + N - 1][::-1]
    ans, flg, matched = 0, 0, set()
    while B:
        for i in range(1, N + 1):
            if i in B and i not in matched:
                x = B[i][-1]
                if x in B and x not in matched and B[x][-1] == i:
                    B[i].pop()
                    B[x].pop()
                    matched |= {i, x}
                    flg = 1
                    if B[i] == []:
                        del B[i]
                    if B[x] == []:
                        del B[x]
        if flg:
            ans += 1
            flg = 0
            matched = set()
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  1 20:25:02 2019

@author: Yamazaki Kenichi
"""

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

T = [0 for i in range(N)]
today = [True for i in range(N)]

ans = 0
counta = 0
check, check2 = 0, 0
while counta < N:
    today = [True for i in range(N)]
    for i in range(N):
        if today[i]:
            vs = A[i][T[i]] - 1
            if A[vs][T[vs]] == i + 1 and today[vs]:
                T[i] += 1
                T[vs] += 1
                check2 += 1
                if T[i] == N - 1:
                    T[i] = 0
                    counta += 1
                if T[vs] == N - 1:
                    T[vs] = 0 
                    counta += 1
                today[i], today[vs] = False, False
#        print(i,vs,today,T)
    if check == check2:
        ans = -1
        break
    else:
        check = check2
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
    items.append(deque(map(int, input().split())))

ans = 0
from collections import defaultdict

while True:
    used = set()
    flag = False
    for j in range(N):
        if j + 1 in used:
            continue
        if len(items[j]) >= 1:
            t = items[j][0]
            if t not in used and len(items[t - 1]) >= 1 and j + 1 == items[t - 1][0]:
                used.add(j + 1)
                used.add(t)
                items[j].popleft()
                items[t - 1].popleft()
                flag = True
    all_done = True
    for i in range(N):
        if len(items[i]) != 0:
            all_done = False
    if flag:
        ans += 1
    else:
        print(-1)
        exit()
    if all_done:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def notempty(b):
    return any(map(lambda x: len(x), b))


n = int(input())
a = [list(reversed(list(map(lambda x:int(x) - 1, input().split()))))
     for _ in range(n)]
cnt = 0
while notempty(a):
    flg = 0
    cnt += 1
    li = [True] * n
    for i in range(n):
        if len(a[i]) and li[i] and len(a[[i][-1]]) and li[a[i][-1]] and a[a[i][-1]][-1] == i:
            5
            tmp = a[i][-1]
            a[i].pop()
            a[tmp].pop()
            li[i], li[tmp] = False, False
            flg = 1
    if not flg:
        print(-1)
        exit(0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque([int(_)-1 for _ in input().split()]) for __ in range(n)]
f=[0 for _ in range(n)]
m=n*(n-1)//2
d=0
while True:
    for i in range(n):
        if a[i] != deque([]):
            if f[i]==0 and f[a[i][0]]==0:
                if a[a[i][0]][0]==i:
                    f[i]=1
                    f[a[i][0]]=1
                    m-=1
                    a[a[i][0]].popleft()
                    a[i].popleft()
    if 1 not in f:
        print(-1)
        break
    else:
        f=[0 for _ in range(n)]
        d+=1
        if m==0:
            print(d)
            break

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(list(map(int, input().split())))
    I = [0 for _ in range(N)]
    res = 0
    while any(i<N-1 for i in I):
        B = [a[i] if i < N-1 else -1 for a,i in zip(A,I)]
        checked = set()
        for j,b in enumerate(B,start=1):
            if B[b-1] == j:
                I[j-1] += 1
                checked.update({j})
        if checked:
            res += 1
        else:
            res = -1
            break
    
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque


def dfs(s, links, states):
    if s in states:
        if states[s] == 1:
            return False
    else:
        states[s] = 1
        for u in links[s]:
            result = dfs(u, links, states)
            if not result:
                return False
        states[s] = 2
    return True


n = int(input())
links = defaultdict(set)
may_root = set()
in_cnt = defaultdict(lambda: 0)
for i, line in enumerate(sys.stdin):
    aaa = list(map(int, line.split()))
    j = aaa[0] - 1
    a, b = (i, j) if i < j else (j, i)
    prev = a * 1000 + b
    may_root.add(prev)

    for j in aaa[1:]:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * 1000 + b
        links[prev].add(key)
        in_cnt[key] += 1
        prev = key
may_root = {r for r in may_root if in_cnt[r] == 0}

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

states = {}
for key in may_root:
    result = dfs(key, links, states)
    if result == False:
        print(-1)
        exit()

q = deque([(r, 1) for r in may_root])
ans = 0
while q:
    k, d = q.popleft()
    ans = max(ans, d)
    d += 1
    q.extend((u, d) for u in links[k])
print(ans)

Submission status: Time Limit Exceeded

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

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            if target < i:
                continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if not all(len(a) == 0 for a in A.values()):
                print(-1)
                return
            else:
                raise ValueError("test")
        # print("11111")
        for i in pool:
            A[i].pop()
            if len(A[i]) == 0:
                Q.remove(i)

        count += 1
        if all(len(a) == 0 for a in A.values()):
            print(count)
            return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    N = II()
    A = XLMIIS(N)
    days = 0
    while len(A) != 0:
        #print(A)
        firstgame = True
        matched = False
        desired = [ a[0] for a in A]
        if desired.count(-1) == N:
            print(days)
            return
        for i in range(N):
            a = desired[i]
            b = desired[a-1]
            # matched
            if a > 0 and b > 0 and b == i+1:
                A[a-1].pop(0)
                if len(A[a-1]) == 0:
                    A[a-1].append(-1)
                A[i].pop(0)
                if len(A[i]) == 0:
                    A[i].append(-1)
                desired[a-1] = -1
                if firstgame:
                    firstgame = False
                    matched = True
                    days += 1
        if matched == False:
            print(-1)
            return 
            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_s = [] 
for i in range(n):
    a_s.append([int(item) - 1 for item in input().split()])

total = n * (n - 1) // 2
days = 0
itrs = [0] * n
fights = 0

while True:
    wants = set()
    has_match = False
    for item in range(n):
        idx = itrs[item]
        if idx == n - 1:
            continue
        want = a_s[item][idx]
        # Check there is match or not
        if a_s[want][itrs[want]] == item:
            has_match = True
            if item < want:
                wants.add((item, want))
            else:
                wants.add((want, item))
    if not has_match:
        break
    # Process match
    for a, b in wants:
        itrs[a] += 1
        itrs[b] += 1
        fights += 1
    days += 1

if fights == total:
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

total_match=n*(n-1)//2
match=0
day=0

while match<total_match:
    day+=1
    today_match=[]

    for i in range(n):
        if i in today_match:
            continue
        if league[i]:
            m=league[i][-1]-1
            if m in today_match:
                continue
            if league[m] and league[m][-1]-1==i:
                today_match.extend((league[i].pop()-1, league[m].pop()-1))
    if not today_match:
        day=-1
        break
    #print(today_match)
    match+=len(today_match)//2

print(day)

Submission status: Time Limit Exceeded

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

a_i = [0] * n

day = 0
while True:
    matches = []
    has_match = False
    for i in range(n):
        if a_i[i] == n - 1:
            continue
        match = {i+1, a[i][a_i[i]]}
        if match in matches:
            lst = list(match)
            a_i[lst[0] - 1] += 1
            a_i[lst[1] - 1] += 1
            has_match = True
        else:
            matches.append(match)
    if has_match:
        day += 1
        if all([a_i[i] == n - 1 for i in range(n)]):
            break
    else:
        day = -1
        break

print(day)

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[List[int]]"):
    flag = True
    counter = 0
    while flag:
        tmp = [a[0] for a in A]
        p_idx = []
        for i, t in enumerate(tmp):
            if i == tmp[t]:
                p_idx.append(i)
        if len(p_idx) == 0:
            print(-1)
            return
        for p in p_idx:
            A[p].pop(0)
            A[p].append(-1)
        if all([all([aa == -1 for aa in a]) for a in A]):
            flag = False
        counter += 1
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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)) - 1 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:
#import numpy as np

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

for i in range(n):
    A[i].append(1010 + i)
    for j in range(n):
        A[i][j] -= 1

#print(A)

S = [0] * n

d = 0
for ii in range(n*n*2):
    co = 0
    i = 0
    F = [0 for i in range(n)]
    ga = 0
    while co < n:
        if F[i] == 0 and S[i] != n:
            aite = A[i][S[i]]
            #print(S)
            #print("aite",aite)
            if aite <= 1000 and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == (n-1)*n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

while (num < n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
    if ((j == n - 1) & (len(visit) == 0)):
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a_list = []
for i in range(N):
    a_list.append(list(map(int, input().split())))

c = 0
z_list = []
while(1):
    alr_list = []
    for i in range(N):
        if i in alr_list:
            continue
        if i in z_list:
            continue
        i_a = a_list[i][0] - 1
        if i_a in alr_list:
            continue
        if i_a in z_list:
            continue

        if i+1 == a_list[i_a][0]:
            a_list[i].pop(0)
            a_list[i_a].pop(0)
            if len(a_list[i]) == 0:
                z_list.append(i)
            if len(a_list[i_a]) == 0:
                z_list.append(i_a)
            alr_list.append(i)
            alr_list.append(i_a)
    c += 1
    if len(z_list) == N:
        break
    if len(alr_list) == 0:
        c = -1
        break
print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def solve():
  ## input
  N = int(input())
  An = [[i-1 for i in list(map(int, input().split()))] for _ in range(N)]  

  ## solve
  ret = 0
  Pn = [0 for _ in range(N)]
  while min(Pn) < N-1:
    dct = defaultdict(lambda:set([]))
    game = 0
    for i in range(N):
      if Pn[i] >= N-1:
        continue
      else:
        j = An[i][Pn[i]]
        if i in dct[j]:
          dct[j].remove(i)
          game += 1
          Pn[i] += 1
          Pn[j] += 1
        else:
          dct[i].add(j)
    if game > 0:
      ret += 1
    else:
      return -1
  return ret

print(solve())

Submission status: Time Limit Exceeded

Solution code:

from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

#N = list(map(int, input().split()))

import sys
def input():
	return sys.stdin.readline().strip()


N = int(input())
A = []
day = [0]*N
for i in range(N):
	A.append(deque(map(int, input().split())))
num = 0
while True:
	judge = 0
	for i in range(N):
		if len(A[i]) > 0:
			for j in range(N):
				if len(A[j]) > 0 and i != j:
					#print(i, j, A[i][0], A[j][0])
					if A[i][0] == j+1 and A[j][0] == i+1:
						A[i].popleft()
						A[j].popleft()
						shiai = max(day[i], day[j]) + 1
						day[i] = shiai
						day[j] = shiai
						num += 1
						judge = 1
						if len(A[i]) == 0:
							break
	if judge == 0:
		break

if num == N*(N - 1)//2:
	print(max(day))
else:
	print(-1)

Submission status: Time Limit Exceeded

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

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            if target < i:
                continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if not all(len(a) == 0 for a in A.values()):
                print(-1)
                return
        # print("11111")
        for i in pool:
            A[i].pop()
            if len(A[i]) == 0:
                Q.remove(i)

        count += 1
        if all(len(a) == 0 for a in A.values()):
            print(count)
            return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int( input())
    A = [ deque( map( int, input().split())) for _ in range(N)]
    cnt = N*(N-1)
    days = 0
    W = [False]*N
    while cnt > 0:
        days += 1
        now = cnt
        V = [0]*N
        for i in range(N):
            if V[i] == 1 or W[i]:
                continue
            a = A[i][0]
            a -= 1
            if V[a] == 1 or W[a]:
                continue
            if i+1 == A[a][0]:
                V[a] = 1
                V[i] = 1
                A[a].popleft()
                A[i].popleft()
                if not A[a]:
                    W[a] = True
                if not A[i]:
                    W[i] = True
                cnt -= 2
        if now == cnt:
            print(-1)
            return
    print( days)

                        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
A = []

def intm1(a):
    return int(a) - 1

for _ in range(N):
    A.append(deque(list(map(intm1, input().split()))))

nokori = N*(N-1)
day = 0

while nokori > 0:
    day += 1
    ng = [False] * N
    upd = False
    for i in range(N):
        if ng[i] or len(A[i]) == 0:
            continue
        j = A[i][0]
        if len(A[j]) > 0 and A[j][0] == i and not ng[j]:
            ng[A[i].popleft()] = True
            ng[A[j].popleft()] = True
            upd = True
            nokori -= 2
    if not upd:
        break

print(day if nokori == 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c=0
f = True
for i in range(N):
  A.append(list(map(int, input().split())))
idx = [0 for i in range(N)]

a = 0

btlf = [False for i in range(N)]#その周回ですでにバトルしたかどうかのフラグです

for i in range((N*(N-1))//2):#周回
  btlf = [False for i in range(N)]#リセット
  for j in range(N):
    #print(idx)
    if idx[j] != N-1:
      a = A[j][idx[j]]
      if A[a-1][idx[a-1]]-1==j and btlf[a-1] == False and btlf[j] == False:
        idx[a-1]+=1
        btlf[a-1] = True
        idx[j]+=1
        btlf[j] = True
        #c+=1#とりあえず試合数で実装して後から修正します
  if idx == [N-1 for i in range(N)]:
    print(i+1)
    f = False
    break
  if btlf == [False for i in range(N)]:#対戦が一度もなければ打ち切ります
    break
if f:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [0 for i in range(n)]
l1 = [0 for i in range(n)]
day = 0
count1 = 0
count2 = 0
key = 1
b = n*(n-1)//2
while count1 < b:
    for i in range(n-1):
        if l[i] < n-1 and l1[i] == 0:
            j = a[i][l[i]] - 1
            if l1[j] == 0:
                if a[j][l[j]] == i + 1:
                    count1 += 1
                    l[i] += 1
                    l[j] += 1
                    l1[i] += 1
                    l1[j] += 1
    if count1 > count2:
        day += 1
        count2 = count1
        l1 = [0 for i in range(n)]
    else:
        key = 0
        break
if key == 1:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import exit
  n = int(input())
  a = [list(map(int, input().split())) for _ in range(n)]
  ilist = [0] * n
  days = 1
  while True:
    booked = set()
    books = 0
    for i in range(n):
      ii = ilist[i]
      if ii == n - 1:
        continue
      j = a[i][ii] - 1
      if a[j][ilist[j]] - 1 != i:
        continue
      if (i in booked) or (j in booked):
        continue
      books += 1
      booked.add(i)
      booked.add(j)
      ilist[i] += 1
      ilist[j] += 1
    if books == 0:
      print(-1)
      exit()
    if all(i == n - 1 for i in ilist):
      break
    days += 1
  print(days)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for i in range(n):
    A[i].append(1010 + i)
    for j in range(n):
        A[i][j] -= 1

#print(A)

S = np.zeros(n, dtype="int")

d = 0
for ii in range(n*n*2):
    co = 0
    i = 0
    F = np.zeros(n)
    ga = 0
    while co < n:
        aite = A[i][S[i]]
        #print(S)
        #print("aite",aite)
        if aite <= 1000 and A[aite][S[aite]] == i and F[i] == 0 and F[aite] == 0:
            #print("g", i, aite)
            S[i] += 1
            S[aite] += 1
            F[i] = 1
            F[aite] = 1
            co = 0
            ga += 1
        i += 1
        if i == n:
            i = 0
        co += 1
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == (n-1)*n:
            print(d-1)
        else:
            print(-1)
        break

Submission status: Time Limit Exceeded

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

ans=0
cnt=0
for j in range(n*n//2+1):
    f=0
    q=[]
    for i in range(n):        
        if len(a[i])>0 and len(a[a[i][0]-1])>0 and i+1==a[a[i][0]-1][0] and i<a[i][0]-1:
            #a[a[i][0]-1].pop(0)
            #a[i].pop(0)
            q.append(i)
            q.append(a[i][0]-1)
            f+=1    
            cnt+=1
    if len(q)>0:
        for k in q:
            a[k].pop(0)
            
            
    if f==0 and cnt<n*(n-1)//2:
        print(-1)
        exit()
    elif f>0:
        ans+=1
    else:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
fin = [False] * N
An = [''] * N
for n in range(N):
    An[n] = deque([int(x) for x in input().split()])

days = 0

while False in fin:
    days += 1
    matched = [False] * N
    flag = False
    for n in [n for n in range(N) if fin[n]==False]:
        if matched[n]:
            continue
        op = An[n][0]
        if An[op - 1][0] == n + 1 and not matched[op - 1]:
            flag = True
            An[n].popleft()
            An[op - 1].popleft()
            matched[n] = True
            matched[op - 1] = True
            if len(An[n]) == 0:
                fin[n] = True
            if len(An[op - 1]) == 0:
                fin[op - 1] = True
    if not flag:
        days = -1
        break
print(days)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    while True:
        s = Counter()
        for i in range(1, N+1):
            if A[i-1]:
                d = A[i-1][-1]
                n = (min(i, d), max(i, d))
                s[n] += 1

        c = 0
        for k, v in s.items():
            if v == 1:
                continue
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            c += 1
        if c == 0:
            break
        else:
            ans += 1

    for a in A:
        if a:
            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:
N = int(input())
A = [ [ int(a)-1 for a in input().split() ] for _ in range(N) ]

ans = 0
flg = True
checked = []
while sum(len(v) for v in A) > 0:
  for i in range(N):
    if i in checked: continue
    if len(A[i]) == 0: continue
    index = A[i][0]
    if index in checked: continue
    if len(A[index]) == 0:
      flg = True
      break
    if A[index][0] == i:
      flg = False
      checked.append(i)
      checked.append(A[i][0])
      A[i].pop(0)
      A[index].pop(0)
  if flg:
    ans = -1
    break
  ans += 1
  flg = True
  checked = []

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
A = [list(reversed(list(map(lambda x:int(x)-1,input().split())))) for i in range(N)]
B = {i:row for i,row in enumerate(A)}

k = 0
end = 0
while 1:
    used = set()
    dels = []
    for i,q in B.items():
        if not q: continue
        if i in used: continue
        j = q[-1]
        if j in used: continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print(-1)
        exit()
    if end == N:
        print(k+1)
        exit()
    for i in dels:
        del B[i]
    k += 1

Submission status: Time Limit Exceeded

Solution code:
def main():
	n = int(input())
	a = [[]]
	for _ in range(n):
		a += [list(list(map(int,input().split())))]
	# print(a)
	ans = 0
	while True:
		ans +=1
		used = [False for i in range(n+1)]
		temp = 0
		tempf = 0
		for i in range(1,n+1):
			if a[i] == []:
				temp += 1
				continue
			elif i == a[a[i][0]][0]:
				used[a[i][0]] = True
				used[i] = True
			# print(i, a[a[i][0]])
		for i in range(1,n+1):
			if used[i]:
				a[i] = a[i][1::]
			else:
				tempf += 1
		if temp == n:
			break
		if tempf == n:
			print(-1)
			return
	print(ans-1)

main()