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:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


N = int(input())
A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

node_id_db = [[0] * (N+1) for _ in range(N + 1)]
v = 0
for i in range(N):
    for j in range(i + 1, N):
        node_id_db[i][j] = v
        v += 1

start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
    Ai = A[i]
    from_id = get_node_id(i, Ai[0], node_id_db)
    if i < Ai[0]:
        start_nodes.append(from_id)
    for j in range(1, N - 1):
        to_id = get_node_id(i, Ai[j], node_id_db)
        edges[from_id].append(to_id)
        from_id = to_id

dp = [-1 for _ in range(N * (N - 1) // 2)]
print(max(dfs(n, edges) for n in start_nodes))

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

N = int(input())
A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

node_id_db = [[0] * (N+1) for _ in range(N + 1)]
v = 0
for i in range(N):
    for j in range(i + 1, N):
        node_id_db[i][j] = v
        v += 1


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
    Ai = A[i]
    from_id = get_node_id(i, Ai[0], node_id_db)
    if i < Ai[0]:
        start_nodes.append(from_id)
    for j in range(1, N - 1):
        to_id = get_node_id(i, Ai[j], node_id_db)
        edges[from_id].append(to_id)
        from_id = to_id

dp = [-1 for _ in range(N * (N - 1) // 2)]


def dfs(node_id):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


print(max(dfs(n) for n in start_nodes))

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 1
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    t = max(t, res + 1)
  dp[v] = t
  return t

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

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

  id = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, visited, calculated, dp, to):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u, visited, calculated, dp, to)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

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

  id = [[0] * N for _ in range(N)]

  visited = [False] * (N * (N - 1) // 2)
  calculated = [False] * (N * (N - 1) // 2)
  dp = [0] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  ans = 0
  for i in range(N * (N - 1) // 2):
    res = dfs(i, visited, calculated, dp, to)
    if res == -1:
      print('-1')
      exit()
    ans = max(ans, res)
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[0]*n]*n
l=[]
s=set()

for i in range(n):
  a[i]=[int(x)-1 for x in input().split()]
l=[int(i) for i in range(n)]

t=0
f=True
while f==True:
  f=False
  s.clear()
  for i in l:
    if len(a[i])==0:
      continue
    f=True
    j=a[i][0]

    if i==a[j][0]:
      s.add(i)
      s.add(j)
  if f==False:
    break

  l = list(s)
  s.clear()
  if len(l)!=0:
    t+=1
    for i in range(len(l)):
      a[l[i]].pop(0)
      s.add(l[i])
      if len(a[l[i]])>0:
        s.add(a[l[i]][0])
  else:
    t = -1
    break
  l=list(s)

print(t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[0]*n]*n
l=[]

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

t=0
f=True
while f==True:
  f=False
  for i in range(n):
    if len(a[i])>0:
      f=True
      j=a[i][0]
      if i<j:
        if i==a[j][0]:
          l.append(i)
          l.append(j)

  if f==False:
    break

  t = t+1 if len(l)>0 else -1
  if len(l)==0:
    break;
  for i in range(len(l)):
    a[l.pop(0)].pop(0)

print(t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[0]*n]*n
l=[]

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

t=0
f=True
while f==True:
  f=False
  for i in range(n):
    if len(a[i])==0:
      continue
    f=True
    j=a[i][0]
    if i<j:
      if i==a[j][0]:
        l.append(i)
        l.append(j)

  if f==False:
    break

  if len(l)!=0:
    t+=1
    for i in range(len(l)):
      a[l.pop(0)].pop(0)
  else:
    t = -1
    break
print(t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[0]*n]*n
l=[]

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

t=0
f=True
while f==True:
  f=False
  for i in range(n):
    if len(a[i])==0:
      continue
    f=True
    if i==a[a[i][0]][0]:
      if i<a[i][0]:
        l.append(i)
        l.append(a[i][0])

  if f==False:
    break

  if len(l)!=0:
    t+=1
    for i in range(len(l)):
      a[l.pop(0)].pop(0)
  else:
    t = -1
    break
print(t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[0]*n]*n
s=set()

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

t=0
f=True
while f==True:
  f=False
  s.clear()
  for i in range(n):
    if len(a[i])==0:
      continue
    f=True
    if i==a[a[i][0]][0]:
      s.add(i)
      s.add(a[i][0])

  if f==False:
    break

  if len(s)!=0:
    t+=1
    l = list(s)
    for i in range(len(l)):
      a[l[i]].pop(0)
  else:
    t = -1
    break
print(t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[0]*n]*n
s=set()

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

t=0
f=True
while f==True:
  f=False
  s.clear()
  for i in range(n):
    if len(a[i])==0:
      continue
    f=True
    if len(a[a[i][0]])==0:
      continue
    if i==a[a[i][0]][0]:
      s.add(i)
      s.add(a[i][0])

  if f==False:
    break

  if len(s)!=0:
    t+=1
    l = list(s)
    for i in range(len(l)):
      a[l[i]].pop(0)
  else:
    t = -1
    break
print(t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[0]*n]*n
l=[]

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

t=0
f=True
while f==True:
  f=False
  for i in range(n):
    if len(a[i])==0:
      continue
    f=True
    if len(a[a[i][0]])==0:
      continue
    if i==a[a[i][0]][0]:
      if not(i in l):
        l.append(i)
      if not(a[i][0] in l):
        l.append(a[i][0])

  if f==False:
    break

  if len(l)!=0:
    t+=1
    while len(l)!=0:
      a[l.pop(0)].pop(0)
      a[l.pop(0)].pop(0)
  else:
    t = -1
    break
print(t)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np


N=int(input())
A=np.array([list(map(int,input().split())) for _ in range(N)])

ans=0

C=np.array([0]*N)
update = True

while update:
  H=[]
  update = False
  for i in range(N):
    if C[i] < N-1:
      r = A[i][C[i]]-1
      if (C[r] < N-1) and (i+1==A[r][C[r]]) and not(r in H) and not(i in H):
        H.append(r)
        H.append(i)
        C[r] += 1
        C[i] += 1
        update = True
  ans += 1

for i in range(N):
  if C[i] < N-1:
    ans=0

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:

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

ans=0

C=[0]*N
update = True

while update:
  H={}
  update = False
  for i in range(N):
    if C[i] < N-1:
      r = A[i][C[i]]-1
      if (C[r] < N-1) and (i+1==A[r][C[r]]) and not(r in H) and not(i in H):
        H[r] = True
        H[i] = True
        C[r] += 1
        C[i] += 1
        update = True
  ans += 1

for i in range(N):
  if C[i] < N-1:
    ans=0

print(ans-1)

Submission status: Time Limit Exceeded

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

ans=0

C=[0]*N
update = True

while update:
  H=[]
  update = False
  for i in range(N):
    if C[i] < N-1:
      r = A[i][C[i]]-1
      if (C[r] < N-1) and (i+1==A[r][C[r]]) and not(r in H) and not(i in H):
        H.append(r)
        H.append(i)
        C[r] += 1
        C[i] += 1
        update = True
  ans += 1

for i in range(N):
  if C[i] < N-1:
    ans=0

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:

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

ans=0

C=[0]*N
update = True

while update:
  H=[]
  update = False
  for i in range(N):
    if C[i] < N-1:
      r = A[i][C[i]]-1
      if (C[r] < N-1) and (i+1==A[r][C[r]]) and not(r in H) and not(i in H):
        H.append(r)
        H.append(i)
        C[r] += 1
        C[i] += 1
        update = True
  ans += 1

for i in range(N):
  if C[i] < N-1:
    ans=0

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
A=list(map(lambda x: deque(x), A))
#print(A)

ans=0

L=[]
for i in range(N):
  L.append(len(A[i]))
#print(L)

while 1:
  P=[0]*N
  sw=0
  C=[]
  for i in range(N):
    if L[i]:
      if i+1==A[A[i][0]-1][0]:
        P[i]=1
        C.append(i)
        sw=1
  #print(P)
  if sw:
    for c in C:
      if P[c]:
        A[c].popleft()
        L[c]-=1
    ans+=1
  else:
    tmp=0
    for a in A:
      tmp+=len(a)
    if tmp!=0:
      ans=-1
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
A=list(map(lambda x: deque(x), A))
#print(A)

ans=0

L=[]
for i in range(N):
  L.append(len(A[i]))
#print(L)

while 1:
  P=[0]*N
  sw=0
  for i in range(N):
    if L[i]:
      if i+1==A[A[i][0]-1][0]:
        P[i]=1
        sw=1
  #print(P)
  if sw:
    for i in range(N):
      if P[i]:
        A[i].popleft()
        L[i]-=1
    ans+=1
  else:
    tmp=0
    for a in A:
      tmp+=len(a)
    if tmp!=0:
      ans=-1
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
A=list(map(lambda x: deque(x), A))
#print(A)

ans=0
while 1:
  P=[0]*N
  for i in range(N):
    if len(A[i]):
      if i+1==A[A[i][0]-1][0]:
        P[i]=1
  #print(P)
  if sum(P):
    for i in range(N):
      if P[i]:
        A[i].popleft()
    ans+=1
  else:
    tmp=0
    for a in A:
      tmp+=len(a)
    if tmp!=0:
      ans=-1
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

edges = defaultdict(lambda: [])
used = [False for _ in range(1001000)]
d = [1 for _ in range(1001000)]


def dfs(i):
    if used[i]:
        return d[i]
    else:
        used[i] = True
        ret = 0
        for v in edges[i]:
            tmp = dfs(v)
            if ret < tmp+1:
                ret = tmp+1
        d[i] = ret
        return ret


def main():
    n = int(input())
    h = [0 for _ in range(1001000)]
    for i in range(n):
        a = list(map(int, input().split()))
        for j in range(1, n-1):
            pa = a[j-1]-1
            na = a[j]-1
            pi = i
            ni = i
            if na > ni:
                na, ni = ni, na
            if pa > pi:
                pa, pi = pi, pa
            edges[1000*pi + pa].append(1000*ni + na)
            h[1000*ni + na] += 1
    
    stack = []
    for k, _ in edges.items():
        if h[k] == 0:
            stack.append(k)
    
    ans = 0
    while len(stack):
        u = stack.pop()
        for v in edges[u]:
            h[v] -= 1
            if h[v] == 0:
                stack.append(v)
        ans += 1

    if ans != n*(n-1)//2:
        print(-1)
    else:
        ret = 0
        for k, _ in edges.items():
            tmp = dfs(k)
            if tmp > ret:
                ret = tmp
        print(ret+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
N = int(input())
es = [[] for i in range(N*(N-1)//2)]
se = [[] for i in range(N*(N-1)//2)]
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = -1
  while q:
    p = q.popleft()
    res = p
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
end = TP_sort(es, ins, start)
if end==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(end)+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

Submission status: Time Limit Exceeded

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

day = 0
match = 0
while match<N*(N-1)//2:
    checkes = [False]*N
    check = False
    for n in range(N):
        jibun = n
        jibun_ind = indexes[jibun]
        if jibun_ind>=N-1:
            continue
        aite = A[jibun][jibun_ind] - 1
        aite_ind = indexes[aite]
        aite_no_aite = A[aite][aite_ind] - 1
        
        if checkes[jibun] or checkes[aite]:
            continue
        if jibun == aite_no_aite:
            checkes[jibun] = True
            checkes[aite] = True
            indexes[jibun] += 1
            indexes[aite] += 1
            match += 1
            check = True
    if not check:
        day = -1
        break
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque
from heapq import heappush,heappop,heapify

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))

q=deque()

for x,y in BEGIN:
	if IN[(x,y)]==0:
		q.append((x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
cnt=0
while q:
	fro=q.popleft()
	cnt+=1
	for to in AL[fro]:
		IN[to]-=1
		DAY[to]=max(DAY[to],DAY[fro]+1)
		if IN[to]==0:
			q.append((to[0],to[1]))

if cnt==N*(N-1)/2:
	print max(DAY.values())
else:
	print -1

Submission status: Time Limit Exceeded

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

day = 0
match = 0
while match<N*(N-1)//2:
    checkes = [False]*N
    check = False
    for n in range(N):
        jibun = n
        jibun_ind = indexes[jibun]
        if jibun_ind>=N-1:
            continue
        aite = A[jibun][jibun_ind] - 1
        aite_ind = indexes[aite]
        aite_no_aite = A[aite][aite_ind] - 1

        if not checkes[jibun] and not checkes[aite] and jibun == aite_no_aite:
            checkes[jibun] = True
            checkes[aite] = True
            indexes[jibun] += 1
            indexes[aite] += 1
            match += 1
            check = True
    if not check:
        day = -1
        break
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

day = 0
match = 0
while match!=N*(N-1)//2:
    checkes = [False for i in range(N)]
    check = False
    for n in range(N):
        jibun = n
        jibun_ind = indexes[jibun]
        if jibun_ind>=N-1:
            continue
        aite = A[jibun][jibun_ind] - 1
        aite_ind = indexes[aite]
        aite_no_aite = A[aite][aite_ind] - 1

        if not checkes[jibun] and not checkes[aite] and jibun == aite_no_aite:
            checkes[jibun] = True
            checkes[aite] = True
            indexes[jibun] += 1
            indexes[aite] += 1
            match += 1
            check = True
    if not check:
        day = -1
        break
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
indexes = [0 for i in range(N)]

day = 0
match = 0
while match!=N*(N-1)//2:
    checkes = [False] * N
    check = False
    for n in range(N):
        jibun = n
        jibun_ind = indexes[jibun]
        if jibun_ind>=N-1:
            continue
        aite = A[jibun][jibun_ind] - 1
        aite_ind = indexes[aite]
        aite_no_aite = A[aite][aite_ind] - 1

        if not checkes[jibun] and not checkes[aite] and jibun == aite_no_aite:
            checkes[jibun] = True
            checkes[aite] = True
            indexes[jibun] += 1
            indexes[aite] += 1
            match += 1
            check = True
    if not check:
        day = -1
        break
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

day = 0
match = 0
while match!=N*(N-1)//2:
    checkes = [False for i in range(N)]
    check = False
    for n in range(N):
        jibun = n
        jibun_ind = indexes[jibun]
        if jibun_ind>=N-1:
            continue
        aite = A[jibun][jibun_ind] - 1
        aite_ind = indexes[aite]
        aite_no_aite = A[aite][aite_ind] - 1

        if not checkes[jibun] and not checkes[aite] and jibun == aite_no_aite:
            checkes[jibun] = True
            checkes[aite] = True
            indexes[jibun] += 1
            indexes[aite] += 1
            match += 1
            check = True
    if not check:
        day = -1
        break
    day += 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque
from heapq import heappush,heappop,heapify

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))

hq=[]

for x,y in BEGIN:
	if IN[(x,y)]==0:
		heappush(hq, (0,x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
while hq:
	cost,fro_x,fro_y=heappop(hq)
	fro=(fro_x,fro_y)
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			heappush(hq,(alt,to[0],to[1]))

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))


q=deque()

for x,y in BEGIN:
	if IN[(x,y)]==0:
		q.append((x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
cnt=0
#while q and cnt<100000:
while q:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			q.append((to[0],to[1]))
	cnt+=1

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))

DAY=defaultdict(lambda: 1)	#距離

ans=-1
while q:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			q.append((to[0],to[1]))

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))

DAY=defaultdict(lambda: 1)	#距離

ans=-1
while q:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=max(DAY[to],DAY[fro]+1)
			q.append((to[0],to[1]))

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))


DAY=defaultdict(lambda: 1)	#距離
Visit=defaultdict(lambda: None)

while q:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			DAY[to]=max(DAY[to],DAY[fro]+1)
			q.append((to[0],to[1]))

try:
	print max(DAY.values())
except:
	print -1