Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict, deque
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    v = 0
    Id = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                v += 1

    def toId(i, j):
        if i > j:
            i, j = j, i
        return Id[i][j]

    to = [[] for i in range(maxv)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n - 2):
            to[a[i][j+1]].append(a[i][j])

    visited = [False for i in range(maxv)]
    calculated = [False for i in range(maxv)]
    dp = [0 for i in range(maxv)]

    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1
            return dp[v]
        visited[v] = True
        dp[v] = 1
        for u in to[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # detected cycle
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

graph = [[] for _ in range(N ** 2)]
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)


@lru_cache(maxsize=None)
def dfs(v):
    if v in hist:
        raise
    hist.add(v)
    ret = 1
    for u in graph[v]:
        ret = max(ret, dfs(u) + 1)
    return ret


hist = set()
try:
    ans = 0
    for v in range(len(graph)):
        ans = max(dfs(v), ans)
        hist = set()
    print(ans)
except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

graph = defaultdict(list)
for i in range(N):
    for j in range(N - 2):
        a, b = i + 1, A[i][j]
        c, d = i + 1, A[i][j + 1]

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[(a, b)].append((c, d))

dist = defaultdict(int)


@lru_cache(maxsize=None)
def dfs(a, b):
    if (a, b) in hist:
        raise
    hist.add((a, b))
    ret = 1
    for c, d in graph[(a, b)]:
        ret = max(ret, dfs(c, d) + 1)
    return ret


hist = set()
try:
    ans = 0
    for a, b in list(graph.keys()):
        ans = max(dfs(a, b), ans)
        hist = set()
    print(ans)
except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.88:
        print(n*(n-1)//2)
        exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
players = [deque() for _ in range(n)]
 
 
for i in range(n):
    ais = list(map(int,input().split()))
    for ai in ais:
        players[i].append((i,ai-1))
 
 
ans = 0
count = 0
day = {}
while True:
    count = 0
    passcount=0
    sumi = [0 for _ in range(n)]
    for i in range(n):
        if not players[i]:
            passcount+=1
            continue
        game = players[i][0]
        game_r =(players[i][0][1],players[i][0][0])
        if (game not in day) and(game_r not in day) and (sumi[i]==0):
            day[game] =1
        elif game_r in day and sumi[game[0]]==0 and sumi[game[1]]==0: 
            sumi[game_r[0]] = 1
            sumi[game[0]] = 1
            players[players[i][0][1]].popleft()
            players[players[i][0][0]].popleft()
            count +=1
    if passcount==n:
        print(ans)
        exit()
    if count ==0:
        print(-1)
        exit()
    ans +=1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = tuple(map(int, input().split()))
todo = [0] * (n+1)
days = 0
finish = 0
while True:
    update = []
    for i in range(1, n+1):
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i and p not in update:
                update.append(i)
                update.append(p)
                todo[i] += 1
                todo[p] += 1
                if todo[i] == n-1:
                    finish += 1
                if todo[p] == n-1:
                    finish += 1
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif finish == n:
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = tuple(map(int, input().split()))
todo = [0] * (n+1)
days = 0
while True:
    update = []
    for i in range(1, n+1):
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i and p not in update:
                update.append(i)
                update.append(p)
                todo[i] += 1
                todo[p] += 1
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
    a=list(map(int,input().split()))
    B=[]
    for x in a:
        b=[i+1,x]
        b.sort()
        b=tuple(b)
        B.append(b)
    A.append(B)

cnt=0
while 1:
    if len(A)==0:
        break
    #print(A)
    tail=[ arr[-1] for arr in A]
    tailset=set([ arr[-1] for arr in A])
    if len(tail)==len(tailset):
        cnt=-1
        break
    else:
        for i in tailset:
            if tail.count(i)==2:
                for j in range(N):
                    if A[j][-1]==i:
                        A[j].pop()
                for k in range(N):
                    for j in range(N):
                        if len(A[j])==0:
                            A.pop(j)
                            N-=1
                            break
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

total = [0]*n

i = 0
count = 0
day = 0
while count < (n*(n-1))//2:
    while total[i] < n-1:
        game = [0] * n
        flag = False
        for j in range(i,n):
            if total[j] == n-1 or game[j] == 1:
                continue
            tmp = a[j][total[j]]
            if game[tmp-1] == 0 and a[tmp-1][total[tmp-1]] == j+1:
                total[j] += 1
                total[tmp-1] += 1
                game[j] += 1
                game[tmp-1] += 1
                count += 1
                flag = True
        if flag == False:
            break
        day += 1
    if flag == False:
        break
    i += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
players = [deque() for _ in range(n)]
 
 
for i in range(n):
    ais = list(map(int,input().split()))
    for ai in ais:
        players[i].append((i,ai-1))
 
 
ans = 0
count = 0
day = set([])
while True:
    count = 0
    passcount=0
    sumi = [0 for _ in range(n)]
    for i in range(n):
        if not players[i]:
            passcount+=1
            continue
        game = players[i][0]
        game_r =(players[i][0][1],players[i][0][0])
        if (game not in day) and(game_r not in day) and (sumi[i]==0):
            day |= {game}
        elif game_r in day and sumi[game[0]]==0 and sumi[game[1]]==0: 
            day -= {game_r,game}
            sumi[game_r[0]] = 1
            sumi[game[0]] = 1
            players[players[i][0][1]].popleft()
            players[players[i][0][0]].popleft()
            count +=1
    if passcount==n:
        print(ans)
        exit()
    if count ==0:
        print(-1)
        exit()
    ans +=1

Submission status: Time Limit Exceeded

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

total = [0]*n

i = 0
count = 0
day = 0
while count < (n*(n-1))//2:
    while total[i] < n-1:
        game = [0] * n
        flag = False
        for j in range(i,n):
            if total[j] == n-1:
                continue
            tmp = a[j][total[j]]
            if game[j] == 0 and game[tmp-1] == 0 and a[tmp-1][total[tmp-1]] == j+1:
                total[j] += 1
                total[tmp-1] += 1
                game[j] += 1
                game[tmp-1] += 1
                count += 1
                flag = True
        if flag == False:
            break
        day += 1
    if flag == False:
        break
    i += 1

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
allnodes = {(0,0)}

def order(edges):
    status = {}
    for n in allnodes:
        status[n] = None
    q = [(0, 0)]
    TMP = 1
    DONE = 2

    def visit(n):
        if status[n] == TMP:
            return False
        elif status[n] is None:
            status[n] = TMP
            for u in edges[n]:
                if visit(u) == False:
                    return False
            status[n] = DONE

        return True

    for n in allnodes:
        if visit(n) == False:
            return False
    return True

edges = {}
for a in range(1,N+1):
    l = [int(x) for x in input().split()]
    prev = (0, 0)
    for y in l:
        x = a 
        if x > y:
            x, y = y, x 
        allnodes.add((x, y))
        edges.setdefault(prev, set()).add((x, y))
        edges.setdefault((x, y), set())
        prev = x, y
#for k in edges: print(k, edges[k])
def longpath(allnodes, edges):
    q = [(0, 0)]
    D = {n:0 for n in allnodes}
    while q:
        u = q.pop()
        d = D[u]
        for v in edges[u]:
            if D[v] < d + 1:
                D[v] = d + 1
                q.append(v)
    return max(D[k] for k in D.keys())

if not order(edges):
    print(-1)
else:
    print(longpath(allnodes, edges))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
players = [[] for _ in range(n)]
 
 
for i in range(n):
    ais = list(map(int,input().split()))
    for ai in ais:
        players[i].append((i,ai-1))
 
 
ans = 0
count = 0
day = set([])
while True:
    count = 0
    passcount=0
    sumi = [0 for _ in range(n)]
    for i in range(n):
        if not players[i]:
            passcount+=1
            continue
        game = players[i][0]
        game_r =(players[i][0][1],players[i][0][0])
        if (game not in day) and(game_r not in day) and (sumi[i]==0):
            day |= {game}
        elif game_r in day and sumi[game[0]]==0 and sumi[game[1]]==0: 
            day -= {game_r,game}
            sumi[game_r[0]] = 1
            sumi[game[0]] = 1
            players[players[i][0][1]].pop(0)
            players[players[i][0][0]].pop(0)
            count +=1
    if passcount==n:
        print(ans)
        exit()
    if count ==0:
        print(-1)
        exit()
    ans +=1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
players = [[] for _ in range(n)]
 
 
for i in range(n):
    ais = list(map(int,input().split()))
    for ai in ais:
        players[i].append((i,ai-1))
 
 
ans = 0
count = 0
while True:
    day = set([])
    count = 0
    passcount=0
    sumi = [0 for _ in range(n)]
    for i in range(n):
        if not players[i]:
            passcount+=1
            continue
        game = players[i][0]
        game_r =(players[i][0][1],players[i][0][0])
        if (game not in day) and(game_r not in day) and (sumi[i]==0):
            day |= {game}
        elif game_r in day: 
            day -= {game_r,game}
            sumi[game_r[0]] = 1
            sumi[game[0]] = 1
            players[players[i][0][1]].pop(0)
            players[players[i][0][0]].pop(0)
            count +=1
    if passcount==n:
        print(ans)
        exit()
    if count ==0:
        print(-1)
        exit()
    
    ans +=1

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 200000:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 250000:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 500000:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
allnodes = {(0,0)}

def order(edges):
    status = {}
    for n in allnodes:
        status[n] = None
    q = [(0, 0)]
    L = []
    TMP = 1
    DONE = 2

    def visit(n):
        if status[n] == TMP:
            return -1
        elif status[n] is None:
            status[n] = TMP
            for u in edges[n]:
                if visit(u) == -1:
                    return -1
            status[n] = DONE
            L.append(n)
        return 0

    for n in allnodes:
        if visit(n) == -1:
            return None
    return L

edges = {}
for a in range(1,N+1):
    l = [int(x) for x in input().split()]
    prev = (0, 0)
    for y in l:
        x = a 
        if x > y:
            x, y = y, x 
        allnodes.add((x, y))
        edges.setdefault(prev, set()).add((x, y))
        edges.setdefault((x, y), set())
        prev = x, y
#for k in edges: print(k, edges[k])
def longpath(allnodes, edges):
    q = [(0, 0)]
    D = {n:0 for n in allnodes}
    while q:
        u = q.pop()
        d = D[u]
        for v in edges[u]:
            if D[v] < d + 1:
                D[v] = d + 1
                q.append(v)
    return max(D[k] for k in D.keys())

L = order(edges)
if L is None:
    print(-1)
else:
    print(longpath(allnodes, edges))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
allnodes = {(0,0)}

def order(edges):
    status = {}
    for n in allnodes:
        status[n] = None
    q = [(0, 0)]
    L = []
    TMP = 1
    DONE = 2

    def visit(n):
        if status[n] == TMP:
            return -1
        elif status[n] is None:
            status[n] = TMP
            for u in edges[n]:
                if visit(u) == -1:
                    return -1
            status[n] = DONE
            L.append(n)
        return 0

    for n in allnodes:
        if visit(n) == -1:
            return None
    return L

edges = {}
for a in range(1,N+1):
    l = [int(x) for x in input().split()]
    prev = (0, 0)
    for y in l:
        x = a 
        if x > y:
            x, y = y, x 
        allnodes.add((x, y))
        edges.setdefault(prev, set()).add((x, y))
        edges.setdefault((x, y), set())
        prev = x, y
#for k in edges: print(k, edges[k])
from heapq import heappush, heappop

def longpath(allnodes, edges):
    q = [(0, (0, 0))]
    D = {n:0 for n in allnodes}
    while q:
        d, u = heappop(q)
        for v in edges[u]:
            if D[v] > d - 1:
                D[v] = d - 1
                heappush(q, (d-1,v))

    return -min(D[k] for k in D.keys())

L = order(edges)
if L is None:
    print(-1)
else:
    print(longpath(allnodes, edges))

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
    chance = [i for i in range(N)]
    flag  = [True] * N #試合をしたかどうかチェック
    while len(chance) != 0: # and tmp < 2 * N + 2:
        ans += 1
        flag  = [True] * N #試合をしたかどうかチェック
        tmp_lst = []
        # print ('chance', chance)
        for i in chance:
            if check[i] >= N - 1 or flag[i] == False:
                # 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
                tmp_lst.append(i)
                tmp_lst.append(b)
                if count == (N * (N - 1))//2:
                    print (ans)
                    exit()
        chance = tmp_lst
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

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
    chance = [i for i in range(N)]
    flag  = [True] * N #試合をしたかどうかチェック
    while tmp < 2 * N + 2 and len(chance) != 0:
        ans += 1
        flag  = [True] * N #試合をしたかどうかチェック
        tmp_lst = []
        # print ('chance', chance)
        for i in chance:
            if check[i] >= N - 1 or flag[i] == False:
                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
                tmp_lst.append(i)
                tmp_lst.append(b)
                if count == (N * (N - 1))//2:
                    print (ans)
                    exit()
        chance = tmp_lst
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

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 = 1
    i = 0
    tmp = 0
    count = 0
    flag  = [True] * N #試合をしたかどうかチェック
    while tmp < 2 * N + 2:
        if i == N:
            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
from collections import deque
input = sys.stdin.readline
N = int(input())
fin = [False] * N
An = [''] * N
q = deque([])
deg = [0] * N
for n in range(N):
    An[n] = [int(x) for x in input().split()]

matched = [False] * N
for n in range(N):
    a = An[n][deg[n]] - 1
    if matched[a]:
        continue
    b = An[a][deg[a]] - 1
    if matched[b]:
        continue
    elif b == n:
        set_ = tuple(sorted([a,b]))
        if set_ not in q:
            q.append(set_)
        matched[a] = True
        matched[b] = True

days = 0
while len(q):
    days += 1
    matched = [False] * N
    flag = False
    q_ = list(q)
    q.clear()
    for a, b in q_:
        if deg[a] < N - 2:
            deg[a] += 1
            c = An[a][deg[a]] - 1
            if matched[c] == False and An[c][deg[c]]-1 == a:
                set_ = tuple(sorted([a, c]))
                q.append(set_)
                matched[c] = True
        else:
            fin[a] = True
        if deg[b] < N - 2:
            deg[b] += 1
            d = An[b][deg[b]] - 1
            if matched[d] == False and An[d][deg[d]]-1 == b:
                set_ = tuple(sorted([b, d]))
                q.append(set_)
                matched[d] = True
        else:
            fin[b] = True

if False in fin:
    days = -1
print(days)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

ans = 0
finish = False
q = []
base_used = [True] + [False] * N
count = 0

while not finish and count != N:
  finish = True
  ans += 1
  used = copy.deepcopy(base_used)
  
  for idx, u in enumerate(used):
    if not u:
      a = A[idx-1][0]
      if not used[a] and A[a-1][0] == idx:
        used[idx] = True
        used[a] = True
        q.extend([idx, a])
        finish = False
    else:
      continue
  
  while q:
    a = q.pop(0)-1
    A[a].pop(0)
    if not A[a]:
      base_used[a+1] = True
      count += 1

if N != count:
  ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

matched = [False] * N
for n in range(N):
    a = An[n][deg[n]] - 1
    if matched[a]:
        continue
    b = An[a][deg[a]] - 1
    if matched[b]:
        continue
    elif b == n:
        set_ = tuple(sorted([a,b]))
        if set_ not in q:
            q.append(set_)
        matched[a] = True
        matched[b] = True

days = 0
while len(q):
    days += 1
    matched = [False] * N
    flag = False
    q_ = list(q)[:]
    q.clear()
    for a, b in q_:
        if deg[a] < N - 2:
            deg[a] += 1
            c = An[a][deg[a]] - 1
            if matched[c] == False and An[c][deg[c]]-1 == a:
                set_ = tuple(sorted([a, c]))
                q.append(set_)
                matched[c] = True
        else:
            fin[a] = True
        if deg[b] < N - 2:
            deg[b] += 1
            d = An[b][deg[b]] - 1
            if matched[d] == False and An[d][deg[d]]-1 == b:
                set_ = tuple(sorted([b, d]))
                q.append(set_)
                matched[d] = True
        else:
            fin[b] = True

if False in fin:
    days = -1
print(days)

Submission status: Time Limit Exceeded

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

matched = [False] * N
for n in range(N):
    a = An[n][deg[n]] - 1
    if matched[a]:
        continue
    b = An[a][deg[a]] - 1
    if matched[b]:
        continue
    elif b == n:
        set_ = tuple(sorted([a,b]))
        if set_ not in q:
            q.append(set_)
        matched[a] = True
        matched[b] = True

days = 0
while len(q):
    days += 1
    matched = [False] * N
    flag = False
    q_ = list(q)[:]
    q = deque([])
    for a, b in q_:
        if deg[a] < N - 2:
            deg[a] += 1
            c = An[a][deg[a]] - 1
            if matched[c] == False and An[c][deg[c]]-1 == a:
                set_ = tuple(sorted([a, c]))
                q.append(set_)
                matched[c] = True
        else:
            fin[a] = True
        if deg[b] < N - 2:
            deg[b] += 1
            d = An[b][deg[b]] - 1
            if matched[d] == False and An[d][deg[d]]-1 == b:
                set_ = tuple(sorted([b, d]))
                q.append(set_)
                matched[d] = True
        else:
            fin[b] = True

if False in fin:
    days = -1
print(days)