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:
def slove():
    import sys
    import copy
    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
    bbb = 0

    for i in range(n):
        if ls[i] != -1:
            mt[i] = a[i][ls[i]]

    it = [i for i in range(n)]

    for w in range(10 ** 15):
        cnt += 1
        bb = False
        update = []
        f = [False] * n
        for i in it:
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        bb = True
                        f[i] = True
                        f[mt[i]-1] = True
                        if ls[i] + 1 < n - 1:
                            ls[i] += 1
                            update.append(i)
                        else:
                            ls[i] = -1
                            bbb += 1

                        if ls[mt[i]-1] + 1 < n - 1:
                            ls[mt[i]-1] += 1
                            update.append(mt[i]-1)
                        else:
                            ls[mt[i]-1] = -1
                            bbb += 1
        it = copy.deepcopy(update)
        for i in update:
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        if bbb == n:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def seek_candidates(current_A):
    can_set = []
    want_set = []
    for n in range(N):
        if(current_A[n+1] != []):
            tmp = set([n+1, current_A[n+1][0]])
            if tmp in want_set:
                can_set.append(tmp)
            else:
                want_set.append(tmp)
    return can_set

def make_next_A(current_A, battles):
    next_A = current_A
    for battle in battles:
        for b in battle:
            next_A[b] = current_A[b][1:]
    return next_A

def make_battle_set(can_set):
    battle_set = []
    battle_players = set()
    for c in can_set:        
        if(c & battle_players == set()):
            battle_set.append(list(c))
            battle_players = battle_players | c
    return battle_set

import collections

A = collections.Counter()
N = int(input())
for n in range(N):
    A[n+1] = list(map(int, input().split()))

success_flag = False
loop_count = 0
currnet_A = A
remain_battles = int(N*(N-1)/2)

while(True):
    loop_count += 1
    can_set = seek_candidates(currnet_A)
    if(can_set == []):
        break
    battle_set = make_battle_set(can_set)
    currnet_A = make_next_A(currnet_A, battle_set)
    remain_battles -= len(battle_set)
    if(remain_battles <= 0):
        success_flag = True
        break
if(success_flag):
    print(loop_count)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())
ans = 0
a = [[int(i)-1 for i in input().split()] for _ in range(n)]
cur = [0 for _ in range(n)]
cur2 = [0 for _ in range(n)]


for k in range(n * (n - 1) // 2):
  f = True
  for i in range(n):
    c = cur[i]
    if c >= n - 1:
      pass
    else:
      op = a[i][c]
      if cur[op] >= n - 1:
        pass
      else:
        op = a[i][c]
        if i == a[op][cur[op]] and c < n-1:
          cur2[i] += 1
          f = False
  if f:
    break
  else:
    ans += 1
  cur = copy.deepcopy(cur2)

for c in cur:
  if c != n - 1:
    fl = False
  else:
    fl = True

if fl:
  print(ans)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())

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

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

a.append([-1])
status.append([0])

changed = 0
end = 0

while end != n:
    for i in range(n):
        enemy = a[i][status[i][0]] - 1
        if a[enemy][status[enemy][0]] == i + 1:
            day = max(status[i][1], status[enemy][1])
            status[i][1] = day + 1
            status[enemy][1]= day + 1

            if status[i][0] == n-2:
                a[i][n-2] = n + 1
                end += 1
            else:
                status[i][0] += 1

            if status[enemy][0] == n-2:
                a[enemy][n-2] = n + 1
                end += 1
            else:
                status[enemy][0] += 1

            changed = 1

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

ans = 0
for i in range(n):
    ans = max(status[i][1], ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

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

match_num = (n * (n - 1)) // 2
match_cnt = 0

fin = [0 for _ in range(n)]
update = True
day = 0
while True:
    update = False
    day += 1
    skip = set()
    for i, d in enumerate(fin):
        if i in skip:
            continue
        skip.add(i)
        if d >= n-1:
            continue

        op = league[i][d]
        if op in skip:
            continue

        me = league[op][fin[op]]

        if i == me:
            update = True
            match_cnt += 1
            fin[i] += 1
            fin[op] += 1
            skip.add(op)

    if match_cnt == match_num:
        break

    if not update:
        day = -1
        break

print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

league = [ [ int(v)-1 for v in input().split() ] for i in range(n) ]
done = [ 0 for i in range(n) ]

def day():
    day_match = 0
    match = [ 0 for i in range(n) ]
    for i in range(n):
        if match[i] == 0:
            j = league[i][done[i]]
            if i != j and league[j][done[j]] == i and match[j]== 0:
                match[i] = 1
                match[j] = 1
                day_match += 1
                if done[i] < n-2:
                    done[i] += 1
                if done[j] < n-2:
                    done[j] += 1
    return day_match

cal_match = (n*n-n) // 2
total_match = 0
cont = 1
d = 0
while cont:
    d += 1
    one_day_match = day()
    total_match += one_day_match

    if one_day_match == 0:
        cont = 0
        print(-1)
    elif total_match == cal_match:
        cont = 0
        print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
new_ls = []
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new_ls.append(tuple(sorted([i + 1, inp[0]])))
cur_stage.update(new_ls)

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    new_ls = []
    for i, j in battle_dict.items():
        if len(j) > 0:
            new_ls.append(tuple(sorted([i, j[0]])))
    cur_stage.update(new_ls)
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#El Patron
from collections import deque

X = int(input())
Z = [deque() for _ in range(X + 1)]
for i in range(1, X + 1):
    for e in map(int, input().split()):
        Z[i].append(e)

DAYS = [1 for _ in range(X + 1)]
empty_queues = 0
while empty_queues < X:
    matched = False
    for i in range(1, X + 1):
        if len(Z[i]) == 0:
            continue
        comp = Z[i].popleft()
        com = Z[comp].popleft()
        if com == i:
            matched = True
            date = max(DAYS[i], DAYS[comp]) + 1
            DAYS[i] = date
            DAYS[comp] = date
            if len(Z[i]) == 0:
                empty_queues += 1
            if len(Z[comp]) == 0:
                empty_queues += 1
        else:
            Z[i].appendleft(comp)
            Z[comp].appendleft(com)
    if not matched:
        print(-1)
        exit(0)
print(max(DAYS[1:]) - 1)

Submission status: Time Limit Exceeded

Solution code:
def scheduler(N, A):
    days = 0
    while True:
        games = []
        no_player = True
        for i in range(N):
            if len(A[i]):
                no_player = False
                oppo = A[i][-1] -1
                if A[oppo][-1] - 1 == i:
                    games.append(i)
        if no_player:
            break
        days += 1
        if len(games) == 0:
            return(-1)
        for game in games:
            A[game].pop()
    return(days)

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

print(scheduler(N, A))

Submission status: Time Limit Exceeded

Solution code:
# pypy ver.
def judge_and_count(A_lst, already_played, played_count):
    count = 0
    roop_count = 0##########
    while sum(played_count) < N*(N-1): # 10**3
        new_play = False
        for i in range(1, N+1): # 10**3
            if len(A_lst[i]) > 0 and already_played[i] == 0:
                p1 = i
                p2 = A_lst[i][0]
                if len(A_lst[p2]) == 0:
                    return -1
                if already_played[p2] == 1:
                    continue
                if A_lst[p2][0] == p1:
                    already_played[p1] = 1
                    already_played[p2] = 1
                    A_lst[p1].pop(0)
                    A_lst[p2].pop(0)
                    played_count[p1] += 1
                    played_count[p2] += 1
                    new_play = True
                    if roop_count > 10**4:########
                        return -1#########
        count += 1

        for i in range(len(already_played)): # 10**3
            already_played[i] = 0
        if not new_play:
            return -1
    
    return count


N = int(input())

already_played = [0]*(N+1)
played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, already_played, played_count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
N = int(input())
# A_i,j = A[i-1][j-1]
A = [list(map(int,input().split(' '))) for i in [0]*N]

dic = defaultdict(int)
ns = [0] * N

ls = range(1,N+1)
ans = 0
while(True):
	new_ls = set([])
	for i in ls:
		if ns[i-1] >= N-1:
			continue
		j = A[i-1][ns[i-1]]
		dic[(i*j,i+j)] += 1
		if dic[(i*j,i+j)] == 2:
			new_ls.add(i)
			new_ls.add(j)
	if not new_ls:
		break
	for ind in new_ls:
		ns[ind-1] += 1
	ls = new_ls
	ans += 1

for i in range(N):
	if ns[i] != N-1:
		print(-1)
		exit()
print(ans)

Submission status: Time Limit Exceeded

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


class player:
    def __init__(self, rivals):
        self.rivals = rivals
        self.index = 0

    def get(self):
        return self.rivals[self.index]

    def next(self):
        self.index += 1

        if self.index >= len(self.rivals):
            return False
        else:
            return True


n = int(input())

players = [None]
for _ in range(n):
    tmps = list(map(int, input().split()))
    players.append(player(tmps))


max_match = int(n*(n-1)/2)
flag = [True]*(n+1)
flag[0] = False

for i in range(1, max_match+1):
    tmp_flag = [True]*(n+1)

    for p in range(1, n+1):
        if flag[p] and tmp_flag[p]:
            r = players[p].get()
            if flag[r] and tmp_flag[r]:
                if p == players[r].get():
                    if not players[r].next():
                        flag[r] = False
                    tmp_flag[r] = False

                    if not players[p].next():
                        flag[p] = False

            tmp_flag[p] = False

    s = sum(flag)
    if s == 0:
        break

if s == 0:
    print(i)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from collections import deque

N = int(input())

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

ans = 0

len_count = [0]*N
while sum(len_count) < N:
    update = False
    done = [0]*(N)
    for i in range(N):
        if done[i] == 1: continue
        if len(A[i]) == 0: continue
        tmp = A[i][0]-1
        if done[tmp] == 1: continue
        if len(A[tmp]) !=0 and A[tmp][0]-1 == i:
            update = True
            done[i] = 1
            done[tmp] = 1
            A[i].popleft()
            A[tmp].popleft()
            if len(A[i])==0:
                len_count[i] = 1
            if len(A[tmp])==0:
                len_count[tmp] = 1
    if not(update):
        print(-1)
        sys.exit()
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

output = 0
memo = [0] * N
newmemo = [0] * N
owari = [0] * N
flag = 0
while flag < N:
    ng = 0
    for i in range(N):
        check = A[i][memo[i]]-1
        if i==A[check][memo[check]]-1:
            if memo[i] < N-2:
                newmemo[i]+=1
            elif (memo[i] == N-2) and (owari[i]==0):
                owari[i] = 1
                flag += 1
            elif (memo[i] == N-2) and (owari[i]==1):
                continue
        else:
            ng += 1
    if ng == N:
        output = -1
        break
    memo = newmemo[:]
    output += 1

print(output)

Submission status: Time Limit Exceeded

Solution code:
#e
n = int(input())
A = [[]] * (n+1)
for i in range(1,n+1):
    A[i] = list(map(int, input().split()))

day = 0
rest = n * (n-1) /2
flg = False
while rest != 0 and flg == False:
    day += 1
    play_in_date = 0
    in_play = []
    for i in range(1,n+1):
        if A[i]!=[] and A[A[i][0]]!=[] and A[A[i][0]][0] == i:
            p1, op = i, A[i][0]
            if (p1 not in in_play) and (op not in in_play):
                in_play.append(p1)
                in_play.append(op)
                A[p1].remove(op)
                A[op].remove(p1)
                play_in_date += 1
                rest -= 1
                #print('day: ',day,' rest ',rest, ' p1: ',p1,'op: ',op)
    if play_in_date == 0:
        flg = True
if flg == True:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  from collections import deque

  N = int(input())
  table = []
  for i in range(N):
    H = deque()
    A = input().split()
    for a in A:
      H.append(int(a))
    table.append(H)
      
  count = 0
  for k in range(10**6):
    flag = 0
    game = [0]*N
    count += 1
    for i in range(N):
      if game[i] == 0 and len(table[i]) != 0:
        x = table[i][0]-1
        if game[x] == 0 and table[x][0] == i+1:
#          print(count,i,x)
          table[i].popleft()
          table[x].popleft()
          game[i] = 1
          game[x] = 1
          flag = 1
    if any(table) == 0:
      print(count)
      exit()
    if flag == 0:
      print(-1)
      exit()
  print(count)  

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import copy

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

ind = [0 for i in range(n)]
ind_copy = copy.copy(ind)

# a = np.array(a)
# a = a - 1

ans = 0
while True:
    kanou = 0
    ans += 1
    senshu = [i for i in range(n)]
    while senshu != []:
        i = senshu.pop()
        if ind[i] <= n-2:
            player = a[i][ind[i]]
        else:
            continue
        if ind[player-1] <= n-2:
            player_vs = a[player-1][ind[player-1]]
        else:
            continue
        if i == player_vs-1:
            senshu.remove(player-1)
            kanou = 1
            ind_copy[i] = ind[i] + 1
            ind_copy[player-1] = ind[player-1] + 1
    if kanou == 0:
        hantei = 0
        for i in range(n):
            if ind[i] < n-2:
                hantei = 1
        if hantei == 1:
            ans = -1
        break
    ind = copy.copy(ind_copy)

if ans != -1:
    print(ans - 1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


def dfs(root, links):
    status = {}
    topological = []
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            q.append((v, 1))
            status[v] = 1
            d += 1
            for u in links[v]:
                if u in status:
                    if status[u] == 1:
                        return False
                else:
                    q.append((u, 0, d))
        else:
            v = node[0]
            status[v] = 2
            topological.append(v)
    topological.reverse()
    return topological


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

topological = dfs(may_root, links)
if topological == False:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))

Submission status: Time Limit Exceeded

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()

match = [0 for i in range((n*(n-1))//2)]
child = [[] for i in range((n*(n-1))//2)]
isroot = [True for i in range((n*(n-1))//2)]


def bfs():
    q = deque([])
    for root, rt in enumerate(isroot):
        if rt:
            q.append(root)
            match[root] = 1
    # print(match)
    while(q):
        item = q.popleft()
        # print(q, item, child[item])
        for ch in child[item]:
            if match[ch] < match[item] + 1:
                match[ch] = match[item] + 1
                q.append(ch)

    return




for idd in range(n):
    nums = getList()
    i = idd + 1
    for j,k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i,j)
        iii, k = min(i, k), max(i,k)
        idx1 = ((j-1)*(j-2))//2 + (ii-1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        isroot[idx2] = False
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)

#
# print(child)
# print(isroot)
# # sys.exit()

bfs()
# print("gg")
ans = 1
for m in match:
    if m > ans:
        ans = m
    if m == 0:
        print(-1)
        sys.exit()

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
A = []
for i in range(N):
    A.append(deque([sorted([int(item), i + 1]) for item in input().split()]))

current = defaultdict(lambda: (0, 0))
day = 0
while sum([len(row) for row in A]) > 0:
    pre = deepcopy(current)
    day += 1
    for i in range(N):
        if current[i + 1] == (0, 0):
            if len(A[i]) > 0:
                current[i + 1] = A[i].popleft()
    for n in range(1, N + 1):
        for m in range(n + 1, N + 1):
            if current[n] == current[m] and current[n] != (0, 0):
                current.pop(n)
                current.pop(m)
    if current == pre:
        print(-1)
        break
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
P = [0] * N
g = []
ans = 0
f = True
while f is True:
    f = False
    for i in range(N):
        if i in g:
            continue
        k = A[i][P[i]] - 1
        if k in g:
            continue
        if A[k][P[k]] - 1 == i:
            g.append(i)
            g.append(k)
            if N - 2 > P[i]:
                P[i] += 1
                f = True
            if N - 2 > P[k]:
                P[k] += 1
                f = True
    ans += 1
    g = []
for p in P:
    if p != N - 2:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

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

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 sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = []
    for _ in range(N):
        q = collections.deque(map(int, input().split()))
        Q.append(q)
        
    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if len(Q[i]) == 0 or gamed[i] != 0:
                continue
            for j in range(i+1, len(Q)):
                if len(Q[j]) == 0 or gamed[j] != 0:
                    continue
                if Q[i][0] == j+1 and Q[j][0] == i+1:
                    Q[i].popleft()
                    Q[j].popleft()
#                    print("game:", j+1, i+1, days)
                    b = True
                    gamed[i] = 1
                    gamed[j] = 1
                    break
        days += 1
        if not b:
            print(-1)
            return
        if all(len(q) == 0 for q in Q):
            break

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

Submission status: Time Limit Exceeded

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

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

for _ in range(total_match):
    day+=1
    today_match=deque([])

    for i,li in enumerate(league):
        if not i in today_match and li:
            m=li[0]-1
            lm=league[m]
            if not m in today_match and lm and lm[0]-1==i:
                today_match.append(li.popleft()-1)
                today_match.append(lm.popleft()-1)
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def solve():
    N = inp()
    AA = [inpl() for _ in range(N)]
    itrs = [0]*N
    ans = cnt = 0

    while True:
        next = set()
        for x,itr in enumerate(itrs):
            if itr < N-1:
                t = AA[x][itr] - 1
                if AA[t][itrs[t]]-1 == x:
                    next.add(x)

        for n in next:
            itrs[n] += 1
            if itrs[n] == N-1:
                cnt += 1

        if len(next) == 0:
            for x in itrs:
                if x != N-1:
                    return -1
            return ans

        ans += 1

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

Submission status: Time Limit Exceeded

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

days = 0

while True:
    remains = sum(len(a[i]) for i in range(n))
    if remains == 0:
        break
    days += 1
    played = []
    for i in range(n):
        if i in played:
            continue
        if len(a[i]) > 0:
            op = a[i][0] - 1
            if op in played:
                continue
            if a[op][0] - 1 == i:
                del a[i][0]
                del a[op][0]
                played.append(i)
                played.append(op)

    if len(played) == 0:
        days = -1
        break

print(days)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

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

progress_list = [0] * N
next_list = [a[0] - 1 for a in A]
done_match = 0

day_limit = N * (N - 1) // 2 + 1
for i in range(day_limit):
    exhausted = [0] * N

    for man_idx in range(N):
        opponent_idx = next_list[man_idx]
        if (opponent_idx == -1) or exhausted[opponent_idx] or exhausted[man_idx]:
            continue
        opponents_opponent = next_list[opponent_idx]

        if man_idx == opponents_opponent:
            # print('day', i + 1, ',', man_idx + 1, opponent_idx + 1)
            exhausted[man_idx] += 1
            progress_list[man_idx] += 1
            if progress_list[man_idx] >= N - 1:
                next_list[man_idx] = -1
            else:
                next_list[man_idx] = A[man_idx][progress_list[man_idx]] - 1
            exhausted[opponent_idx] += 1
            progress_list[opponent_idx] += 1
            if progress_list[opponent_idx] >= N - 1:
                next_list[opponent_idx] = -1
            else:
                next_list[opponent_idx] = A[opponent_idx][progress_list[opponent_idx]] - 1
            done_match += 1

    if sum(exhausted) == 0:
        break

    if done_match == N * (N - 1) // 2:
        print(i + 1)
        exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
li = deque(list(map(int,input().split())) for i in range(1,n+1))

cnt = 0
check = []
play = 0
tamel = []
s = 0

while play < n*(n-1) // 2:
    s = play
    for i in range(1,n+1):
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][0]
        if li[temp-1][0] == i:
            tamel.append(i-1)
            tamel.append(temp-1)
            play += 1
            check.append(temp)
    cnt += 1
    for i in tamel:
        del li[i][0]
    tamel = []
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		edge[match_dict[(x,y)]].append(match_dict[(z,w)])
		parent[match_dict[(z,w)]].append(match_dict[(x,y)])
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		if finish[c]:
			continue
		finish[c] = True
		for e in edge[c]:
			if finish[e]:
				continue
			if all([finish[p] for p in parent[e]]):
				new_candidate.append(e)
	day += 1
	candidate = new_candidate

all_finished = all(finish)
if all_finished:
	print(day)
else:
	print(-1)