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,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}


for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
conduct=set([])
subconduct=set([])
q=set([])
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.add(key)
sub=set([])
while q:
    while q:
        x=q.pop()
        for n in _to[x]:
            if conduct>=_from[n]:
                subconduct.add(n)
                sub.add(n)
        if not q:
            q=sub
            sub=set([])
            conduct=conduct|subconduct
            subconduct=set([])
            day+=1
            break

if conduct==set(node):
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}


for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
conduct=set([])
q=[]
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.append(key)
sub=[]
heapq.heapify(q)
heapq.heapify(sub)
while q:
    while q:
        x=heapq.heappop(q)
        for n in _to[x]:
            if conduct>=_from[n]:
                conduct.add(n)
                heapq.heappush(sub,n)
        if not q:
            q=sub
            sub=[]
            heapq.heapify(sub)
            day+=1
            break

if conduct==set(node):
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[]] + A

cnt = 0
ok = True
q = list(range(1, N+1))

for _ in range(N * (N - 1) // 2):
    can_match_today = [False] * (N+1)
    fin = True
    match = False
    nq = []
    for i in q:
        if can_match_today[i] or not A[i]:
            continue

        fin = False
        l = A[i][-1]

        if can_match_today[l]:
            continue
        r = A[l][-1]

        if r == i:
            match = True
            can_match_today[l] = True
            can_match_today[i] = True
            A[l].pop()
            A[i].pop()
            nq.append(l)
            nq.append(i)

    if fin:
        break

    if not match:
        ok = False
        break

    cnt += 1
    q = nq


if ok:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[]] + A

cnt = 0
ok = True
q = list(range(1, N+1))

for _ in range(N * (N - 1) // 2):
    can_match_today = [False] * (N+1)
    fin = True
    match = False
    for i in q:
        if can_match_today[i] or not A[i]:
            continue

        fin = False
        l = A[i][-1]

        if can_match_today[l]:
            continue
        r = A[l][-1]

        if r == i:
            match = True
            can_match_today[l] = True
            can_match_today[i] = True
            A[l].pop()
            A[i].pop()
            q.append(l)
            q.append(i)

    if fin:
        break

    if not match:
        ok = False
        break

    cnt += 1


if ok:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[]] + A

cnt = 0
ok = True

for _ in range(N * (N - 1) // 2):
    d = [False] * (N+1)
    fin = True
    match = False
    for i in range(1, N + 1):
        if d[i] or not A[i]:
            continue

        fin = False
        l = A[i][-1]

        if d[l]:
            continue
        r = A[l][-1]

        if r == i:
            match = True
            d[l] = True
            d[i] = True
            A[l].pop()
            A[i].pop()

    if fin:
        break

    if not match:
        ok = False
        break

    cnt += 1


if ok:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[]] + A

cnt = 0
ok = True

for _ in range(N * (N - 1) // 2):
    match = []
    fin = True
    for i in range(1, N + 1):
        if not A[i]:
            continue

        fin = False
        l = A[i][-1]
        r = A[l][-1]

        if r == i:
            match.append(l)

    if fin:
        break

    if not match:
        ok = False
        break

    for i in match:
        A[i].pop()

    cnt += 1


if ok:
    print(cnt)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(p, EdgeTo, Length, Visited):
    if p in Visited: return -1
    if p in Length: return Length[p]
    else:
        maxL = 0
        nV = Visited | {p}
        if p not in EdgeTo:
            Length[p] = 1
            return 1
        else:
            for e in EdgeTo[p]:
                back = dfs(e, EdgeTo, Length, nV)
                if back == -1:
                    Length[p] = -1
                    return -1
                else: maxL = max(maxL, back)
            Length[p] = maxL + 1
            return maxL + 1
        
def solve():
    input = sys.stdin.readline
    N = int(input())
    edgeTo = dict()
    edgeFrom = dict()
    Length = dict()
    A = [[int(a) for a in input().split()] for _ in range(N)]
    for i in range(1, N + 1):
        p = (min(i, A[i-1][0]), max(i, A[i-1][0]))
        for j in range(1, N - 1):
            nextp = (min(i, A[i-1][j]), max(i, A[i-1][j]))
            if p in edgeTo: edgeTo[p].append(nextp)
            else: edgeTo[p] = [nextp]
            if nextp in edgeFrom: edgeFrom[nextp].append(p)
            else: edgeFrom[nextp] = [p]
            p = nextp

    Ans = -1
    for i in range(1, N + 1):
        if (min(i, A[i-1][0]), max(i, A[i-1][0])) not in edgeFrom:
            b = dfs((min(i, A[i-1][0]), max(i, A[i-1][0])), edgeTo, Length, set())
            if b == -1:
                print(-1)
                break
            else: Ans = max(Ans, b)
    else: print(Ans)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(p, EdgeTo, Length, Visited):
    if p in Visited: return -1
    if p in Length: return Length[p]
    else:
        maxL = 0
        nV = Visited | {p}
        if p not in EdgeTo:
            Length[p] = 1
            return 1
        else:
            for e in EdgeTo[p]:
                back = dfs(e, EdgeTo, Length, nV)
                if back == -1:
                    Length[p] = -1
                    return -1
                    break
                else: maxL = max(maxL, back)
            else:
                Length[p] = maxL + 1
                return maxL + 1
        
def solve():
    input = sys.stdin.readline
    N = int(input())
    edgeTo = dict()
    edgeFrom = dict()
    Length = dict()
    for i in range(1, N + 1):
        A = [int(a) for a in input().split()]
        p = (min(i, A[0]), max(i, A[0]))
        for j in range(1, N - 1):
            nextp = (min(i, A[j]), max(i, A[j]))
            if p in edgeTo: edgeTo[p].append(nextp)
            else: edgeTo[p] = [nextp]
            if nextp in edgeFrom: edgeFrom[nextp].append(p)
            else: edgeFrom[nextp] = [p]
            p = nextp

    start = []
    for i in range(1, N):
        for j in range(i+1, N+1):
            if (i, j) not in edgeFrom: start.append((i, j))
    Ans = 0
    if len(start) == 0: print(-1)
    else:
        for s in start:
            b = dfs(s, edgeTo, Length, set())
            if b == -1:
                print(-1)
                break
            else: Ans = max(Ans, b)
        else: print(Ans)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(p, EdgeTo, Length, Visited):
    if p in Visited: return -1
    if Length[p] != 0: return Length[p]
    else:
        maxL = 0
        nV = Visited | {p}
        if p not in EdgeTo:
            Length[p] = 1
            return 1
        else:
            for e in EdgeTo[p]:
                back = dfs(e, EdgeTo, Length, nV)
                if back == -1:
                    Length[p] = -1
                    return -1
                    break
                else: maxL = max(maxL, back)
            else:
                Length[p] = maxL + 1
                return maxL + 1
        
def solve():
    input = sys.stdin.readline
    N = int(input())
    edgeTo = dict()
    edgeFrom = dict()
    Length = dict()
    for i in range(1, N + 1):
        A = [int(a) for a in input().split()]
        p = (min(i, A[0]), max(i, A[0]))
        for j in range(1, N - 1):
            nextp = (min(i, A[j]), max(i, A[j]))
            if p in edgeTo: edgeTo[p].append(nextp)
            else: edgeTo[p] = [nextp]
            if nextp in edgeFrom: edgeFrom[nextp].append(p)
            else: edgeFrom[nextp] = [p]
            p = nextp

    start = []
    for i in range(1, N):
        for j in range(i+1, N+1):
            Length[(i, j)] = 0
            if (i, j) not in edgeFrom: start.append((i, j))
    Ans = 0
    if len(start) == 0: print(-1)
    else:
        for s in start:
            b = dfs(s, edgeTo, Length, set())
            if b == -1:
                print(-1)
                break
            else: Ans = max(Ans, b)
        else: print(Ans)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
day=0
match=n*(n-1)
card=1
next=[0]*n
for i in range(n):
    a[i].append(-1)

while card>0 and match>0:
  day+=1
  player=[]
  for i in range(n):
    t=a[i][next[i]]-1
    if i==a[t][next[t]]-1:
      player.append(i)
  for i in player:
    next[i]+=1
  card=len(player)
  match-=card
if match>0:
  day=-1
print(day)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
day=-1
match=n*(n-1)//2
card=1
for i in range(n):
    a[i].append(-1)
while card>0:
  day+=1
  card=0
  player=[]
  for i in range(1,n+1):
    if i==a[a[i-1][0]-1][0]:
      card+=1
      player.append(i)
  for i in player:
    del a[i-1][0]
  match-=card//2
if match>0:
  day=-1
print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from copy import deepcopy 

MAXN = 1005
MAXV = MAXN * (MAXN - 1)//2
G = [[] for _ in range(MAXV)]

id = [[-1] * MAXN for _ in range(MAXN)]
def toId(i,j):
    if i > j:
        i,j = j,i
    return id[i][j]


finished = [0] * MAXV
dp = [-1] * MAXV
def dfs(v):
    if dp[v] != -1:
        if finished[v] == 0:
            return -1
        return dp[v]
    dp[v] = 0
    for e in G[v]:
        res = dfs(e)
        if res == -1:
            return -1
        dp[v] = max(dp[v],res + 1)
    finished[v] = 1
    return dp[v]


def main():
    n = int(input())
    a = [[int(i) - 1 for i in input().split()] for _ in range(n)]

    v = 0
    for i in range(n):
        for j in range(i + 1,n):
            id[i][j] = v
            v += 1
    
    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):
            G[a[i][j]].append(a[i][j + 1])
    
    ans = 0
    for i in range(v):
        res = dfs(i)
        if res == -1:
            ans = -1
            break
        ans = max(ans,dfs(i) + 1)
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from copy import deepcopy 

def main():
    n = int(input())
    a = []
    for _ in range(n):
        b = [int(i) - 1 for i in input().split()]
        a.append(b[::-1])
    
    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if a[j][-1] == i:
            if i > j:
                i,j = j,i
            q.add((i,j))
    
    for i in range(n):
        check(i)
        
    day = 0
    while len(q):
        day += 1
        prevQ = deepcopy(q)
        q.clear()
        for i,j in prevQ:
            a[i].pop()
            a[j].pop()
        for i,j in prevQ:
            check(i)
            check(j)
    
    ans = day
    for i in range(n):
        if len(a[i]) != 0:
            ans = -1
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = set()
match = 0
for i in range(N):
    c = A[i].popleft()
    candidate.add(c)

while candidate:
    day += 1
    used = set()
    next = set()
    rmv = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if (b, a) in candidate:
            rmv.add((a, b))
            rmv.add((b, a))
            match += 1
            if A[a-1]:
                x = A[a-1].popleft()
                next.add(x)
            if A[b-1]:
                y = A[b-1].popleft()
                next.add(y)
            used.add(a)
            used.add(b)
    candidate -= rmv
    if match == N * (N-1) // 2:
        break
    candidate |= next
    if not used:
        print(-1); exit()

print(day)
# 10

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = set()
match = 0
for i in range(N):
    c = A[i].popleft()
    candidate.add(c)

while candidate:
    day += 1
    used = set()
    next = set()
    rmv = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if (b, a) in candidate:
            rmv.add((a, b))
            rmv.add((b, a))
            match += 1
            if A[a-1]:
                x = A[a-1].popleft()
                next.add(x)
            if A[b-1]:
                y = A[b-1].popleft()
                next.add(y)
            used.add(a)
            used.add(b)
    for r in rmv:
        candidate.remove(r)
    if match == N * (N-1) // 2:
        break
    candidate |= next
    if not used:
        print(-1); exit()

print(day)
# 10

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        f = 1
        res = 0
        for y in v[x]:
            if d[y]:
                d[y] = 0
                f &= dfs(y)
                d[y] = 1
            else:
                return 0
            if not f:
                return 0
            if res < r[y]:
                res = r[y]
        r[x] = res+1
        return f

    n = I()
    a = LIR(n)
    N = n*(n-1)
    f = [0]*N
    v = [[] for i in range(N)]
    lis = set()
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
        k = a[i][0]
        x = n*min(i,k)+max(i,k)
        for j in range(1,n-1):
            l = a[i][j]
            y = n*min(i,l)+max(i,l)
            v[y].append(x)
            f[x] += 1
            lis.add(x)
            lis.add(y)
            x = y
    if min([f[i] for i in lis]):
        print(-1)
        return
    d = [1]*N
    r = [0]*N
    for i in lis:
        if not f[i]:
            d[i] = 0
            if not dfs(i):
                print(-1)
                return
    print(max([r[i] for i in lis]))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        f = 1
        for y in v[x]:
            if d[y]:
                d[y] = 0
                f &= dfs(y)
                d[y] = 1
            else:
                return 0
            if not f:
                return f
        return f

    def dfs2(x):
        res = 0
        for y in v[x]:
            if d[y]:
                d[y] = 0
                dfs2(y)
            if res < r[y]:
                res = r[y]
        r[x] = res+1
    n = I()
    a = LIR(n)
    N = n*(n-1)
    f = [0]*N
    v = [[] for i in range(N)]
    lis = set()
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
        for j in range(n-2):
            k,l = a[i][j],a[i][j+1]
            x = n*min(i,k)+max(i,k)
            y = n*min(i,l)+max(i,l)
            v[y].append(x)
            f[x] += 1
            lis.add(x)
            lis.add(y)
    if min([f[i] for i in lis]):
        print(-1)
        return
    d = [1]*N
    for i in lis:
        if not f[i]:
            d[i] = 0
            if not dfs(i):
                print(-1)
                return
    r = [0]*N
    d = [1]*N
    for i in lis:
        if not f[i]:
            d[i] = 0
            dfs2(i)
    print(max([r[i] for i in lis]))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        res = 0
        for y in v[x]:
            if d[y]:
                d[y] = 0
                dfs(y)
                if res < r[y]:
                    res = r[y]
                d[y] = 1
            else:
                r[x] = float("inf")
                f[x] = float("inf")
        r[x] = res + 1

    n = I()
    a = LIR(n)
    f = defaultdict(lambda : 0)
    v = defaultdict(lambda : [])
    lis = set()
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
        for j in range(n-2):
            k,l = a[i][j],a[i][j+1]
            x = (min(i,k),max(i,k))
            y = (min(i,l),max(i,l))
            v[y].append(x)
            f[x] += 1
            lis.add(x)
            lis.add(y)
    d = defaultdict(lambda : 1)
    q = deque([])
    r = defaultdict(lambda : 0)
    for i in lis:
        if not f[i]:
            d[i] = 0
            dfs(i)
    if max(f.values()) == float("inf") or min(f.values()):
        print(-1)
    else:
        print(max(r.values()))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

n = int(input())

A = [0]*n
for i in range(n):
    a = list(map(int, input().split()))
    a = [a_-1 for a_ in a]
    A[i] = a

g = [[] for i in range(n*(n-1)//2)]
id = [[[-1] for i in range(n)] for j in range(n)]

temp = 0
for i in range(n-1):
    for j in range(i+1, n):
        id[i][j] = temp
        id[j][i] = temp
        temp += 1

for i in range(n):
    for j in range(n-2):
        g[id[i][A[i][j]]].append(id[i][A[i][j+1]])

visit = [-1]*(n*(n-1)*2)
clc = [-1]*(n*(n-1)*2)
dp = [1]*(n*(n-1)*2)
def dfs(v):
    if visit[v] != -1:
        if clc[v] == -1:
            return -1
        return dp[v]
    visit[v] = 0
    for u in g[v]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res+1)
    clc[v] = 0
    return dp[v]

ans = 0
for i in range(n*(n-1)//2):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import combinations

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

adj = defaultdict(list)
in_deg = {(i, j): 0 for i, j in combinations(range(n), 2)}

for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = min(i, j), max(i, j)
        match2 = min(i, k), max(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [k for k, v in in_deg.items() if v == 0]
day = 0
while cnd:
    nxt_cnd = []
    for u in cnd:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt_cnd.append(v)

    cnd = nxt_cnd
    day += 1

if sum(in_deg.values()) != 0:
    day = -1

print(day)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


match_sm = n * (n - 1) // 2

adj = [np.empty(0, dtype=np.int32) for _ in range(match_sm)]
in_deg = np.zeros(match_sm, dtype=np.int16)
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1] = np.append(adj[match1], match2)
        in_deg[match2] += 1

cnd = np.array([i for i, e in enumerate(in_deg) if e == 0], dtype=np.int32)
day = 0
while cnd.size:
    in_deg[cnd] -= 1
    for u in cnd:
        in_deg[adj[u]] -= 1

    cnd = np.where(in_deg == 0)[0]
    day += 1

if np.any(in_deg >= 1):
    day = -1

print(day)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


match_sm = n * (n - 1) // 2

adj = [[] for _ in range(match_sm)]
in_deg = np.zeros(match_sm, dtype=np.int16)
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = np.array([i for i, e in enumerate(in_deg) if e == 0], dtype=np.int32)
day = 0
while cnd.size:
    in_deg[cnd] -= 1
    for u in cnd:
        in_deg[adj[u]] -= 1

    cnd = np.where(in_deg == 0)[0]
    day += 1

if np.any(in_deg >= 1):
    day = -1

print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
M = []
for i in range(1, N):
	for j in range(i + 1, N + 1):
		M.append((i, j))
# print(M)
ins = {}; outs = {}
for p in M:
	ins[p] = []; outs[p] = []
# print(ins); print(outs)

for i in range(1, N + 1):
	Ai = list(map(int,input().split()))
	for j in range(N - 2):
		i1, j1 = min(i, Ai[j]), max(i, Ai[j])
		i2, j2 = min(i, Ai[j + 1]), max(i, Ai[j + 1])
		outs[(i1, j1)].append((i2, j2))
		ins[(i2, j2)].append((i1, j1))

# print(ins); print(outs)
d = {p : -1 for p in M}
# M0 = [p for p in M if ins[p] == []]
q = deque()
for p in M:
	if ins[p] == []:
		q.append(p); d[p] = 1
ans = -1
while q:
	u = q.pop()
	for v in outs[u]:
		# print(d)
		d[v] = max(d[v], d[u] + 1)
		q.append(v)
		ans = max(ans, d[v])	
	if ans > N * (N - 1) // 2:
		ans = -1
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# dequeにtupleを入れられないので，(i, j)の代わりに整数 N * i + j を頂点とするグラフを考える。

N = int(input())
M = []
for i in range(1, N):
	for j in range(i + 1, N + 1):
		M.append(N * i + j)
# print(M)
ins = {}; outs = {}
for p in M:
	ins[p] = []; outs[p] = []
# print(ins); print(outs)

for i in range(1, N + 1):
	Ai = list(map(int,input().split()))
	for j in range(N - 2):
		i1, j1 = min(i, Ai[j]), max(i, Ai[j])
		i2, j2 = min(i, Ai[j + 1]), max(i, Ai[j + 1])
		outs[N * i1 + j1].append(N * i2 + j2)
		ins[N * i2 + j2].append(N * i1 + j1)

# print(ins); print(outs)
d = {p : -1 for p in M}
# M0 = [p for p in M if ins[p] == []]
q = deque()
for p in M:
	if ins[p] == []:
		q.append(p); d[p] = 1
ans = -1
while q:
	u = q.pop()
	for v in outs[u]:
		# print(d)
		d[v] = max(d[v], d[u] + 1)
		q.append(v)
		ans = max(ans, d[v])	
	if ans > N * (N - 1) // 2:
		ans = -1
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# dequeにtupleを入れられないので，(i, j)の代わりに整数 N * i + j を頂点とするグラフを考える。

N = int(input())
M = []
for i in range(1, N):
	for j in range(i + 1, N + 1):
		M.append(N * i + j)
# print(M)
ins = {}; outs = {}
for p in M:
	ins[p] = []; outs[p] = []
# print(ins); print(outs)

for i in range(1, N + 1):
	Ai = list(map(int,input().split()))
	for j in range(N - 2):
		i1, j1 = min(i, Ai[j]), max(i, Ai[j])
		i2, j2 = min(i, Ai[j + 1]), max(i, Ai[j + 1])
		outs[N * i1 + j1].append(N * i2 + j2)
		ins[N * i2 + j2].append(N * i1 + j1)

# print(ins); print(outs)
M0 = [p for p in M if ins[p] == []]
# print(M0)

ans = -1
for p in M0:
	d = {p : -1 for p in M}
	q = deque(); q.append(p); d[p] = 1
	# print(d)
	while q:
		u = q.pop()
		for v in outs[u]:
			# print(d)
			d[v] = max(d[v], d[u] + 1)
			q.append(v)
			ans = max(ans, d[v])	
	if ans > N * (N - 1) // 2:
		ans = -1
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10**5
N = int(input())
M = []
for i in range(1, N):
	for j in range(i + 1, N + 1):
		M.append((i, j))
# print(M)
ins = {}; outs = {}
for p in M:
	ins[p] = []; outs[p] = []
# print(ins); print(outs)

for i in range(1, N + 1):
	Ai = list(map(int,input().split()))
	for j in range(N - 2):
		i1, j1 = min(i, Ai[j]), max(i, Ai[j])
		i2, j2 = min(i, Ai[j + 1]), max(i, Ai[j + 1])
		outs[(i1, j1)].append((i2, j2))
		ins[(i2, j2)].append((i1, j1))
	
# print(ins); print(outs)
M0 = [p for p in M if ins[p] == []]
# print(M0)

ans = -1
for p in M0:
	d = {p : -1 for p in M}
	q = []; q.append(p); d[p] = 1
	# print(d)
	while q:
		u = q.pop()
		for v in outs[u]:
			# print(d)
			d[v] = max(d[v], d[u] + 1)
			q.append(v)
			ans = max(ans, d[v])	
	if ans > N * (N - 1) // 2:
		ans = -1
		break
print(ans)