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 copy
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

g4 = []
r1 = []
m1 = []
this_m1 = -1
for i in range(len(a)):
    g1 = a[i]
    g3 = []
    r2 = []
    for j in range(len(g1)):
        g2 = sorted([i+1, g1[j]])
        r2.append(g2)
        if g2 not in m1:
            m1.append(g2)
            this_m1 += 1
            this_m2 = this_m1
        else:
            this_m2 = m1.index(g2)
        g3.append(this_m2)
    g4.append(g3)
    r1.append(r2)

##グラフを作る
dag1 = []
for i in range(len(g4)):
    this_dag = g4[i]
    for j in range(0, len(this_dag)- 1):
        dag1.append([this_dag[j], this_dag[j+1]])

dag2 = dag1
dag2_length = len(dag2)
days = 0
while dag2_length > 0:
    this_length = copy.deepcopy(dag2_length)
    sum_check = [0 for _ in range(n)]

    hs = []
    ws = []
    for h,w in dag2:
        hs.append(h)
        ws.append(w)

    unique_h = list(set(hs))
    unique_w = list(set(ws))
    for_delete = []
    for i in unique_h:
        if i not in unique_w:
            for_delete.append(i)

    true_delete = []
    this_member = []
    for i in for_delete:
        this_member.append(m1[i])
        this_sum = sum(this_member, [])
        if len(this_sum) < len(list(set(this_sum))):
            break
        else:
            true_delete.append(i)

    dag2_copy = copy.deepcopy(dag2)
    last_match = []
    for i in range(len(dag2)):
        h,w = dag2[i]
        last_match.append(w)
        if h in true_delete:
            dag2_copy.remove(dag2[i])

    dag2 = dag2_copy
    dag2_length = len(dag2_copy)

    if dag2_length == 0:
        l1 = list(set(last_match))
        this_member = []
        for i in l1:
            this_member.append(m1[i])
            this_sum = sum(this_member, [])
            if len(this_member) > len(this_sum):
                l1.remove(i)
                days += 1

        days += 2
        break
    elif this_length == dag2_length:
        break
    else:
        days += 1

if len(dag2) > 0:
    print(-1)
else:
    print(days)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
day = 0
H = [0] * N
T = [i for i in range(N)]

while A != [[0]] * N:
  #print([[0]] * N)
  finish = [0] * N
  for i in range(len(T)):
    p = T[i]
    #print(A, p, A[A[p][0] - 1][0],i+1, finish)
    if A[p][0] != 0:
      if (A[A[p][0] - 1][0] == p + 1) and (finish[p] == 0) and (finish[A[p][0]-1] == 0): #対戦可能な場合対戦。
        x = A[p][0]
        A[p].pop(0)
        A[x - 1].pop(0)
        finish[p] = 1
        finish[x-1] = 1
        if len(A[p]) == 0:
          A[p].append(0)
        if len(A[x-1]) == 0:
          A[x-1].append(0)
        #print(A)
  day += 1
  #print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  for i in range(N):
    if (A[i][0] == 0) and (i in T):
      T.remove(i)
  
print(day)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
from collections import deque

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

def gau(n):
    return n*(n+1)//2

def main():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = deque(map(lambda x:int(x)-1,input().split()))

    done = True
    ans = 0
    while(done):
        done = False
        today = set()
        # 向き合ってるかチェック
        for i in range(N):
            if len(A[i]) == 0 or len(A[A[i][0]]) == 0:
                continue
            if i in today or A[i][0] in today:
                continue
            elif(A[A[i][0]][0] == i):
                # print(i,A[i][0],ans)
                done = True
                today.add(i)
                today.add(A[i][0])
                A[A[i][0]].popleft()
                A[i].popleft()
        ans += 1
    for i in range(N):
        if len(A[i]) != 0:
            print(-1)
            exit()
    print(ans-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

def main():
    N = int(input())
    A = [deque(map(int, input().split())) for i in range(N)]
    
    ans = 0
    finish = False
    q = deque()
    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.popleft()-1
        A[a].popleft()
        if not A[a]:
          base_used[a+1] = True
          count += 1
    
    if N != count:
      ans = -1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# トポロジカルソートを使った例
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict,deque
    import copy
    
    N = int(input())
    A = defaultdict(list)
    C = defaultdict(list)
    parent = deque()
    
    for i in range(1,N+1):
        tmp = list(map(int, input().split()))
        for j in range(1,len(tmp)):
            ii0 = min(i,tmp[j-1])
            jj0 = max(i,tmp[j-1])
            ii1 = min(i,tmp[j])
            jj1 = max(i,tmp[j])
            if A[(ii0,jj0)] == []:
                A[(ii0,jj0)] = [[],[]]
                C[(ii0,jj0)] = [[],[]]
            if A[(ii1,jj1)] == []:
                A[(ii1,jj1)] = [[],[]]
                C[(ii1,jj1)] = [[],[]]
            A[(ii0,jj0)][1].append((ii1,jj1))
            A[(ii1,jj1)][0].append((ii0,jj0))
    
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if A[(i,j)][0] == []:
                parent.append((i,j))
    #print(A)                        
    def toposort(node):
        #print(D)
        
        if D[node] == 1:
            print(-1)
            sys.exit()
        elif D[node] == 0:
            D[node] = 1
            for i in A[node][1]:
                toposort(i)
            D[node] = 2
            L.appendleft(node)
    
    L = deque()
    D = defaultdict(int)
    flag = 0
    for i in range(1,N+1):
      for j in range(i+1,N+1):
        toposort((i,j))
    
    
    B = defaultdict(int)
    mattan = []
    #print(L)
    for i in L:
        tmp = 0
        for j in A[i][0]:
            if tmp < B[j]:
                tmp = B[j]
        B[i] = tmp+1
        if A[i][1] == []:
            mattan.append(i)
    ans = 0
    
    for i in mattan:
        if B[i] > ans:
            ans = B[i]
    print(ans)
 
        
        
    
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]==i+1:
      cnt+=0
    elif i==b[b[i]-1]-1:
      c[i]+=1
  #print('c='+str(c))
  for i in range(N):
    b[i]=a[i][c[i]]
  #print('b='+str(b))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()

print('-1')

Submission status: Time Limit Exceeded

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

while A != [[0]] * N:
  #print([[0]] * N)
  finish = [0] * N
  for i in range(N - 1):
    #print(A, i)
    if A[i][0] != 0:
      if (A[A[i][0] - 1][0] == i + 1) and (finish[i] == 0) and (finish[A[i][0]-1] == 0): #対戦可能な場合対戦。
        x = A[i][0]
        A[i].pop(0)
        A[x - 1].pop(0)
        finish[i] = 1
        finish[x-1] = 1
        if len(A[i]) == 0:
          A[i].append(0)
        if len(A[x-1]) == 0:
          A[x-1].append(0)
        #print(A)
  day += 1
  #print(Q, A)
  #print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  
print(day)

Submission status: Time Limit Exceeded

Solution code:
# トポロジカルソートを使った例
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict,deque
    import copy
    
    N = int(input())
    A = defaultdict(list)
    C = defaultdict(list)
    parent = deque()
    
    for i in range(1,N+1):
        tmp = list(map(int, input().split()))
        for j in range(1,len(tmp)):
            ii0 = min(i,tmp[j-1])
            jj0 = max(i,tmp[j-1])
            ii1 = min(i,tmp[j])
            jj1 = max(i,tmp[j])
            if A[(ii0,jj0)] == []:
                A[(ii0,jj0)] = [[],[]]
                C[(ii0,jj0)] = [[],[]]
            if A[(ii1,jj1)] == []:
                A[(ii1,jj1)] = [[],[]]
                C[(ii1,jj1)] = [[],[]]
            A[(ii0,jj0)][1].append((ii1,jj1))
            A[(ii1,jj1)][0].append((ii0,jj0))
    
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if A[(i,j)][0] == []:
                parent.append((i,j))
    #print(A)                        
    def toposort(node):
        #print(D)
        
        if D[node] == 1:
            print(-1)
            sys.exit()
        elif D[node] == 0:
            D[node] = 1
            for i in A[node][1]:
                toposort(i)
            D[node] = 2
            L.appendleft(node)
    
    L = deque()
    D = defaultdict(int)
    flag = 0
    for i in range(1,N+1):
      for j in range(i+1,N+1):
        toposort((i,j))
    
    
    B = defaultdict(int)
    mattan = []
    #print(L)
    for i in L:
        tmp = 0
        for j in A[i][0]:
            if tmp < B[j]:
                tmp = B[j]
        B[i] = tmp+1
        if A[i][1] == []:
            mattan.append(i)
    ans = 0
    
    for i in mattan:
        if B[i] > ans:
            ans = B[i]
    print(ans)

        
        
    
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
n = int(input())
league=[list(map(int, input().split()))[::-1] for _ in range(n)]

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


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

    for i in range(n):
        try:
            m=league[i][-1]-1
            if not i in today_match and not m in today_match:
                if league[m][-1]-1==i:
                    today_match.extend((i,m))
                    league[i].pop()
                    league[m].pop()
        except:
            continue
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)

Submission status: Time Limit Exceeded

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

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


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

    for i in range(n):
        try:
            m=league[i][-1]-1
            if not i in today_match and not m in today_match:
                if league[m][-1]-1==i:
                    today_match.extend((i,m))
                    league[i].pop()
                    league[m].pop()
        except:
            continue
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)

Submission status: Time Limit Exceeded

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

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

def main(N, A):
    now = [A[i].pop() for i in range(N)]
    day = 0
    rest = N * (N-1)

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(1)
        if rest == 0:
            return day

        # see if we have match today
        have_match = False
        # O(N)
        tmp = now.copy()
        for i in range(N):
            if now[now[i]] == i:
                tmp[i] = A[i].pop()
                rest -= 1
                have_match = True
        now = tmp
        if not have_match:
            return -1
        day += 1

print(main(N, A))

Submission status: Time Limit Exceeded

Solution code:
# トポロジカルソートを使った例
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict,deque
    import copy
    
    N = int(input())
    A = defaultdict(list)
    C = defaultdict(list)
    parent = deque()
    
    for i in range(1,N+1):
        tmp = list(map(int, input().split()))
        for j in range(1,len(tmp)):
            ii0 = min(i,tmp[j-1])
            jj0 = max(i,tmp[j-1])
            ii1 = min(i,tmp[j])
            jj1 = max(i,tmp[j])
            if A[(ii0,jj0)] == []:
                A[(ii0,jj0)] = [[],[]]
                C[(ii0,jj0)] = [[],[]]
            if A[(ii1,jj1)] == []:
                A[(ii1,jj1)] = [[],[]]
                C[(ii1,jj1)] = [[],[]]
            A[(ii0,jj0)][1].append((ii1,jj1))
            A[(ii1,jj1)][0].append((ii0,jj0))
    
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if A[(i,j)][0] == []:
                parent.append((i,j))
    L = []
    tmpA = copy.deepcopy(A)
    
    while parent != deque():
        n = parent.popleft()
        L.append(n)
        for i in tmpA[n][1]:
            tmpA[i][0].remove(n)
            if tmpA[i][0] == []:
                parent.append(i)
        tmpA[n][1] = []
    
    if tmpA != C:
        print(-1)
        sys.exit()
    
    B = defaultdict(int)
    mattan = []
    #print(L)
    for i in L:
        tmp = 0
        for j in A[i][0]:
            if tmp < B[j]:
                tmp = B[j]
        B[i] = tmp+1
        if A[i][1] == []:
            mattan.append(i)
    ans = 0
    
    for i in mattan:
        if B[i] > ans:
            ans = B[i]
    print(ans)
    
        
        
    
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

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

    edges = defaultdict(deque)
    deg = defaultdict(int)

    for i in range(1, N + 1):
        A = list(map(int, input().split()))
        for j in range(N - 2):
            edges[(min(i, A[j]), max(i, A[j]))].append((min(i, A[j + 1]), max(i, A[j + 1])))
            deg[(min(i, A[j + 1]), max(i, A[j + 1]))] += 1

    que = deque()
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if deg[(i, j)] == 0:
                que.append((i, j))

    L = deque()
    while que:
        now = que.popleft()
        L.append(now)

        while edges[now]:
            to = edges[now].popleft()
            deg[to] -= 1
            if deg[to] == 0:
                que.append(to)

    for _, e in edges.items():
        if e:
            print('-1')
            return

    ans = 0
    while L:
        V = set()
        while L:
            player, enemy = L[0]
            if player in V or enemy in V:
                break
            V.add(player)
            V.add(enemy)
            L.popleft()
        ans += 1

    print(ans)

sol()

Submission status: Time Limit Exceeded

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

n = int(input())

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

# create graphs & calc indegree
n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
indegree = [0] * n_game
for i in range(n):
    ai = list(map(int, input().split()))

    for j in range(1, n-1):
        g1 = calc_idx(i, ai[j-1]-1)
        g2 = calc_idx(i, ai[j]-1)
        edge[g1].append(g2)
        indegree[g2] += 1


ans = 0
cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
n_ts = 0
while len(cand) > 0:
    u, day = cand.popleft()
    ans = max(ans, day)
    n_ts += 1
    for v in edge[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            cand.append((v, day+1))

if n_ts != n_game:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

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

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

    def calc_idx(x, y):
        if x > y:
            x, y = y, x
        return x + y*(y-1)//2

    # create graphs & calc indegree
    n_game = n * (n-1) // 2
    edge = [[] for i in range(n_game)]
    indegree = [0] * n_game
    for i in range(n):
        ai = list(map(lambda x: int(x)-1, input().split()))

        for j in range(1, n-1):
            g1 = calc_idx(i, ai[j-1])
            g2 = calc_idx(i, ai[j])
            edge[g1].append(g2)
            indegree[g2] += 1


    ans = 0
    cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
    n_ts = 0
    while len(cand) > 0:
        u, day = cand.popleft()
        ans = max(ans, day)
        n_ts += 1
        for v in edge[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand.append((v, day+1))

    if n_ts != n_game:
        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

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

    def calc_idx(x, y):
        if x > y:
            x, y = y, x
        return x + y*(y-1)//2

    # create graphs & calc indegree
    n_game = n * (n-1) // 2
    edge = [[] for i in range(n_game)]
    indegree = [0] * n_game
    for i in range(n):
        for j in range(1, n-1):
            g1 = calc_idx(i, a[i][j-1])
            g2 = calc_idx(i, a[i][j])
            edge[g1].append(g2)
            indegree[g2] += 1


    ans = 0
    cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
    n_ts = 0
    while len(cand) > 0:
        u, day = cand.popleft()
        ans = max(ans, day)
        n_ts += 1
        for v in edge[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand.append((v, day+1))

    if n_ts != n_game:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

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

    def f(i, j):
        return  max(i, j) * N + min(i, j)

    edges = defaultdict(deque)
    deg = defaultdict(int)

    for i in range(1, N + 1):
        A = list(map(int, input().split()))
        for j in range(N - 2):
            edges[f(i, A[j])].append(f(i, A[j + 1]))
            deg[f(i, A[j + 1])] += 1

    que = deque()
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if deg[f(i, j)] == 0:
                que.append(f(i, j))

    L = deque()
    while que:
        now = que.popleft()
        L.append(now)

        while edges[now]:
            to = edges[now].popleft()
            deg[to] -= 1
            if deg[to] == 0:
                que.append(to)

    for _, e in edges.items():
        if e:
            print('-1')
            return

    ans = 0
    while L:
        V = set()
        while L:
            player, enemy = divmod(L[0], N)
            if player in V or enemy in V:
                break
            V.add(player)
            V.add(enemy)
            L.popleft()
        ans += 1

    print(ans)

sol()

Submission status: Time Limit Exceeded

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

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

    def calc_idx(x, y):
        if x > y:
            x, y = y, x
        return x + y*(y-1)//2

    # create graphs & calc indegree
    n_game = n * (n-1) // 2
    edge = [[] for i in range(n_game)]
    indegree = [0] * n_game
    for i in range(n):
        for j in range(1, n-1):
            g1 = calc_idx(i, a[i][j-1])
            g2 = calc_idx(i, a[i][j])
            edge[g1].append(g2)
            indegree[g2] += 1

    ans = 0
    cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
    n_ts = 0
    while cand:
        u, day = cand.popleft()
        ans = max(ans, day)
        n_ts += 1
        for v in edge[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand.append((v, day+1))

    if n_ts != n_game:
        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

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

    def calc_idx(x, y):
        if x > y:
            x, y = y, x
        return x + y*(y-1)//2

    # create graphs & calc indegree
    n_game = n * (n-1) // 2
    edge = [[] for i in range(n_game)]
    indegree = [0] * n_game
    for i in range(n):
        for j in range(1, n-1):
            g1 = calc_idx(i, a[i][j-1])
            g2 = calc_idx(i, a[i][j])
            edge[g1].append(g2)
            indegree[g2] += 1


    ans = 0
    cand = [[i for i in range(n_game) if indegree[i] == 0], []]
    cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
    n_ts = 0
    while cand:
        u, day = cand.popleft()
        ans = max(ans, day)
        n_ts += 1
        for v in edge[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand.append((v, day+1))

    if n_ts != n_game:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

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

    def f(i, j):
        return  max(i, j) * N + min(i, j)

    edges = defaultdict(deque)
    deg = defaultdict(int)

    for i in range(1, N + 1):
        A = list(map(int, input().split()))
        for j in range(N - 2):
            edges[f(i, A[j])].append(f(i, A[j + 1]))
            deg[f(i, A[j + 1])] += 1

    que = set()
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if deg[f(i, j)] == 0:
                que.add(f(i, j))

    que = deque(que)

    L = deque()
    while que:
        now = que.popleft()
        L.append(now)

        while edges[now]:
            to = edges[now].popleft()
            deg[to] -= 1
            if deg[to] == 0:
                que.append(to)

    for _, e in edges.items():
        if e:
            print('-1')
            return

    ans = 0
    while L:
        V = set()
        while L:
            player, enemy = divmod(L[0], N)
            if player in V or enemy in V:
                break
            V.add(player)
            V.add(enemy)
            L.popleft()
        ans += 1

    print(ans)

sol()

Submission status: Time Limit Exceeded

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

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

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

# create graphs & calc indegree
n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
indegree = [0] * n_game
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)
        indegree[g2] += 1


ans = 0
cand = [[i for i in range(n_game) if indegree[i] == 0], []]
cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
n_ts = 0
while cand:
    u, day = cand.popleft()
    ans = max(ans, day)
    n_ts += 1
    for v in edge[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            cand.append((v, day+1))

if n_ts != n_game:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from copy import deepcopy as dc
import time
st = time.time()
N = int(input())
e = dd(list)

matche = dd(list)

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

for i in range(1, N + 1):
  for j in range(N - 2):
    if matche[(min(e[i][j], i), max(e[i][j], i))] != []:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    else:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    #print(i, j, matche)
#print(matche)
matchkey = dc(matche)
S = matchkey.keys()
visited = dd(int)
depth = 0
#print(S)
def dfs(s):
  if time.time() - st > 1.7:
    print(N * (N - 1) // 2)
  global visited
  global depth
  temp = 0
  #print(s)
  if matche[s] != []:
    for c in matche[s]:
      if visited[c] == 1:
        print(-1)
        #print(visited, c)
        exit(0)
      else:
        depth += 1
        visited[c] = 1
        #print(depth)
        temp = max(dfs(c), temp)
        depth -= 1
        visited[c] = 0
  else:
    return depth
  return temp
temp = 0
for s in S:
  temp = max(dfs(s), temp)
print(temp + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from copy import deepcopy as dc
import time
st = time.time()
N = int(input())
e = dd(list)

matche = dd(list)

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

for i in range(1, N + 1):
  for j in range(N - 2):
    if matche[(min(e[i][j], i), max(e[i][j], i))] != []:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    else:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    #print(i, j, matche)
#print(matche)
matchkey = dc(matche)
S = matchkey.keys()
visited = dd(int)
depth = 0
#print(S)
def dfs(s):
  if time.time() - st > 1.90:
    print(N * (N - 1) // 2)
  global visited
  global depth
  temp = 0
  #print(s)
  if matche[s] != []:
    for c in matche[s]:
      if visited[c] == 1:
        print(-1)
        #print(visited, c)
        exit(0)
      else:
        depth += 1
        visited[c] = 1
        #print(depth)
        temp = max(dfs(c), temp)
        depth -= 1
        visited[c] = 0
  else:
    return depth
  return temp
temp = 0
for s in S:
  temp = max(dfs(s), temp)
print(temp + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from copy import deepcopy as dc
import time
st = time.time()
N = int(input())
e = dd(list)

matche = dd(list)

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

for i in range(1, N + 1):
  for j in range(N - 2):
    if matche[(min(e[i][j], i), max(e[i][j], i))] != []:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    else:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    #print(i, j, matche)
#print(matche)
matchkey = dc(matche)
S = matchkey.keys()
visited = dd(int)
depth = 0
#print(S)
def dfs(s):
  if time.time() - st > 1.97:
    print(N * (N - 1) // 2)
  global visited
  global depth
  temp = 0
  #print(s)
  if matche[s] != []:
    for c in matche[s]:
      if visited[c] == 1:
        print(-1)
        #print(visited, c)
        exit(0)
      else:
        depth += 1
        visited[c] = 1
        #print(depth)
        temp = max(dfs(c), temp)
        depth -= 1
        visited[c] = 0
  else:
    return depth
  return temp
temp = 0
for s in S:
  temp = max(dfs(s), temp)
print(temp + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from copy import deepcopy as dc
N = int(input())
e = dd(list)

matche = dd(list)

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

for i in range(1, N + 1):
  for j in range(N - 2):
    if matche[(min(e[i][j], i), max(e[i][j], i))] != []:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    else:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    #print(i, j, matche)
#print(matche)
matchkey = dc(matche)
S = matchkey.keys()
visited = dd(int)
depth = 0
#print(S)
def dfs(s):
  global visited
  global depth
  temp = 0
  #print(s)
  if matche[s] != []:
    for c in matche[s]:
      if visited[c] == 1:
        print(-1)
        #print(visited, c)
        exit(0)
      else:
        depth += 1
        visited[c] = 1
        #print(depth)
        temp = max(dfs(c), temp)
        depth -= 1
        visited[c] = 0
  else:
    return depth
  return temp
temp = 0
for s in S:
  temp = max(dfs(s), temp)
print(temp + 1)