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 sys
from collections import deque

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [deque(rl()[::-1]) for _ in range(N)]
answer = 0
match = 0
while True:
    used = set()
    bool = False
    for i in range(N):
        if len(A[i]) == 0:
            continue
        op = A[i][-1] - 1
        if op in used or i in used:
            continue
        if A[op][-1]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            bool = True
            A[i].pop()
            A[op].pop()
    
    answer += 1
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
G = {(i,j):[0,[]] for i in range(1,N) for j in range(i+1,N+1)}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    k1 = i
    k2 = A[0]
    if k1>k2:
        k1,k2 = k2,k1
    pre = (k1,k2)
    for j in range(1,N-1):
        k1 = i
        k2 = A[j]
        if k1>k2:
            k1,k2 = k2,k1
        G[pre][1].append((k1,k2))
        G[(k1,k2)][0] += 1
        pre = (k1,k2)
B = {}
que = deque([])
hist = {a:0 for a in G}
for a in G:
    if G[a][0]==0:
        que.append((a,0))
        hist[a] = 1
while que:
    a,c = que.popleft()
    if c not in B:
        B[c] = []
    B[c].append(a)
    for b in G[a][1]:
        if hist[b]==0:
            G[b][0] -= 1
            if G[b][0]==0:
                que.append((b,c+1))
                hist[b] = 1
n = 0
for c in B:
    n += len(B[c])
if n<(N*(N-1))//2:
    print(-1)
else:
    print(len(B))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
        if not nxt:
            return -1
        for i in set(nxt):
            if A[i]:
                w[i] = A[i].pop()
            else:
                w[i] = -1
                r -= 1
        cur = nxt
    return d


print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = []
    d = 0
    n = set(range(N))
    while True:
        p = 0
        l = set()
        d += 1
        for i in n:
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j] = A[j][:-1]
                A[i] = A[i][:-1]
                p += 1
        n = l
        if p == 0:
            print(-1)
            break
        if sum([len(i) for i in A]) == 0:
            print(d)
            break
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = []
    d = 0
    while True:
        p = 0
        l = set()
        d += 1
        for i in range(N):
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j] = A[j][:-1]
                A[i] = A[i][:-1]
                p += 1
        if p == 0:
            print(-1)
            break
        if sum([len(i) for i in A]) == 0:
            print(d)
            break
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
    d = 0
    p = [0] * N
    r = N
    cur = list(range(N))
    while r:
        matched = False
        d += 1
        m = [False] * N
        nxt = []
        for i in cur:
            if m[i]:
                continue
            if p[i] == N - 1:
                continue
            o = A[i][p[i]]
            if (not m[o]) and A[o][p[o]] == i:
                matched = True
                p[i] += 1
                p[o] += 1
                m[i] = True
                m[o] = True
                if p[i] == N - 1:
                    r -= 1
                else:
                    nxt.append(i)
                if p[o] == N - 1:
                    r -= 1
                else:
                    nxt.append(o)
        cur = nxt
        if not matched:
            return -1
    return d


print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
    d = 0
    p = [0] * N
    r = N
    while r:
        matched = False
        d += 1
        m = [False] * N
        for i in range(N):
            if m[i]:
                continue
            if p[i] == N - 1:
                continue
            o = A[i][p[i]]
            if (not m[o]) and A[o][p[o]] == i:
                matched = True
                p[i] += 1
                p[o] += 1
                m[i] = True
                m[o] = True
                if p[i] == N - 1:
                    r -= 1
                if p[o] == N - 1:
                    r -= 1
        if not matched:
            return -1
    return d


print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        #from_to[make_hash(i, node_to)].add(make_hash(i, node_from))
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(h)
        if pointing_i == 0:
            DST.add(h)
if len(START) == 0 or len(DST) == 0:
    print(-1)

else:
    Q = [v for v in START]
    visited = set()
    dist = 0
    while Q:
        tmp = []
        dist += 1
        for q in Q:
            for nex in from_to[q]:
                tmp.append(nex)
                visited.add(nex)
        Q = tmp
    print(dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        #from_to[make_hash(i, node_to)].add(make_hash(i, node_from))
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(h)
        if pointing_i == 0:
            DST.add(h)
if len(START) == 0 or len(DST) == 0:
    print(-1)

else:
    Q = [[v, 1] for v in START]
    visited = set()
    dist = 1
    while Q:
        tmp = []
        for n in Q:
            q = n[0]
            d = n[1]
            for nex in from_to[q]:
                tmp.append([nex, d+1])
                dist = d+1
                visited.add(nex)
        Q = tmp
    print(dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
# print("pointed", list([un_hash(key), val] for key, val in pointed.items()))
# print("pointing", list([un_hash(key), val] for key, val in pointing.items()))
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(h)
        if pointing_i == 0:
            DST.add(h)
if len(START) == 0 or len(DST) == 0:
    print(-1)

else:
    Q = [[v, 1] for v in START]
    dist = 1
    while Q:
        q, d = Q.pop()
        for nex in from_to[q]:
            Q.append([nex, d+1])
            dist = d+1
    print(dist)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = {(i,j):[0,[]] for i in range(1,N) for j in range(i+1,N+1)}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    for j in range(1,N-1):
        i1 = i
        a = A[j-1]
        if a<i1:
            i1,a = a,i1
        i2 = i
        b = A[j]
        if i2>b:
            i2,b = b,i2
        G[(i1,a)][1].append((i2,b))
        G[(i2,b)][0] += 1
hist = {a:0 for a in G}
d = []
for x in G:
    if G[x][0]==0:
        d.append(x)
        hist[x] = 1
D = []
if len(d)>0:
    D.append(d)
while d:
    d = []
    for a in D[-1]:
        for b in G[a][1]:
            G[b][0] -= 1
            if G[b][0]==0 and hist[b]==0:
                d.append(b)
                hist[b] = 1
    if len(d)>0:
        D.append(d)
k = 0
for a in hist:
    k += hist[a]
if k<(N*(N-1))//2:
    print(-1)
else:
    print(len(D))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = {(i,j):[0,[]] for i in range(1,N) for j in range(i+1,N+1)}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    for j in range(1,N-1):
        i1 = i
        a = A[j-1]
        if a<i1:
            i1,a = a,i1
        i2 = i
        b = A[j]
        if i2>b:
            i2,b = b,i2
        G[(i1,a)][1].append((i2,b))
        G[(i2,b)][0] += 1
hist = {a:0 for a in G}
d = []
for x in G:
    if G[x][0]==0:
        d.append(x)
        hist[x] = 1
D = []
if len(d)>0:
    D.append(d)
while d:
    d1 = D[-1]
    d = []
    for a in d1:
        for b in G[a][1]:
            G[b][0] -= 1
            if G[b][0]==0 and hist[b]==0:
                d.append(b)
                hist[b] = 1
    if len(d)>0:
        D.append(d)
k = 0
for a in hist:
    k += hist[a]
if k<(N*(N-1))//2:
    print(-1)
else:
    print(len(D))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = {(i,j):[0,[]] for i in range(1,N) for j in range(i+1,N+1)}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    for j in range(1,N-1):
        i1 = i
        a = A[j-1]
        if a<i1:
            i1,a = a,i1
        i2 = i
        b = A[j]
        if i2>b:
            i2,b = b,i2
        G[(i1,a)][1].append((i2,b))
        G[(i2,b)][0] += 1
d = []
for x in G:
    if G[x][0]==0:
        d.append(x)
D = []
if len(d)>0:
    D.append(d)
while d:
    d1 = D[-1]
    d = []
    for a in d1:
        for b in G[a][1]:
            G[b][0] -= 1
            if G[b][0]==0 and b not in d:
                d.append(b)
        del G[a]
    if len(d)>0:
        D.append(d)
if len(G)>0 and len(d)==0:
    print(-1)
else:
    print(len(D))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = {(i,j):[[],[]] for i in range(1,N) for j in range(i+1,N+1)}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    for j in range(1,N-1):
        i1 = i
        a = A[j-1]
        if a<i1:
            i1,a = a,i1
        i2 = i
        b = A[j]
        if i2>b:
            i2,b = b,i2
        G[(i1,a)][1].append((i2,b))
        G[(i2,b)][0].append((i1,a))
G1 = sorted([[a,len(G[a][0])] for a in G],key=lambda x:x[1])
D = []
d = []
for i in range(len(G1)):
    if G1[i][1]==0:
        d.append(G1[i][0])
    else:break
if len(d)>0:
    D.append(d)
while d:
    d1 = D[-1]
    d = []
    for a in d1:
        for b in G[a][1]:
            G[b][0].remove(a)
            if len(G[b][0])==0 and b not in d:
                d.append(b)
        del G[a]
    if len(d)>0:
        D.append(d)
if len(G)>0 and len(d)==0:
    print(-1)
else:
    print(len(D))

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    A = [deque(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
    ans = 0
    while any(A):
        ok = False
        used = [False] * N
        for i in range(N):
            a = A[i]
            if not a or used[i]:
                continue
            j = a[0]
            b = A[j]
            if not b or used[j]:
                continue
            if i == b[0]:
                ok = True
                A[i].popleft()
                A[j].popleft()
                used[i] = used[j] = True
        if not ok:
            print(-1)
            exit()
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N = int(input())
A = [deque(list(map(lambda x: int(x)-1, input().split()))) for _ in range(N)]
ans = 0
while any(A):
    ok = False
    used = [False] * N
    for i in range(N):
        a = A[i]
        if not a or used[i]:
            continue
        j = a[0]
        b = A[j]
        if not b or used[j]:
            continue
        if i == b[0]:
            ok = True
            A[i].popleft()
            A[j].popleft()
            used[i] = True
            used[j] = True
    if not ok:
        print(-1)
        exit()
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
ans = 0
while any(A):
    ok = False
    used = []
    for i in range(N):
        a = A[i]
        if not a or i in used:
            continue
        j = a[0]
        b = A[j]
        if not b or j in used:
            continue
        if i == b[0]:
            ok = True
            A[i].pop(0)
            A[j].pop(0)
            used.append(i)
            used.append(j)
    if not ok:
        print(-1)
        exit()
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

CONT = True
IDXS=[0]*N
days = 0
ST=set()

next_check = range(N)
while CONT:
    cont = False
    _next_check = []
    for i in next_check:
        if IDXS[i] < N-1:
            pair = MATCHES[i][IDXS[i]]
            p, q = pair
            if pair in ST:
                ST.remove(pair)
                # print("{}: {}".format(days, pair))
                if IDXS[i] < N-1:
                    IDXS[p-1] += 1
                    IDXS[q-1] += 1
                    cont = True
                    _next_check.append(p-1)
                    _next_check.append(q-1)
            else:
                ST.add(pair)
    next_check = _next_check
    CONT = cont
    days += cont

# print(IDXS)
if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

CONT = True
IDXS=[0]*N
DONE=[False]*(N+1)
days = 0
ST=set()
while CONT:
    cont = False
    ST.clear()
    for i in range(N):
        if IDXS[i] < N-1:
            pair = MATCHES[i][IDXS[i]]
            p, q = pair
            if pair in ST:
                ST.remove(pair)
                # print("{}: {}".format(days, pair))
                if IDXS[i] < N-1:
                    IDXS[p-1] += 1
                    IDXS[q-1] += 1
                    cont = True
            else:
                ST.add(pair)
    CONT = cont
    days += cont


# print(IDXS)
if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

CONT = True
IDXS=[0]*N
DONE=[False]*(N+1)
days = 0
ST=set()
while CONT:
    cont = False
    ST.clear()
    for i in range(N):
        if IDXS[i] < N-1:
            pair = MATCHES[i][IDXS[i]]
            p, q = pair
            if pair in ST:
                ST.remove(pair)
                # print("{}: {}".format(days, pair))
                if IDXS[i] < N-1:
                    IDXS[p-1] += 1
                    IDXS[q-1] += 1
                    cont = True
            else:
                # print("add:{}".format(pair))
                ST.add(pair)
    # print(ST)
    CONT = cont
    days += cont


# print(IDXS)
if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

CONT = True
IDXS=[0]*N
DONE=[False]*N
days = 0
ST=set()
while CONT:
    cont = False
    ST.clear()
    for i in range(N): DONE[i] = False
    for i in range(N):
        if IDXS[i] < N-1:
            if MATCHES[i][IDXS[i]] in ST:
                if not DONE[MATCHES[i][IDXS[i]][0]-1] and not DONE[MATCHES[i][IDXS[i]][1]-1]:
                    ST.remove(MATCHES[i][IDXS[i]])
                    DONE[MATCHES[i][IDXS[i]][0]-1] = True
                    DONE[MATCHES[i][IDXS[i]][1]-1] = True
                    # print("{}: {}".format(days, MATCHES[i][IDXS[i]]))
                    if IDXS[i] < N-1:
                        IDXS[MATCHES[i][IDXS[i]][0]-1] += 1
                        IDXS[MATCHES[i][IDXS[i]][1]-1] += 1
                        cont = True
            else:
                # print("add:{}".format(MATCHES[i][IDXS[i]]))
                ST.add(MATCHES[i][IDXS[i]])
    # print(ST)
    CONT = cont
    days += cont


# print(IDXS)
if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    MAXGAME = (N*(N-1))//2
    while True:
        if totalGame == MAXGAME:
            break
        
        # 既にこのターンでマッチしたインデックスを保持
        match = set()

        for i in range(N):
            if not A[i]:
                continue
            match_index = A[i][-1]-1

            if not A[match_index]:
                continue

            if match_index in match or i in match:
                continue

            if A[match_index][-1]-1 == i:
                A[i].pop()
                A[match_index].pop()
                match.add(i)
                match.add(match_index)
                totalGame += 1

        if len(match) == 0:
            print(-1)
            return

        answer += 1

    print(answer)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    while True:
        if totalGame == (N*(N-1))//2:
            break

        match = set()
        # 既にこのターンでマッチしたインデックスを保持

        for i in range(N):
            if not A[i]:
                continue
            match_index = A[i][-1]-1

            if not A[match_index]:
                continue

            if match_index in match or i in match:
                continue

            if A[match_index][-1]-1 == i:
                A[i].pop()
                A[match_index].pop()
                match.add(i)
                match.add(match_index)
                totalGame += 1

        if len(match) == 0:
            print(-1)
            return

        answer += 1

    print(answer)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    while True:
        if totalGame == (N*(N-1))//2:
            break

        match = set()
        # 既にこのターンでマッチしたインデックスを保持

        for i in range(N):

            if not A[i]:
                continue
            match_index = A[i][-1]-1
            if not A[match_index]:
                continue

            if match_index in match or i in match:
                continue

            if A[match_index][-1]-1 == i:
                A[i].pop()
                A[match_index].pop()
                match.add(i)
                match.add(match_index)
                totalGame += 1

        if len(match) == 0:
            print(-1)
            return

        answer += 1

    print(answer)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    while True:
        if totalGame == N*(N-1)//2:
            break

        match = set()
        # 既にこのターンでマッチしたインデックスを保持

        for i in range(N):
            if not A[i]:
                continue
            match_index = A[i][-1]-1

            if match_index in match or i in match:
                continue

            if A[match_index][-1]-1 == i:
                A[i].pop()
                A[match_index].pop()
                match.add(i)
                match.add(match_index)
                totalGame += 1
            else:
                continue

        if len(match) == 0:
            print(-1)
            return
        answer += 1

    print(answer)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    
    A = [None] * N
    for i in range(N):
        A[i] = list(map(int, input().split()))
        
    
    day = 0
    roop_flag = True
    
    b = [A[i][0] for i in range(N)]

    while roop_flag:
        
        day += 1
        # 基本はNGの状態にしておく
        roop_flag = False
        done = [False] * N
        
        
        for i in range(N):
            if b[i] is None:
                continue
            
            if not done[i] and not done[b[i] - 1]:
                if b[b[i] - 1] == i + 1:
                    roop_flag = True
                    
                    done[i] = True
                    done[b[i] - 1] = True
                    
                    A[i] = A[i][1:]
                    A[b[i] -1] = A[b[i] - 1][1:]

                    if len(A[b[i] - 1]) > 0:
                        b[b[i] - 1] = A[b[i] - 1][0]
                    else:
                        b[b[i] - 1] = None
                    
                    if len(A[i]) > 0:
                        b[i] = A[i][0]
                    else:
                        b[i] = None
                    

        if b == [None] * N:
            print(day)
            quit()
            
        
    print(-1)
    

    
if __name__ == "__main__":
    main()