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:
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
import sys
sys.setrecursionlimit(10**7)

m=(n*(n-1))//2
g=[[] for _ in range(m)]
for i in range(n):
  for j in range(n-2):
    if i+1>a[i][j]:
      t0=f((a[i][j],i+1))
    else:
      t0=f((i+1,a[i][j]))
    if i+1>a[i][j+1]:
      t1=f((a[i][j+1],i+1))
    else:
      t1=f((i+1,a[i][j+1]))
    g[t0].append(t1)
def dfs(t):
  if v[t]:
    if c[t]==0:
      return -1
    else:
      dp[t]
  v[t]=1
  for l in g[t]:
    ret=dfs(l)
    if ret==-1:return -1
    dp[t]=max(dp[t],ret+1)
  c[t]=1
  return dp[t]
ans=0
for i in range(m):
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  tmp=dfs(i)
  if tmp==-1:
    print(-1)
    exit()
  ans=max(ans,tmp)
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for _ in range(n)]
ans=0
na={1}
cnt=0
while cnt<(n*(n-1))//2:
  ans+=1
  na=set(())
  for i in range(n):
    if i+1 in na:continue
    if not a[i]:continue
    if a[i] and a[i][0] in na:continue
    if a[a[i][0]-1][0]==i+1:
      na.add(i+1)
      na.add(a[i][0])
      a[a[i][0]-1].popleft()
      a[i].popleft()
      cnt+=1
  if not na:
    print(-1)
    exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for _ in range(n)]
ans=0
na={1}
cnt=0
while cnt<(n*(n-1))//2:
  ans+=1
  na=set(())
  """
  d={}
  for i in range(n):
    if a[i]:
      if a[i][0]in d:
        d[a[i][0]].append(i+1)
      else:
        d[a[i][0]]=deque([i+1])
  print(d)
  """
  for i in range(n):
    if i+1 in na:continue
    if not a[i]:continue
    if a[i] and a[i][0] in na:continue
    if a[a[i][0]-1][0]==i+1:
      na.add(i+1)
      na.add(a[i][0])
      a[a[i][0]-1].popleft()
      a[i].popleft()
      cnt+=1
  if not na:
    print(-1)
    exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N = int(input())

    A_all = []
    for i in range(N):
        As = list(map(int, input().split()))
        A_all.append(As)
    A_index = [0] * N

    for i in range(N * (N - 1) // 2 + 1):
        matches = set()
        for j in range(1, N+1):
            A_idx = A_index[j - 1]
            if A_idx >= N - 1:
                continue
            k = A_all[j - 1][A_idx]
            B_idx = A_index[k - 1]
            if B_idx >= N - 1:
                continue
            if j == A_all[k - 1][B_idx]:
                pair = tuple(sorted([j, k]))
                matches.add(pair)

        if not matches:
            break

        for match in matches:
            for j in match:
                A_index[j - 1] += 1

    if all([A_idx == N - 1 for A_idx in A_index]):
        print(i)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(int(x) - 1 for x in input().split()) for _ in range(n)]
B = [0] * n

ans = 1
while True:
    day_set = set()
    for i in range(n):
        if i in day_set or B[i] >= n - 1:
            continue
        j = A[i][B[i]]
        if j in day_set or B[j] >= n - 1:
            continue
        if A[j][B[j]] == i:
            B[i] += 1
            B[j] += 1
            day_set.add(i)
            day_set.add(j)
            if all(b >= n - 1 for b in B):
                print(ans)
                exit()
    if not day_set:
        print(-1)
        exit()
    else:
        ans += 1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(int(x) - 1 for x in input().split()) for _ in range(n)]
B = [0] * n

ans = 1
while True:
    day_set = set()
    for i in range(n):
        if i in day_set or B[i] == n - 1:
            continue
        j = A[i][B[i]]
        if j in day_set or B[j] == n - 1:
            continue
        if A[j][B[j]] == i:
            B[i] += 1
            B[j] += 1
            day_set.add(i)
            day_set.add(j)
            if all(b == n - 1 for b in B):
                print(ans)
                exit()
    if not day_set:
        print(-1)
        exit()
    else:
        ans += 1

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    #A = [LI() for _ in range(N)]
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            #print(fr,to)
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    # https://mhiro216.hatenablog.com/entry/2019/09/08/142414
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  # 計算が終わっていない頂点を2度訪れるのはループがあるということ
            return dp[v]
        visited[v] = True
        for u in V[v]:  # 全ての辺をなめる
            res = dfs(u)
            if res == -1: return -1  # ループがあれば-1を返す
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  # ループがあれば-1を返す（問題文の指示）
            return
    print(ans)
    return

def examE2():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    #A = [LI() for _ in range(N)]
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            #print(fr,to)
            V[fr].append(to)
    #print(V)


    # 閉路検出
    def hasCycle(n,V):
        visited = [False]*n
        used = [False]*n

        def dfs(s, p=-1):
            if used[s]:
                return False

            now_use.add(s)

            for v in V[s]:
                if visited[v]:
                    return True
                if v in now_use:
                    continue
                visited[v] = True
                res = dfs(v, s)
                visited[v] = False
                if res:
                    return True
            return False

        has_cycle = False

        for i in range(node):
            now_use = set()
            if used[i]:
                continue
            visited[i] = True
            if dfs(i):
                has_cycle = True
                break
            for u in now_use:
                used[u] = True
            visited[i] = False

        return has_cycle

    if hasCycle(node,V):
        print(-1)
        return

    def getMaxLength(n,V):
        visited = [False]*n
        def dfs(s,p=-1):
            res = 0

            for v in V[s]:
                if v==p:
                    continue
                visited[v] = True
                child = dfs(v, s)
                if res<child:
                    res = child

                visited[v] = False

            return res+1

        max_length = 0

        for i in range(n):
            length = dfs(i)
            if max_length<length:
                max_length = length

        return max_length

    ans = getMaxLength(node,V)
    print(ans)
    return

def examF():
    # 合ってんのこれ?????
    def calc_L(a,b):
        return (a**2 + b**2)**(1/2)
    N = I()
    X = [[]for _ in range(N)]
    for i in range(N):
        x,y = LI()
        d = math.degrees(math.atan2(y,x))
        if d<0:
            d += 360
        X[i] = [d,x,y]
    X.sort()
    #print(X)
    ans = 0
    for i in range(N):
        cur_X = 0; cur_Y = 0
        for d2,x2,y2 in (X[i:] + X[:i]):
            if calc_L(cur_X+x2,cur_Y+y2)<calc_L(cur_X,cur_Y):
                continue
            cur_X += x2
            cur_Y += y2

        now = calc_L(cur_X,cur_Y)
        if now>ans:
            ans = now

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE2()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    node = N*(N-1)//2
    V = [[]for _ in range(node)]
    D = [[0]*N for _ in range(N)]
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[i][j] = cur
            D[j][i] = cur
            cur += 1
    #A = [LI() for _ in range(N)]
    for i in range(N):
        a = LI()
        for j in range(N-2):
            fr = D[i][a[j]-1]
            to = D[i][a[j+1]-1]
            #print(fr,to)
            V[fr].append(to)

    visited = [False] * node
    calculated = [False] * node
    dp = [1] * node
    # https://mhiro216.hatenablog.com/entry/2019/09/08/142414
    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1  # 計算が終わっていない頂点を2度訪れるのはループがあるということ
            return dp[v]
        visited[v] = True
        for u in V[v]:  # 全ての辺をなめる
            res = dfs(u)
            if res == -1: return -1  # ループがあれば-1を返す
            elif res+1>dp[v]:
                dp[v] = res + 1
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(node):
        res = dfs(i)
        ans = max(ans,res)
        if res == -1:
            print('-1')  # ループがあれば-1を返す（問題文の指示）
            return
    print(ans)
    return

def examE2():
    N = I()
    V = defaultdict(set)
    for i in range(N):
        A = LI()
        for j in range(N-2):
            a0, a1 = sorted([i,A[j]-1]), sorted([i,A[j+1]-1])
            V[tuple(a0)].add(tuple(a1))
    #print(V)

    # 閉路検出
    def hasCycle(V):
        visited = defaultdict(lambda: False)

        def dfs(s, p=-1):
            res = False

            if not s in V:
                return False

            for v in V[s]:
                if v == p:
                    continue
                if visited[v]:
                    return True
                visited[v] = True
                res |= dfs(v, s)
                visited[v] = False
                if res:
                    break
            return res

        has_cycle = False
        for i in V.keys():
            if dfs(i):
                has_cycle = True
                break
        #print(has_cycle)
        return has_cycle

    if hasCycle(V):
        print(-1)
        return

    def getMaxLength(V):
        visited = defaultdict(lambda: False)
        def dfs(s,p=-1):
            res = 0

            if not s in V:
                return res+1

            for v in V[s]:
                if v==p:
                    continue
                visited[v] = True
                child = dfs(v, s)
                if res<child:
                    res = child

                visited[v] = False

            return res+1

        max_length = 0

        for i in V.keys():
            length = dfs(i)
            if max_length<length:
                max_length = length

        return max_length

    ans = getMaxLength(V)
    print(ans)
    return

def examF():
    # 合ってんのこれ?????
    def calc_L(a,b):
        return (a**2 + b**2)**(1/2)
    N = I()
    X = [[]for _ in range(N)]
    for i in range(N):
        x,y = LI()
        d = math.degrees(math.atan2(y,x))
        if d<0:
            d += 360
        X[i] = [d,x,y]
    X.sort()
    #print(X)
    ans = 0
    for i in range(N):
        cur_X = 0; cur_Y = 0
        for d2,x2,y2 in (X[i:] + X[:i]):
            if calc_L(cur_X+x2,cur_Y+y2)<calc_L(cur_X,cur_Y):
                continue
            cur_X += x2
            cur_Y += y2

        now = calc_L(cur_X,cur_Y)
        if now>ans:
            ans = now

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE2()

"""

"""

Submission status: Time Limit Exceeded

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

N = int(readline())
A = [None] * N
for i in range(N):
  # 後ろからpopできるように逆順リストで持つ
  A[i] = list(map(lambda x:x - 1,map(int,readline().split())))[::-1]
  
# 今日試合ができる可能性がある人リスト
candi = set(range(N))

day = 0
while True:
  day += 1
  nex = set()
  done = set()
  for player in candi:
    if player in done:
      continue
    # player が試合できるかチェック
    if not A[player]:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if A[rival][-1] == player:
      # 試合できる
      A[player].pop()
      A[rival].pop()
      if A[player]:
        nex.add(player)
      done.add(player)
      if A[rival]:
        nex.add(rival)
      done.add(rival)
    else:
      # 試合できないが、明日も試合できる状態
      nex.add(player)
  if len(done) == 0:
    # 一試合もできなかった
    print(-1)
    exit(0)
  if len(nex) == 0:
    print(day)
    exit(0)
  candi = nex

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
#それぞれ長さはn-1
a=[[(j-1,i) if j-1<i else (i,j-1) for j in list(map(int,input().split()))] for i in range(n)]
#試合の候補をいれる
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#どこまで見たか
b=[0]*n
#最大n(n-1)/2回
ans=0
while len(d):
    ans+=1
    nextd=[]
    cleard=[]
    #一個も同じのなかったらむり
    g=True
    for i in d:
        if d[i]==2:
            g=False
            e,f=i
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
    if g:
        exit(print(-1))       
    for i in nextd:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for i in cleard:
        d.pop(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
#それぞれ長さはn-1
a=[[(j-1,i) if j-1<i else (i,j-1) for j in list(map(int,input().split()))] for i in range(n)]
#試合の候補をいれる
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#どこまで見たか
b=[0]*n
check=[n-1]*n
#最大n(n-1)/2回
ans=0
while b!=check:
    ans+=1
    nextd=[]
    cleard=[]
    #一個も同じのなかったらむり
    g=True
    #print(d)
    for i in d:
        if d[i]==2:
            g=False
            e,f=i
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
    if g:
        exit(print(-1))       
    for i in nextd:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for i in cleard:
        d.pop(i)
print(ans)

Submission status: Time Limit Exceeded

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

n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
g={(i,j):[] for i in range(n+1) for j in range(n+1) if i<j}
visit={(i,j):0 for i in range(n+1) for j in range(n+1) if i<j}
d={(i,j):0 for i in range(n+1) for j in range(n+1) if i<j}

inf=10**10

for i in range(1,n+1):
    last=(0,1)
    for j in list(map(int,input().split())):
        current=(min(i,j),max(i,j))
        g[last].append(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs((0,1)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
g={(i,j):set() for i in range(n+1) for j in range(n+1) if i<j}
visit={(i,j):0 for i in range(n+1) for j in range(n+1) if i<j}
d={(i,j):0 for i in range(n+1) for j in range(n+1) if i<j}

inf=10**10

for i in range(1,n+1):
    last=(0,1)
    for j in list(map(int,input().split())):
        current=(min(i,j),max(i,j))
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
        
    if len(g[u])==0:
        return 0
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        ans=max(ans,1+dfs(v))
    
    visit[u]=2
    d[u]=ans
    return d[u]

print(dfs((0,1)))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    loops = 0
    while loops < 10**5:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in (players-finished):
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
        loops += 1
    assert loops < 10**5, "error"
    print(day)





if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    while True:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in (players-finished):
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
    print(day)





if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    while True:
        todays_players = set()
        matched = False
        if all(map(lambda x: x==N-1, ptrs)):
            break
        #print("------")
        for home in range(N):
            if ptrs[home] == N-1:
                continue
            away = A[home][ptrs[home]]
            if ptrs[away] == N-1:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
    print(day)





if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
a=[0]+[list(map(int,sys.stdin.readline().strip().split()[::-1])) for _ in range(n)]

pairs=n*(n-1)//2
ans=0

while pairs>0:
    ans+=1
    tpairs=0
    dic={}

    for i in range(1,n+1):
        if len(a[i])==0:
            continue
        lasta=a[i][-1]
        p=(min(i,lasta),max(i,lasta))

        if p in dic:
            dic[p]+=1
        else:
            dic[p]=1

    for (i,j),v in dic.items():
        if v==1:
            continue

        a[i].pop()
        a[j].pop()
        tpairs+=1
    
    if tpairs==0:
        print(-1)
        break

    pairs-=tpairs
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n=int(input())
a=[0]+[list(map(int,sys.stdin.readline().strip().split()[::-1])) for _ in range(n)]

pairs=n*(n-1)//2
ans=0

while pairs>0:
    ans+=1
    tpairs=0
    x=[]

    for i in range(1,n+1):
        if len(a[i])==0:
            continue
        lasta=a[i][-1]
        x.append((min(i,lasta),max(i,lasta)))
    
    cnt=Counter(x)

    for (i,j),v in cnt.most_common():
        if v==1:
            break

        a[i].pop()
        a[j].pop()
        tpairs+=1
    
    if tpairs==0:
        print(-1)
        break

    pairs-=tpairs
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n=int(input())
a=[0]+[list(map(int,sys.stdin.readline().strip().split()[::-1])) for _ in range(n)]

pairs=n*(n-1)//2
ans=0

while pairs>0:
    ans+=1
    tpairs=0
    x=[]

    for i in range(1,n+1):
        if len(a[i])==0:
            continue
        x.append((min(i,a[i][-1]),max(i,a[i][-1])))
    
    cnt=Counter(x)

    for (i,j),v in cnt.most_common():
        if v==1:
            break

        a[i].pop()
        a[j].pop()
        tpairs+=1
    
    if tpairs==0:
        print(-1)
        break

    pairs-=tpairs
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

pairs=n*(n-1)//2
ans=0

while pairs>0:
    ans+=1
    tpairs=0
    x=[]

    for i in range(1,n+1):
        if len(a[i])==0:
            continue
        x.append((min(i,a[i][-1]),max(i,a[i][-1])))
    
    cnt=Counter(x)

    for (i,j),v in cnt.items():
        if v==1:
            continue

        a[i].pop()
        a[j].pop()
        tpairs+=1
    
    if tpairs==0:
        print(-1)
        break

    pairs-=tpairs
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import networkx as nx

input = sys.stdin.readline

N = int(input())
G = nx.DiGraph()
G.add_nodes_from([(i, j) for i, j in itertools.combinations(range(1, N + 1), 2)])
for i in range(1, N + 1):
    Ai = tuple(map(int, input().split()))
    for j in range(N - 2):
        G.add_edge((min(i, Ai[j]), max(i, Ai[j])),
                   (min(i, Ai[j + 1]), max(i, Ai[j + 1])))

if nx.is_directed_acyclic_graph(G):
    print(nx.dag_longest_path_length(G) + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import networkx as nx

N = int(input())
G = nx.DiGraph()
G.add_nodes_from([(i, j) for i, j in itertools.combinations(range(1, N + 1), 2)])
for i in range(1, N + 1):
    Ai = tuple(map(int, input().split()))
    for j in range(N - 2):
        G.add_edge((min(i, Ai[j]), max(i, Ai[j])),
                   (min(i, Ai[j + 1]), max(i, Ai[j + 1])))

if nx.is_directed_acyclic_graph(G):
    print(nx.dag_longest_path_length(G) + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

N = int(input())
G = nx.DiGraph()
for i in range(1, N + 1):
    Ai = tuple(map(int, input().split()))
    for j in range(N - 2):
        G.add_edge((min(i, Ai[j]), max(i, Ai[j])),
                   (min(i, Ai[j + 1]), max(i, Ai[j + 1])))

if nx.is_directed_acyclic_graph(G):
    print(nx.dag_longest_path_length(G) + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# 休憩review
# League
from collections import deque
N = int(input())
G = [[] for i in range(N**2+1)]
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(1, N-1):
        _from, _to = a[j-1], a[j]
        G[N*min(i+1, _from)-N+max(i+1, _from)
          ].append(N*min(i+1, _to)-N+max(i+1, _to))


In = [0 for i in range(N**2+1)]  # In[node] = node に入る入次数
for i in range(1, N**2+1):
    for node in G[i]:
        In[node] += 1


stack = deque()
for i in range(1, N**2+1):
    if In[i] == 0:
        stack.append(i)  # stack := 入次数が0になった点を入れておく


Removed = [False for i in range(N**2+1)]  # 考慮されたか
cnt = [1 for i in range(N**2+1)]


while stack:
    x = stack.popleft()
    Removed[x] = True
    for node in G[x]:
        In[node] -= 1
        if In[node] == 0:
            cnt[node] += cnt[x]
            stack.append(node)


all_checked = all(Removed[node] == True for node in range(1, N**2+1))
if all_checked:
    answer = max(cnt)
    print(answer)
    exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        a = list(map(int, readline().split()))
        for j in range(n - 2):
            y = a[j]
            z = a[j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


if __name__ == '__main__':
    main()