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())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = [False] * (n+1)
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n+1):
    if cursor[i] < n-1:
      j = table[i][cursor[i]]
      if not is_matched[i] and table[j][cursor[j]] == i and not is_matched[j]:
        match += 1
        cursor[i] += 1
        is_matched[i] = True
        cursor[j] += 1
        is_matched[j] = True
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched =  [False] * (n+1)
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
ans = 0
tmp = 0
total = (N * (N - 1)) // 2

for i in range(total):
    sLst = [0] * N
    for j in range(N):
        if len(a[j]) != 0 and len(a[a[j][0] - 1]) != 0:
            if sLst[j] == 0 and sLst[a[j][0] - 1] == 0:
                if a[a[j][0] - 1][0] == j + 1:
                    sLst[a[j][0] - 1] = a[a[j][0] - 1].pop(0)
                    sLst[j] = a[j].pop(0)
                    tmp += 1
                    total -= 1
    if total == 0:
        ans += 1
        break

    if tmp == 0:
        print(-1)
        exit()

    tmp = 0
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

node_list = []

def get_key(a, b):
    if a > b:
        return (a << 10) + b
    else:
        return (b << 10) + a

def link(parent, child):
#    parent.next[child.hash] = child
    child.prev[parent.hash] = parent

def main():

    table = {}

    for i in range(0, N):
        array = [int(v) - 1 for v in input().split(' ')]

        j = array[0]
        key0 = get_key(i, j)

        if not key0 in table:
            e = E(i, j)
            table[key0] = e
            node_list.append(e)
        p = table[key0]

        for k in range(1, len(array)):
            j = array[k]
            key = get_key(i, j)

            if not key in table:
                e = E(i, j)
                table[key] = e
                node_list.append(e)
            n = table[key]

            link(p, n)

            p = n

class E:
    def __init__(self, a, b):
        if a > b:
            self.hash = (a << 10) + b
            #self.name = "%d,%d" % (a, b)
        else:
            self.hash = (b << 10) + a
            #self.name = "%d,%d" % (a, b)

#        self.next = {}
        self.prev = {}

#    def get_name(self):
#        return self.name

main()    

days = 0
while len(node_list) > 0:
    days += 1
    close_list = []
    open_list = []

    for n in node_list:
        if len(n.prev) == 0:
            #print("game: ", n.get_name())
            close_list.append(n)
        else:
            open_list.append(n)

    if len(close_list) == 0:
        print("-1")
        exit()

    for n in close_list:
        for o in open_list:
            if n.hash in o.prev:
                o.prev.pop(n.hash)

    node_list = open_list

print(days)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = [False] * (n+1)
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    for j in range(i+1, n+1):
      if cursor[i] < n-1 and table[i][cursor[i]] == j and not is_matched[i] and table[j][cursor[j]] == i and not is_matched[j]:
        match += 1
        cursor[i] += 1
        is_matched[i] = True
        cursor[j] += 1
        is_matched[j] = True
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched =  [False] * (n+1)
print(d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

node_list = []

def get_key(a, b):
    if a > b:
        return (a << 10) + b
    else:
        return (b << 10) + a

def link(parent, child):
    parent.next[child.hash] = child
    child.prev[parent.hash] = parent

def main():

    table = {}

    for i in range(0, N):
        array = [int(v) - 1 for v in input().split(' ')]

        j = array[0]
        key0 = get_key(i, j)

        if not key0 in table:
            e = E(i, j)
            table[key0] = e
            node_list.append(e)
        p = table[key0]

        for k in range(1, len(array)):
            j = array[k]
            key = get_key(i, j)

            if not key in table:
                e = E(i, j)
                table[key] = e
                node_list.append(e)
            n = table[key]

            link(p, n)

            p = n

class E:
    def __init__(self, a, b):
        if a > b:
            self.hash = (a << 10) + b
            self.name = "%d,%d" % (a, b)
        else:
            self.hash = (b << 10) + a
            self.name = "%d,%d" % (a, b)

        self.next = {}
        self.prev = {}

    def get_name(self):
        return self.name

main()    

days = 0
while len(node_list) > 0:
    days += 1
    close_list = []
    open_list = []

    for n in node_list:
        if len(n.prev) == 0:
            #print("game: ", n.get_name())
            close_list.append(n)
        else:
            open_list.append(n)

    if len(close_list) == 0:
        print("-1")
        exit()

    for n in close_list:
        for o in open_list:
            if n.hash in o.prev:
                o.prev.pop(n.hash)

    node_list = open_list

print(days)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

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
    n = N - 1
    for i in range(N):
        A[i].reverse()
    done = list(range(N))
    while True:
        used = [False] * N
        tmp_done = []
        for i in done:
            if not used[i] and len(A[i]) > 0:
                j = A[i][-1] - 1
                if not used[j] and len(A[j]) > 0 and A[j][-1] - 1 == i:
                    used[i] = True
                    used[j] = True
                    A[i].pop()
                    A[j].pop()
                    #p[i] += 1
                    #p[j] += 1
                    tmp_done.append(i)
                    tmp_done.append(j)
        if len(tmp_done) == 0:
            for i in range(N):
                #if p[i] < n:
                if len(A[i]) > 0:
                    print(-1)
                    return
            break
        done = tmp_done
        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)) - 1 for _ in range(N-1) ] for _ in range(N) ]  # type: "List[List[int]]"
    A = [list(map(int, input().split())) for i in range(N)]
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [] # i番目の選手のj番目の試合の相手
waiting = [0 for i in range(n)] # i番目の選手が何試合目をしたいのか
count = 0 #試合日数のカウント
for _ in range(n):
    a.append(list(map(int, input().split())))

for i in range(n * (n - 1) // 2):
    register = [0 for _ in range(n)]
    flag = 0
    for j in range(n):
        if register[j] == 1:
            continue
        j_waiting = waiting[j]
        if j_waiting == n - 1:
            continue
        enemy = a[j][j_waiting] - 1
        if register[enemy] == 1:
            continue
        enemy_waiting = waiting[enemy]
        if enemy_waiting == n - 1:
            continue
        enemy_enemy = a[enemy][enemy_waiting] - 1
        if j == enemy_enemy:
            waiting[j] += 1
            waiting[enemy] += 1
            register[j] = 1
            register[enemy] = 1
            flag = 1
    if flag == 0:
        count = -1
        break
    if min(waiting) == n - 1:
        count = i + 1
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = [False] * (n+1)
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n+1):
    for j in range(i+1, n+1):
      if cursor[i] < n-1 and table[i][cursor[i]] == j and not is_matched[i] and table[j][cursor[j]] == i and not is_matched[j]:
        match += 1
        cursor[i] += 1
        is_matched[i] = True
        cursor[j] += 1
        is_matched[j] = True
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched =  [False] * (n+1)
print(d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    check = [1]*n
    flg = False
    i = -1
    while sum(check) != 0:
        i += 1
        if not check[i]:
            continue
        if len(a[i]) == 0:
            check[i] = 0
            continue
        (x,y) = a[i].popleft()
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            flg = True
            check[y-1] = 0
            a[y-1].popleft()
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [] # i番目の選手のj番目の試合の相手
waiting = [0 for i in range(n)] # i番目の選手が何試合目をしたいのか
count = 0 #試合日数のカウント
for _ in range(n):
    a.append(list(map(int, input().split())))

for i in range(n * (n - 1) // 2):
    register = [0 for _ in range(n)]
    flag = 0
    for j in range(n):
        #print(j)
        if register[j] == 1:
            continue
        j_waiting = waiting[j]
        #print(j_waiting)
        if j_waiting == n - 1:
            continue
        enemy = a[j][j_waiting] - 1
        #print(enemy)
        if register[enemy] == 1:
            continue
        enemy_waiting = waiting[enemy]
        if enemy_waiting == n - 1:
            continue
        enemy_enemy = a[enemy][enemy_waiting] - 1
        if j == enemy_enemy:
            #print('{} vs {}'.format(j+1, enemy+1))
            waiting[j] += 1
            waiting[enemy] += 1
            register[j] = 1
            register[enemy] = 1
            flag = 1
        #print(register)
    #print(min(waiting))
    if flag == 0:
        count = -1
        break
    if min(waiting) == n - 1:
        count = i + 1
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    check = [1]*n
    flg = False
    for i in range(n):
        if not check[i]:
            continue
        if len(a[i]) == 0:
            check[i] = 0
            continue
        (x,y) = a[i].popleft()
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            flg = True
            check[y-1] = 0
            a[y-1].popleft()
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def topological_sort(root, links, in_count):
    topological = []
    q = root
    while q:
        v = q.pop()
        topological.append(v)
        for u in links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                q.add(u)
    return topological


n = int(input())
match_count = n * (n - 1) // 2

offsets = [0]
tmp = -2
for i in range(1, n + 1):
    offsets.append(tmp)
    tmp += n - i - 1

roots = set()
in_links = [set() for _ in range(match_count)]
out_links = [set() for _ in range(match_count)]

for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    prev = offsets[i] + j if i < j else offsets[j] + i
    roots.add(prev)

    for j in aaa[1:]:
        key = offsets[i] + j if i < j else offsets[j] + i
        out_links[prev].add(key)
        in_links[key].add(prev)
        prev = key

in_count = list(map(len, in_links))
roots = {r for r in roots if in_count[r] == 0}

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

topological = topological_sort(roots, out_links, in_count)
if len(topological) != match_count:
    print(-1)
    exit()

depth = [0] * match_count
for v in topological:
    depth[v] = max(map(depth.__getitem__, in_links[v]), default=0) + 1

print(max(depth))

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(N):
            if gamed[i] > 0 or len(Q[i]) == 0:
                continue
            j = Q[i][0] - 1
            if gamed[j] > 0 or len(Q[j]) == 0:
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = 1
                gamed[j] = 1
                games -= 1
                b = True
                continue
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
from collections import deque
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

move_in = [[[] for i in range(N)] for j in range(N)]
move_out = [[[] for i in range(N)] for j in range(N)]
cost = [[0] * N for _ in range(N)]
start_pair = []
for i in range(N):
    a_list = _li_()
    start_pair.append(a_list[0])
    for j in range(N-2):
        start = [min(i, a_list[j]), max(i, a_list[j])]
        end = [min(i, a_list[j+1]), max(i, a_list[j+1])]
        move_in[end[0]][end[1]].append((start[0], start[1]))
        move_out[start[0]][start[1]].append((end[0], end[1]))

count = 0
stack = deque([])
for i in range(N):
    pair = start_pair[i]
    if i < pair and i == start_pair[pair]:
        stack.append((i, start_pair[i]))  # 3つ目は距離
        cost[i][start_pair[i]] = 1
        count += 1


ans = 0
while stack:
    cand = stack.pop()
    for dest in move_out[cand[0]][cand[1]]:
        cost[dest[0]][dest[1]] = max(cost[dest[0]][dest[1]],
                                     cost[cand[0]][cand[1]] + 1)
        in_list = move_in[dest[0]][dest[1]]
        if in_list[0] == cand:
            del in_list[0]
        else:
            del in_list[1]
        if len(in_list) == 0:
            count += 1
            if len(move_out[dest[0]][dest[1]]) == 0:
                ans = max(ans, cost[dest[0]][dest[1]])
            else:
                stack.append(dest)

if count == (N * (N-1) // 2):
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys


def topological_sort(root, links, in_count):
    topological = []
    q = root.copy()
    while q:
        v = q.pop()
        topological.append(v)
        for u in links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                q.add(u)
    return topological


n = int(input())
match_count = n * (n - 1) // 2

offsets = [0]
tmp = -2
for i in range(1, n + 1):
    offsets.append(tmp)
    tmp += n - i - 1

roots = set()
in_links = [set() for _ in range(match_count)]
out_links = [set() for _ in range(match_count)]

for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    a, b = (i, j) if i < j else (j, i)
    prev = offsets[a] + b
    roots.add(prev)

    for j in aaa[1:]:
        a, b = (i, j) if i < j else (j, i)
        key = offsets[a] + b
        out_links[prev].add(key)
        in_links[key].add(prev)
        prev = key

in_count = list(map(len, in_links))
roots = {r for r in roots if in_count[r] == 0}

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

topological = topological_sort(roots, out_links, in_count)
if len(topological) != n * (n - 1) // 2:
    print(-1)
    exit()

depth = [0] * match_count
for v in topological:
    depth[v] = max(map(depth.__getitem__, in_links[v]), default=0) + 1

print(max(depth))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
A=[]
for i in range(n):
  A.append([int(i) for i in input().split()])
nn=n*(n-1)//2
F=[[0]*(n+1) for _ in range(n+1)]
cur=0
for i in range(1,n):
  for j in range(i+1,n+1):
    F[i][j]=cur
    F[j][i]=cur
    cur+=1
Edge=[[] for _ in range(nn)]
Deg=[0]*nn
for i in range(n):
  s=F[i+1][A[i][0]]
  for j in range(1,n-1):
    t=F[i+1][A[i][j]]
    Edge[s].append(t)
    Deg[t]+=1
    s=t
ans=0
S=[i for i in range(nn) if Deg[i]==0]
D=deque()
DD=deque(S)
while DD:
  D=DD
  DD=deque()
  while D:
    d=D.popleft()
    for g in Edge[d]:
      Deg[g]-=1
      if Deg[g]==0:
        DD.append(g)
        S.append(g)
  ans+=1
print(-1 if len(S)<nn else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import collections
import time

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i,q in enumerate(Q):
            if gamed[i] > 0 or len(q) == 0:
                continue
            j = q[0] - 1
            if gamed[j] > 0 or len(Q[j]) == 0:
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                q.popleft()
                Q[j].popleft()
                gamed[i] = 1
                gamed[j] = 1
                games -= 1
                b = True
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0]*(N+1)
A[0] = [0]*N
B = [1]*(N+1)

for i in range(N):
    a = [0]*N
    s = [int(i) for i in input().split()]
    for j in range(1,N):
        a[j] = s[j-1]
    A[i+1] = a

day = 0
match = 0
old_match = 0
limit = (N*(N-1))//2
unreached = [True]*(N+1)

flag = False

while match < limit:
    unreached = [True]*(N+1)
    for i in range(1, N):
        for j in range(i+1, N+1):
            if unreached[i] and unreached[j] and B[i] < N and B[j] < N:
                if i == A[j][B[j]] and A[i][B[i]] == j:
                    B[i] += 1
                    B[j] += 1
                    unreached[i] = False
                    unreached[j] = False
                    match += 1
                    break
                
    if old_match == match:
        flag = True
        break
    
    day += 1
    old_match = match


if flag:
    day = -1

print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = [[0] for _ in range(n)]

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

t = [a[i][0] for i in range(n)]
l = [0]*n
used = [False]*n

head = 0
day = 0

for i in range(min(n*(n-1)//2,10**4)):
    if t == [-1]*n:
        break
    while True:
        if used[head] == False:
            used[head] = True
            if used[t[head]] == False:
                if t[t[head]] == head:
                    used[t[head]] = True
                    l[head] += 1
                    l[t[head]] += 1
                    t[t[head]] = a[t[head]][l[t[head]]]
                    t[head] = a[head][l[head]]
                    head = (head + 1)%n    
                else:
                    head = (head + 1)%n
        elif used[head] == True:
            head = (head + 1)%n
        if used == [True]*n:
            day += 1
            used = [False]*n
            break

if t != [-1]*n:
    print(-1)
    exit()

print(day)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    f = defaultdict(lambda : 0)
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        if f[(x,y)] == 0 and f[(y,x)] == 1:
                flg = True
                f[(y,x)] = 0
        elif f[(x,y)] == 0:
            f[(x,y)] = 1
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
    for k,l in f.items():
        if l != 0:
            a[k[0]-1].appendleft(k)
for i in a:
    if len(i) != 0:
        print(-1)
        quit()

Submission status: Time Limit Exceeded

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

days = 0
games_amount = 0
for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl,sys
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = cl.deque()
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl,sys
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = [[0] for _ in range(n)]

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

t = [a[i][0] for i in range(n)]
l = [0]*n
used = [False]*n

head = 0
day = 0

for i in range(n*(n-1)//2):
    if t == [-1]*n:
        break
    while True:
        if used[head] == False:
            used[head] = True
            if used[t[head]] == False:
                if t[t[head]] == head:
                    used[t[head]] = True
                    l[head] += 1
                    l[t[head]] += 1
                    t[t[head]] = a[t[head]][l[t[head]]]
                    t[head] = a[head][l[head]]
                    head = (head + 1)%n    
                else:
                    head = (head + 1)%n
        elif used[head] == True:
            head = (head + 1)%n
        if used == [True]*n:
            day += 1
            used = [False]*n
            break

if t != [-1]*n:
    print(-1)
    exit()

print(day)