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

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

        if len(pool) == 0:
            if not all(len(a) == 0 for a in A):
                print(-1)
                return
        for i in pool:
            A[i].pop()
        count += 1
        if all(len(a) == 0 for a in A):
            print(count)
            return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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
while 1:
    co = 0
    i = 0
    F = [0] * n
    ga = 0
    while co < n:
        aite = A[i][S[i]]
        #print(S)
        #print("aite",aite)
        if aite <= 1000 and F[i] == 0 and F[aite] == 0 and A[aite][S[aite]] == i:
            #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):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: a-1, As))))
  A.append(As)
#print(A)
d = 0
n = 0
while True:
  gs = []
  for i in range(N):
    if A[i] == []:
      continue
    j = A[i][-1]
    if j < i:
      continue
    if A[j] == []:
      continue
    if A[j][-1] == i:
      n += 1
      gs.append((i, j))
  if gs == []:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  for i, j in gs:
    A[i].pop()
    A[j].pop()
  d += 1
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
while True:
    vs = set()
    nn = False
    for i in range(N):
        i += 1
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)

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)]

k = 0
end = 0
while 1:
    used = set()
    for i,q in enumerate(A):
        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
            if not A[j]: end += 1
    if not used:
        print(-1)
        exit()
    if end == N:
        print(k+1)
        exit()
    k += 1

Submission status: Time Limit Exceeded

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

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

ans = 0

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

        if i == r and l not in s and r not in s:
            s.add(l)
            s.add(r)
            f = True
        else:
            L[i].appendleft(l)
            L[l].appendleft(r)

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

dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

day = 0
setn = set(range(n))
while True:
    popped = 0
    plist = set()
    zeros = 0
    tmpns = copy.copy(setn)
    for i in setn:
        if len(a[i]) == 0:
            tmpns.remove(i)
            continue
        if i in plist:
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if num in plist:
            continue
        if a[num][0] - 1 == i:
            plist.add(num)
            a[i].popleft()
            a[num].popleft()
            popped += 1
    if popped == 0:
        if len(tmpns) == 0:
            break
        else:
            day = -1
            break
    setn = tmpns
    day += 1

print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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 = []
    for i in range(N):
        if i in ng or len(A[i]) == 0:
            continue
        j = A[i][0]
        if len(A[j]) > 0 and j not in ng and A[j][0] == i:
            ng.append(A[i].popleft())
            ng.append(A[j].popleft())
            nokori -= 2
    if len(ng) == 0:
        break

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

Submission status: Time Limit Exceeded

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

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

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            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
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# ABC139e
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

day = 0
#print(a)
while (True):
    l = []
    for i in range(n):
        if (len(a[i])!=0 and len(a[a[i][0] - 1])!=0 and a[a[i][0] - 1][0]-1 == i):
            l.append(i)
    if (len(l) == 0):
        break
    for i in l:
        a[i].pop(0)
    #print(l)
    l.clear()
    day += 1
    #print(a)
count=0
for i in range(n):
    count += len(a[i])
if(count==0):
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
P = [0] * N
cnt, day = 0, 0
while 1:
    day += 1
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == N*(N-1)//2:
        print(day)
        break
    if flag == 0:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    for w in range(10 ** 15):
        cnt += 1
        f = [False] * n
        cc = 0
        
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
                cc += 1
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        cc -= 2
                        f[i] = True
                        f[mt[i]-1] = True
            if cc == 0:
                break
        bb = False
        for i in range(n):
            if f[i]:
                if ls[i] + 1 < n - 1:
                    ls[i] += 1
                    bb = True
                else:
                    ls[i] = -1
        b = True
        for i in range(n):
            if ls[i] != -1:
                b = False
                break
        if b:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

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

def f():
    day = 0
    ptrs = [0] * n

    while True:
        if all(ptr == n - 1 for ptr in ptrs):
            return day

        visited = [False] * n
        for i in range(n):
            if ptrs[i] == n - 1 or visited[i]:
                continue
            
            x = a[i][ptrs[i]] # iの次候補
            if ptrs[x] == n - 1 or visited[x]:
                continue

            y = a[x][ptrs[x]] # xの次候補
            if i == y:
                ptrs[i] += 1
                ptrs[x] += 1
                visited[i] = True
                visited[x] = True

        # すべて未訪問の場合
        if all(not v for v in visited):
            return -1
        day += 1

print(f())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

day = 0
setn = set(range(n))
while True:
    popped = 0
    plist = set()
    zeros = 0
    tmpns = copy.copy(setn)
    for i in setn:
        if len(a[i]) == 0:
            tmpns.remove(i)
            continue
        if i in plist:
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if num in plist:
            continue
        if a[num][0] - 1 == i:
            plist.add(num)
            a[i].popleft()
            a[num].popleft()
            popped += 1
    if popped == 0:
        if len(tmpns) == 0:
            break
        else:
            day = -1
            break
    day += 1

print(day)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
d={}
for i in range(N):
	d[i+1] = list(map(int,input().split()))[::-1]


cnt=0
while True:
	
	f=True
	for i in d:
		if d[i]!=[]:
			f=False
	if f:
		print(cnt)
		break
	
	f=True
	p=[]
	for i in d:
		if d[i]!=[]:
		 	j=d[i][-1]
		 	if d[j]!=[] and d[j][-1]==i and (i not in p) and (j not in p): 
		 		d[i].pop()
		 		d[j].pop()
		 		p.append(i)
		 		p.append(j)
		 		f=False
	if f:
		print(-1)
		break
	
	cnt+=1

Submission status: Time Limit Exceeded

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


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


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

cnt = [0] * N

S = []
for i in range(N):
  t = A[i][cnt[i]] - 1
  if i == A[t][cnt[t]] - 1:
    if cnt[i] != N - 2:
      S.append(i)

ans = 1
while S:
  ans += 1
  L = [True] * N
  for i in S:
    cnt[i] += 1
  T = []
  for i in S:
    if L[i]:
      t = A[i][cnt[i]] - 1
      if i == A[t][cnt[t]] - 1:
        if cnt[i] != N - 2:
          L[i] = False
          T.append(i)
        if L[t]:
          L[t] = False
          if cnt[t] != N - 2:
            T.append(t)
  S = T

for i in range(N):
  if cnt[i] != N - 2:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n
    aconditions = {}
    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)
        aconditions[i] = set(al)

    # print(agrid)
    # print(aconditions)

    ans = 0
    while True:
        match = set()
        for i in range(n):
            if len(aconditions[i]) == 0 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]]
            if len(aconditions[target]) == 0 or target in match:  # もう全部対戦済み or この日対戦済み
                continue

            if agrid[target][agrid_pointer[target]] != i:  # 次対戦できない
                continue

            # can match
            aconditions[i].remove(target)
            agrid_pointer[i] += 1

            aconditions[target].remove(i)
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)
            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for v in aconditions.values():
        if len(v) != 0:
            print(-1)
            return
    print(ans)


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
    while cnt > 0:
        days += 1
        now = cnt
        V = [0]*N
        for i in range(N):
            if V[i] == 1 or not A[i]:
                continue
            a = A[i][0]
            a -= 1
            if V[a] == 1 or not A[a]:
                continue
            if i+1 == A[a][0]:
                V[a] = 1
                V[i] = 1
                A[a].popleft()
                A[i].popleft()
                cnt -= 2
        if now == cnt:
            print(-1)
            return
    print( days)

                        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: a-1, As))))
  A.append(As)
#print(A)
d = 0
n = 0
while True:
  s = set()
  n2 = 0
  for i in range(N):
    if A[i] == []:
      continue
    j = A[i][-1]
    if i in s or j in s:
      continue
    if A[j] == []:
      continue
    if A[j][-1] == i:
      n += 1
      n2 += 1
      A[i].pop()
      A[j].pop()
      s.add(i)
      s.add(j)
  if n2 == 0:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  d += 1
print(d)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

a = []

for i in range(N):

    A = list(map(int,input().split()))

    a.append(A)

day = 0
flag = True
end = 0

while end < N and day < N*(N-1)//2:

    day += 1

    Q = []
    flag = False

    for i in range(N):


        if len(a[i]) > 0  and a[ a[i][0]-1 ][0] == i + 1 and a[i][0] > i + 1:

            Q.append(a[i][0])
            Q.append(i + 1)

            flag = True

    if not flag:
        break

    #print (a,Q)

    for q in Q:
        del a[q-1][0]

        if len(a[q-1]) == 0:
            end += 1



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

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    for w in range(10 ** 15):
        cnt += 1
        f = [False] * n
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        f[i] = True
                        f[mt[i]-1] = True
        bb = False
        for i in range(n):
            if f[i]:
                if ls[i] + 1 < n - 1:
                    ls[i] += 1
                    bb = True
                else:
                    ls[i] = -1
        b = True
        for i in range(n):
            if ls[i] != -1:
                b = False
                break
        if b:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

day = 0
while True:
    day += 1
    used = [0] * n
    for i in range(n):
        if a[i] and a[a[i][0]] and not used[i] and not used[a[i][0]] and a[a[i][0]][0] == i:
            used[i] = 1
            used[a[i][0]] = 1
            del a[a[i][0]][0]
            del a[i][0]
    if sum([len(i) for i in a]) == 0:
        print(day)
        break
    if sum(used) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    for i in range(10 ** 15):
        cnt += 1
        f = [False] * n
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        f[i] = True
                        f[mt[i]-1] = True
        bb = False
        for i in range(n):
            if f[i]:
                if ls[i] + 1 < n - 1:
                    ls[i] += 1
                    bb = True
                else:
                    ls[i] = -1
        b = True
        for i in range(n):
            if ls[i] != -1:
                b = False
                break
        if b:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())
table = [None for i in range(N)]

for i in range(N):
    table[i] = list(map(int, input().split()))
    for j in range(len(table[i])):
        table[i][j] -= 1

nissuu = 0
siaisuu = 0

while siaisuu < N * (N - 1) // 2:
    rireki = []
    zoubunn = 0

    yatta = [False for _ in range(N)]
    for i in range(N):
        if yatta[i]:
            continue

        if len(table[i]) == 0:
            continue

        aite = table[i][0]
        if len(table[aite]) == 0:
            print(-1)
            sys.exit(0)

        if yatta[aite]:
            continue

        if table[aite][0] != i:
            continue

        siaisuu += 1
        zoubunn += 1
        table[i] = table[i][1:]
        table[aite] = table[aite][1:]
        yatta[i] = True
        yatta[aite] = True
        rireki.append((i, aite))

    if zoubunn == 0:
        print(-1)
        sys.exit(0)

    nissuu += 1
    # print(rireki)

print(nissuu)

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

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

        if len(pool) == 0:
            if not all(len(a) == 0 for a in A):
                print(-1)
                return
        for i in pool:
            A[i].pop(0)
        count += 1
        if all(len(a) == 0 for a in A):
            print(count)
            return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

        if i == r and l not in s and r not in s:
            s.add(l)
            s.add(r)
            f = True
        else:
            L[i].appendleft(l)
            L[l].appendleft(r)

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

dfs()

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

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]

A.append([-1])

def f():
    can_use = []
    for n in range(N):
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
    return len(can_use)

answer = 0
rest = N*(N-1)
while True:
    answer += 1
    x = f()
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
alist=[]
nowlist=[]
klist=[]
poplist=[]
nextlist=[]
incre=0
error=0
day=0

for i in range(n):
    alist.append(list(map(int, input().split())))

for i in range(n):
    nowlist.append(0)
    poplist.append(i)
    nextlist.append(i)

koho=[]

while error==0 and incre<n*(n-1):
    for i in range(n):
        if nowlist[i]<n-1 and i in nextlist:
            small=sorted([i+1, alist[i][nowlist[i]]])
            koho.append(small)
    koho=sorted(koho)
    swit=0
    poplist=[]
    nextlist=[]
    for i in range(len(koho)-1):
        if koho[i]==koho[i+1]:
            nowlist[koho[i][0]-1]+=1
            nowlist[koho[i][1]-1]+=1
            poplist.append(i)
            poplist.append(i+1)
            nextlist.append(koho[i][0]-1)
            nextlist.append(koho[i][1]-1)
            incre+=2
            swit=1
    day+=1
    for i in range(len(poplist)):
        koho.pop(poplist[len(poplist)-i-1])
    if swit==0:
        day=-1
        error=1

print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import collections

As = [collections.deque()]
for i in range(N):
    deq = collections.deque()
    for a in map(int, input().split()):
        deq.append(a)
    As.append(deq)

d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
while sw:
    tab = set()
    c = 0
    for i in range(1, N + 1):
        if len(As[i]) == 0:
            continue
        a, b = min(i, As[i][0]), max(i, As[i][0])
        if (a, b) in tab:
            ms += 1
            c += 1
            if ms == msMax:
                sw = False
                break
            As[a].popleft()
            As[b].popleft()
        else:
            tab.add((a, b))
    if c == 0:
        d = 0
        break
    d += 1
print(d - 1)

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    while True:
        cnt += 1
        f = [False] * n
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        f[i] = True
                        f[mt[i]-1] = True
        bb = False
        for i in range(n):
            if f[i]:
                if ls[i] + 1 < n - 1:
                    ls[i] += 1
                    bb = True
                else:
                    ls[i] = -1
        b = True
        for i in range(n):
            if ls[i] != -1:
                b = False
                break
        if b:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

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

from collections import deque

N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]

A.append([-1])

def f():
    can_use = [n for n in range(N) if A[A[n][-1]][-1] == n]
    for n in can_use:
        A[n].pop()
    return len(can_use)

answer = 0
rest = N*(N-1)
while True:
    answer += 1
    x = f()
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)

Submission status: Time Limit Exceeded

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

# print(A_array)

s_index = [0] * N

ans_date = 1
finish_player = 0
while(1):
    flag = 0
    match_array = [0] * N
    for i in range(N):
        if match_array[i] == 1 or s_index[i] == N - 1:
            continue
        vs = A_array[i][s_index[i]] - 1
        # print(i,vs)
        if A_array[vs][s_index[vs]] - 1 == i:
            match_array[i] = 1
            match_array[vs] = 1
            flag = 1
    if flag == 0:
        print(-1)
        exit()
    # print(s_index,match_array)
    for i, match in enumerate(match_array):
        if match == 1:
            s_index[i] += 1
            if s_index[i] == N - 1:
                finish_player += 1
    if finish_player == N:
        break
    ans_date += 1
print(ans_date)

Submission status: Time Limit Exceeded

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

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

remain_games = n * (n-1) // 2
ans = 0
while remain_games:
    flag = [0] * n
    update = False
    for i in range(n):
        if len(a[i]) == 0 or len(a[ a[i][0] ]) == 0:
            continue
        if flag[i] == 0 and a[ a[i][0] ][0] == i and flag[ a[i][0] ] == 0:
            b = a[i].popleft()
            _ = a[b].popleft()
            flag[i] = 1
            flag[b] = 1
            remain_games -= 1
            # print(ans, i, b)
            update = True
    if not update:
        ans = -1
        break
    ans += 1

print(ans)