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())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1:
            #交代できる時
            if not (visited[i] or visited[K-1]):
                if not (finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True
                    else:
                      	now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True
                    else:
                        now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1

judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1:
            #交代できる時
            if not (visited[i] or visited[K-1]):
                if not (finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True
                    else:
                      	now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True
                    else:
                        now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1

judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict,deque
n = inn()
pr = [[ [] for i in range(n+1) ] for j in range(n+1)]
ch = [[ [] for i in range(n+1) ] for j in range(n+1)]
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        ch[x1][y1].append((x2,y2))
        pr[x2][y2].append((x1,y1))
g = {}
q = []
for i in range(1,n):
    for j in range(i+1,n+1):
        if len(pr[i][j])==0:
            q.append((i,j))
            g[(i,j)] = 1
        else:
            g[(i,j)] = 0
ddprint(ch)
ddprint("pr")
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.pop()
    i,j = z
    for y in ch[i][j]:
        g[y] = max(g[y], g[z]+1)
        #ddprint("y {} z {}".format(y,z))
        pr[y[0]][y[1]].remove(z)
        if len(pr[y[0]][y[1]])==0:
            #del pr[y]
            q.append(y)
if min(g.values())==0:
    print(-1)
else:
    print(max(g.values()))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict,deque
n = inn()
pr = {}
ch = {}
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        if (x1,y1) in ch:
            ch[(x1,y1)].append((x2,y2))
        else:
            ch[(x1,y1)] = [(x2,y2)]
        if (x2,y2) in pr:
            pr[(x2,y2)].append((x1,y1))
        else:
            pr[(x2,y2)] = [(x1,y1)]
g = {}
q = []
for i in range(1,n):
    for j in range(i+1,n+1):
        if (i,j) not in pr:
            q.append((i,j))
            g[(i,j)] = 1
        else:
            g[(i,j)] = 0
ddprint(ch)
ddprint("pr")
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.pop()
    if z in ch:
      for y in ch[z]:
        g[y] = max(g[y], g[z]+1)
        #ddprint("y {} z {}".format(y,z))
        pr[y].remove(z)
        if len(pr[y])==0:
            #del pr[y]
            q.append(y)
if min(g.values())==0:
    print(-1)
else:
    print(max(g.values()))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from collections import defaultdict,deque
n = inn()
pr = defaultdict(list)
ch = defaultdict(list)
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        ch[(x1,y1)].append((x2,y2))
        pr[(x2,y2)].append((x1,y1))
g = {}
q = deque([])
for i in range(1,n):
    for j in range(i+1,n+1):
        if (i,j) not in pr:
            q.append((i,j))
            g[(i,j)] = 1
        else:
            g[(i,j)] = 0
ddprint(ch)
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.popleft()
    for y in ch[z]:
        g[y] = max(g[y], g[z]+1)
        pr[y].remove(z)
        if len(pr[y])==0:
            del pr[y]
            q.append(y)
if min(g.values())==0:
    print(-1)
else:
    print(max(g.values()))

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 = defaultdict(int)
    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を返す
            dp[v] = max(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 examF():
    ans = 0
    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__':
    examE()

"""

"""

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 = defaultdict(int)
    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を返す
            dp[v] = max(dp[v], res + 1)
        calculated[v] = True
        return dp[v]

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

def examF():
    ans = 0
    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__':
    examE()

"""

"""

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)]
    A = [LI() for _ in range(N)]
    D = defaultdict(int)
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[(i,j)] = cur
            D[(j,i)] = cur
            cur += 1
    for i in range(N):
        a = A[i]
        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を返す
            dp[v] = max(dp[v], res + 1)
        calculated[v] = True
        return dp[v]

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

def examF():
    ans = 0
    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__':
    examE()

"""

"""

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)]
    A = [LI() for _ in range(N)]
    D = defaultdict(int)
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[(i,j)] = cur
            D[(j,i)] = cur
            cur += 1
    ins = [0]*node
    for i in range(N):
        a = A[i]
        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)
            ins[to] += 1

    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を返す
            dp[v] = max(dp[v], res + 1)
        calculated[v] = True
        return dp[v]

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

def examF():
    ans = 0
    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__':
    examE()

"""

"""

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)]
    A = [LI() for _ in range(N)]
    D = defaultdict(int)
    cur = 0
    for i in range(N):
        for j in range(i+1,N):
            D[(i,j)] = cur
            D[(j,i)] = cur
            cur += 1
    ins = [0]*node
    for i in range(N):
        a = A[i]
        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)
            ins[to] += 1

    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を返す
            dp[v] = max(dp[v], res + 1)
        calculated[v] = True
        return dp[v]

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

def examF():
    ans = 0
    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)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
An = []
for n in range(N):
  An.append(list(map(int, input().split())))

Bn = [0 for _ in range(N)]
Dn = [0 for _ in range(N)]

fail = False
for n in range(N * (N - 1)//2):
  for i in range(N):
    if Bn[i] >= N -1:
      continue
    j = An[i][Bn[i]]  -1
    if Bn[j] >= N -1:
      continue
    ii = An[j][Bn[j]] - 1 
    if  i == ii :
      Bn[i] += 1
      Bn[j] += 1
      day = max(Dn[i], Dn[j]) + 1
      Dn[i] = day
      Dn[j] = day
      break
  if i == N -1:
    fail =True
    break
if fail:
  print(-1)
else:
  print(max(Dn))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
N = int(input())
dic = defaultdict(list)
toNum = {}
L = N*(N-1)//2
s = [0]
for i in range(N-1,0,-1):
  s += [s[-1]+i]
dist = [0]*L
for i in range(N):
  inf = [int(c)-1 for c in input().split()]
  pa = min(i,inf[0])
  pb = max(i,inf[0])
  pnum = s[pa]+(pb-pa-1)
  for j in range(1,N-1):
    a = min(i,inf[j])
    b = max(i,inf[j])
    num = s[a]+(b-a-1)
    dic[pnum]  += [num]
    dist[num] += 1
    pa = a
    pb = b
    pnum = num

hq = []
for i in range(L):
  if dist[i]==0:
    heappush(hq,(1,i))
  dist[i] = 0
if hq==[]:
  print(-1)
  import sys
  sys.exit()
cnt = 0
ans = 0
while hq:
  c, n = heappop(hq)
  if dist[n]>=c:
    continue
  dist[n] = c
  cnt += 1
  for m in dic[n]:
    if dist[m]>=c+1:
      continue
    if ans<c+1:
      ans = c+1
    heappush(hq,(c+1,m))
  if ans>L:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
N = int(input())
dic = defaultdict(list)
toNum = {}
L = N*(N-1)//2
s = [0]
for i in range(N-1,0,-1):
  s += [s[-1]+i]
used = [True]*L
for i in range(N):
  inf = [int(c)-1 for c in input().split()]
  pa = min(i,inf[0])
  pb = max(i,inf[0])
  pnum = s[pa]+(pb-pa-1)
  for j in range(1,N-1):
    a = min(i,inf[j])
    b = max(i,inf[j])
    num = s[a]+(b-a-1)
    used[num] = False
    dic[pnum]  += [num]
    pa = a
    pb = b
    pnum = num

hq = []
dist = [0]*L
for i in range(L):
  if used[i]:
    heappush(hq,(1,i))
if hq==[]:
  print(-1)
  import sys
  sys.exit()
cnt = 0
ans = 0
while hq:
  c, n = heappop(hq)
  if dist[n]>=c:
    continue
  dist[n] = c
  cnt += 1
  for m in dic[n]:
    if dist[m]>=c+1:
      continue
    if ans<c+1:
      ans = c+1
    heappush(hq,(c+1,m))
  if ans>L:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
N = int(input())
dic = defaultdict(list)
toNum = {}
cnt = 0
L = N*(N-1)//2
for i in range(N):
  for j in range(i+1,N):
    toNum[(i,j)] = cnt
    cnt += 1
used = [True]*L
for i in range(N):
  inf = [int(c)-1 for c in input().split()]
  pa = min(i,inf[0])
  pb = max(i,inf[0])
  pnum = toNum[(pa,pb)]
  for j in range(1,N-1):
    a = min(i,inf[j])
    b = max(i,inf[j])
    num = toNum[(a,b)]
    used[num] = False
    dic[pnum]  += [num]
    pa = a
    pb = b
    pnum = num

hq = []
dist = [0]*L
for i in range(L):
  if used[i]:
    heappush(hq,(1,i))
if hq==[]:
  print(-1)
  import sys
  sys.exit()
cnt = 0
ans = 0
while hq:
  c, n = heappop(hq)
  if dist[n]>=c:
    continue
  dist[n] = c
  cnt += 1
  for m in dic[n]:
    if dist[m]>=c+1:
      continue
    if ans<c+1:
      ans = c+1
    heappush(hq,(c+1,m))
  if ans>L:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

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

id = [0]*N
Lock = [-1]*N
ans = 0
flag = [True]*N
min_id = 0
while(min_id < N-1):
    ans += 1
    if ans > (N*(N-1)) // 2:
        break
    tmp = set()
    for i in range(N):
        if id[i] >= N-1:
            continue
        else:
            if Lock[i] >= 0:
                continue
            else:
                if Lock[A[i][id[i]]-1] == i and i not in tmp:
                    Lock[A[i][id[i]]-1] = -1
                    id[A[i][id[i]]-1] += 1
                    tmp.add(A[i][id[i]]-1)
                    id[i] += 1
                else:
                    if i not in tmp:
                        Lock[i] = A[i][id[i]]-1
    min_id = min(id)
if ans > (N*(N-1)) // 2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

id = [0]*N
Lock = [-1]*N
ans = 0
flag = [True]*N
min_id = 0
while(min_id < N-1):
    ans += 1
    if ans > N**2:
        break
    tmp = set()
    for i in range(N):
        if id[i] >= N-1:
            continue
        else:
            if Lock[i] >= 0:
                continue
            else:
                if Lock[A[i][id[i]]-1] == i and i not in tmp:
                    Lock[A[i][id[i]]-1] = -1
                    id[A[i][id[i]]-1] += 1
                    tmp.add(A[i][id[i]]-1)
                    id[i] += 1
                else:
                    if i not in tmp:
                        Lock[i] = A[i][id[i]]-1
    min_id = min(id)
if ans > N**2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

id = [0]*N
Lock = [-1]*N
ans = 0
flag = [True]*N
while(min(id) < N-1):
    ans += 1
    if ans > N**2:
        break

    tmp = set()
    for i in range(N):
        if id[i] >= N-1:
            continue
        else:
            if Lock[i] >= 0:
                continue
            else:
                if Lock[A[i][id[i]]-1] == i and i not in tmp:
                    Lock[A[i][id[i]]-1] = -1
                    id[A[i][id[i]]-1] += 1
                    tmp.add(A[i][id[i]]-1)
                    id[i] += 1
                else:
                    if i not in tmp:
                        Lock[i] = A[i][id[i]]-1
if ans > N**2:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []

from collections import deque

# わかりやすくindexを1から始めるように、ダミー要素追加
A.append(deque([0]))

for i in range(N):
  tmp_a = deque(map(int, input().split()))
  A.append(tmp_a)

#print(A)

from copy import deepcopy
matchtable = deepcopy(A)
finished = [deque([0]) for i in range(N+1)]
days = 0
success = False
before = []

while before != matchtable:
  # 日付
  days += 1
  #print('day',days)

  # 試行前の状態をとっておく
  before = deepcopy(matchtable)

  # ペアリング試行
  for i in range(1, N+1):
    aite = matchtable[i][0]
    if aite == 0: continue

    if matchtable[aite][0] == i:
      # ペア成立 --> 0に置き換える
      #print('ペア成立 {} - {}'.format(i,aite))
      matchtable[i][0] = 0
      matchtable[aite][0] = 0

  # 成立した試合を消化する(0を詰める)
  for i in range(1,N+1):
    if matchtable[i][0] == 0 and len(matchtable[i]) > 1:
      matchtable[i].popleft()

  # 確認用
  #print(matchtable)

  # 0ベクトルならすべて消化
  if matchtable == finished:
    success = True
    break

  # ここで matchtable == before なら、これ以上の組み合わせは無理なので break
  # while の条件に入れてある


if success:
  print(days)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
l = [deque([])]+[deque(map(int, input().split())) for _ in range(N)]

v = 0
ans = 0
t = N*(N-1)//2

while v<t and ans<t:
    used = set()
    for n in range(1, N+1):
        if n in used:continue
        if not l[n]:continue
        pair = l[n][0]
        b = l[pair][0]
        if pair in used:continue

        if b==n:
            l[n].popleft()
            l[pair].popleft()
            used|={n,pair}
            v += 1
    ans += 1

if ans==t and ans!=v:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import copy

input = sys.stdin.readline


def main():
    N = int(input())
    A = [collections.deque([int(x) for x in input().split()]) for _ in range(N)]

    day = 0
    c = 0
    nxt = [A[x][0] for x in range(N)]
    for i in range(N):
        A[i].popleft()

    while c != N * (N - 1):
        day += 1

        nxt2 = copy.copy(nxt)
        tmp = set()
        for i in set(nxt):
            if i == -1 or i in tmp:
                continue
            if i == nxt[nxt[i - 1] - 1]:
                if A[i - 1]:
                    nxt2[i - 1] = A[i - 1].popleft()
                else:
                    nxt2[i - 1] = -1
                if A[nxt[i - 1] - 1]:
                    nxt2[nxt[i - 1] - 1] = A[nxt[i - 1] - 1].popleft()
                else:
                    nxt2[nxt[i - 1] - 1] = -1
                tmp.add(i)
                tmp.add(nxt[i - 1])
                c += 2
        if not tmp:
            print(-1)
            return

        nxt = copy.copy(nxt2)

    print(day)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

input = sys.stdin.readline


def main():
    N = int(input())
    A = [collections.deque([int(x) for x in input().split()]) for _ in range(N)]

    day = 0
    c = 0
    while c != N * (N - 1):
        day += 1
        f = False
        for i in range(N):
            x = float("inf")

            if A[i]:
                x = A[i][0]
                if 0 > x > -day:
                    A[i].popleft()
                    if A[i]:
                        x = A[i][0]
                    else:
                        x = float("inf")

            if x == -day or x == float("inf"):
                continue
            if A[x - 1][0] and 0 > A[x - 1][0] > -day:
                A[x - 1].popleft()
            if A[x - 1] and A[x - 1][0] == i + 1:
                c += 2
                A[i][0] = -day
                A[x - 1][0] = -day
                f = True
        if not f:
            print(-1)
            return

    print(day)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

G = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
    edge[i] = G[i][cur[i]]

day = 0
player = set(range(N))
while len(player) > 0:
    day += 1
    game = []
    for i in player:
        if i == edge[edge[i]]:
            game.append(i)
    if len(game) == 0:
        print(-1)
        exit()
    else:
        for j in game:
            cur[j] += 1
            c = cur[j]
            if c >= N - 1:
                player.remove(j)
            else:
                edge[j] = G[j][c]

print(day)

Submission status: Time Limit Exceeded

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


def dfs(n, pn):
    nn = edge[n]
    if nn == pn:
        game.append(n)
        game.append(pn)
    elif track[nn] == 0:
        track[nn] = 1
        dfs(nn, n)


N = int(input())

G = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
cur = [0] * N
edge = [0] * N
for i in range(N):
    edge[i] = G[i][cur[i]]

day = 0
cnt = 0
while cnt < N:
    day += 1
    track = [0] * N
    game = []
    for i in range(N):
        if track[i] == 0:
            track[i] = 1
            dfs(i, -1)
    if len(game) == 0:
        print(-1)
        exit()
    else:
        for j in game:
            cur[j] += 1
            c = cur[j]
            if c >= N - 1:
                edge[j] = j
                cnt += 1
            else:
                edge[j] = G[j][c]

print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

stdin = sys.stdin

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

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

print(answer)