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 collections import deque
N = int(input())
G = {}
for i in range(1,N+1):
    a = list(map(int,input().split()))
    i1 = i
    i2 = a[0]
    if i1>i2:
        i1,i2 = i2,i1
    if (i1,i2) not in G:
        G[(i1,i2)] = [0,[]]
    for j in range(1,N-1):
        i1 = i
        i2 = a[j-1]
        i3 = i
        i4 = a[j]
        if i1>i2:
            i1,i2 = i2,i1
        if i3>i4:
            i3,i4 = i4,i3
        G[(i1,i2)][1].append((i3,i4))
        if (i3,i4) not in G:
            G[(i3,i4)] = [0,[]]
        G[(i3,i4)][0] += 1
que = deque([])
hist = {}
for a in G:
    hist[a] = 0
flag = 0
for a in G:
    if G[a][0]==0:
        hist[a] = 1
        que.append((a,1))
if len(que)==0:
    flag = 1
if flag==0:
    cnt = 0
    while que:
        a,d = que.popleft()
        for b in G[a][1]:
            G[b][0] -= 1
            if G[b][0]==0:
                que.append((b,d+1))
                cnt = d+1
                hist[b] = 1
for a in hist:
    if hist[a]==0:
        flag=1
        break
if flag==1:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import deque


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = deque(input_int_list())
    day = 0
    matches = 0
    while True:
        played = set()
        for a, v in d.items():
            if d[a] and a not in played:
                b = d[a][0]
                if d[b] and a == d[b][0] and b not in played:
                    d[a].popleft()
                    d[b].popleft()
                    played.add(a)
                    played.add(b)
                    matches += 1
        if not played:
            break
        day += 1

    if matches == (n * (n - 1)) // 2:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = input_int_list()[::-1]
    day = 0
    matches = 0
    while True:
        played = set()
        for a, v in d.items():
            if d[a] and a not in played:
                b = d[a][-1]
                if d[b] and a == d[b][-1] and b not in played:
                    d[a].pop()
                    d[b].pop()
                    played.add(a)
                    played.add(b)
                    matches += 1
        if not played:
            break
        day += 1

    if matches == (n * (n - 1)) // 2:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
G = {}
for i in range(1,N+1):
    a = list(map(int,input().split()))
    i1 = i
    i2 = a[0]
    if i1>i2:
        i1,i2 = i2,i1
    if (i1,i2) not in G:
        G[(i1,i2)] = [0,[]]
    for j in range(1,N-1):
        i1 = i
        i2 = a[j-1]
        i3 = i
        i4 = a[j]
        if i1>i2:
            i1,i2 = i2,i1
        if i3>i4:
            i3,i4 = i4,i3
        G[(i1,i2)][1].append((i3,i4))
        if (i3,i4) not in G:
            G[(i3,i4)] = [0,[]]
        G[(i3,i4)][0] += 1
que = deque([])
hist = {}
for a in G:
    hist[a] = 0
flag = 0
for a in G:
    if G[a][0]==0:
        que.append((a,1))
        hist[a] = 1
if len(que)==0:
    flag = 1
if flag==0:
    cnt = 0
    while que:
        a,d = que.popleft()
        for b in G[a][1]:
            G[b][0] -= 1
            if G[b][0]==0:
                que.append((b,d+1))
                cnt = d+1
                hist[b] = 1
    for a in hist:
        if hist[a]==0:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = input_int_list()[::-1]
    day = 0
    matches = 0
    while True:
        played = set()
        for a, v in d.items():
            if d[a]:
                b = d[a][-1]
                if d[b] and a == d[b][-1] and a not in played and b not in played:
                    d[a].pop()
                    d[b].pop()
                    played.add(a)
                    played.add(b)
                    matches += 1
        if not played:
            break
        day += 1

    if matches == (n * (n - 1)) // 2:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    idx = [0] * N
    d = 0
    while True:
        c = [False] * N
        for i in range(N):
            if idx[i] >= N - 1: continue
            if c[i]: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                c[i] = True
                c[m] = True
        f = False
        for i in range(N):
            if c[i]:
                idx[i] += 1
                f = True
        if not f:
            print(-1)
            return
        d += 1
        if all([idx[i] >= N - 1 for i in range(N)]):
            print(d)
            return

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, A)

Submission status: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
sys.setrecursionlimit(10**6)

n = ni()
def idx(u,v):
    return u*n+v
tree = [[] for i in range(n**2)]
go=[False]*n**2
back=[False]*n**2
memo = [1]*n**2 #memo[i] iからの深さ
start = []
for i in range(n):
    A1 = lma()
    pu,pv = i,A1[0]-1
    if pu>pv:pu,pv=pv,pu
    start.append(idx(pu,pv))
    for j in range(1,n-1):
        u,v = i,A1[j]-1
        if u>v:u,v=v,u
        tree[idx(pu,pv)].append(idx(u,v))
        pu,pv=u,v
        start.append(idx(pu,pv))
#print(tree)
def dfs(s):
    go[s]=True
    for node in tree[s]:
        if not go[node]:
            memo[s] = max(dfs(node)+1,memo[s])
        else:
            if back[node]:
                memo[s] = max(memo[node]+1,memo[s])
            else:
                print(-1)
                exit()
    back[s]=True
    return memo[s]
ans = 0
for s in start:
    if not go[s]:
        ans = max(ans,dfs(s))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
def hash(x,y):
    x,y =min(x,y),max(x,y)
    return x*(N+1)+y
s = set()
N = int(input())
edge = [[] for _ in range(N*N+N)]
ind = [0]*(N*N+N)
for i in range(1,N+1):
    A = list(map(int,input().split()))
    s.add(hash(i,A[0]))
    for j in range(N-1):
        for k in range(j+1,N-1):
            edge[hash(i,A[j])].append(hash(i,A[k]))
            ind[hash(i,A[k])] += 1
d = deque()
nd = deque()
for hash in s:
    if ind[hash] == 0:
        d.append(hash)
ans = 0
finished = 0
while d:
    while d:
        hash = d.popleft()
        finished += 1
        for nhash in edge[hash]:
            ind[nhash] -= 1
            if ind[nhash] == 0:
                nd.append(nhash)
    d = nd
    nd = deque()
    ans += 1
if finished == N*(N-1)//2:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
def hash(x,y):
    x,y =min(x,y),max(x,y)
    return x*10000+y
edge = defaultdict(list)
ind = defaultdict(int)
s = set()
N = int(input())
for i in range(1,N+1):
    A = list(map(int,input().split()))
    s.add(hash(i,A[0]))
    for j in range(N-1):
        for k in range(j+1,N-1):
            edge[hash(i,A[j])].append(hash(i,A[k]))
            ind[hash(i,A[k])] += 1
d = deque()
nd = deque()
for hash in s:
    if ind[hash] == 0:
        d.append(hash)
ans = 0
finished = 0
while d:
    while d:
        hash = d.popleft()
        finished += 1
        for nhash in edge[hash]:
            ind[nhash] -= 1
            if ind[nhash] == 0:
                nd.append(nhash)
    d = nd
    nd = deque()
    ans += 1
if finished == N*(N-1)//2:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
edge = defaultdict(list)
ind = defaultdict(int)
s = set()
N = int(input())
for i in range(1,N+1):
    A = list(map(int,input().split()))
    s.add((min(i,A[0]),max(i,A[0])))
    for j in range(N-1):
        for k in range(j+1,N-1):
            x1 = min(i,A[j])
            y1 = max(i,A[j])
            x2 = min(i,A[k])
            y2 = max(i,A[k])
            edge[(x1,y1)].append((x2,y2))
            ind[(x2,y2)] += 1
d = deque()
nd = deque()
for x1,y1 in s:
    if ind[(x1,y1)] == 0:
        d.append((x1,y1))
ans = 0
num = 0
while d:
    while d:
        x1,y1 = d.popleft()
        num += 1
        for x2,y2 in edge[(x1,y1)]:
            ind[(x2,y2)] -= 1
            if ind[(x2,y2)] == 0:
                nd.append((x2,y2))
    d = nd
    nd = deque()
    ans += 1
if num == N*(N-1)//2:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import networkx as nx

input = sys.stdin.buffer.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):
        p, q = Ai[j], Ai[j + 1]
        G.add_edge(((i, p) if i <= p else (p, i)),
                   ((i, q) if i <= q else (q, i)))

try:
    print(nx.dag_longest_path_length(G) + 1)
except nx.NetworkXUnfeasible:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    ans = -float("inf")
    for v in ns[u]:
        if done[v]:
            ans = max(ans, vals[v]+1)
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
            ans = max(ans, vals[v]+1)
    done[u] = True
    if ans==-float("inf"):
        ans = 0
    vals[u] = ans
    return pos
ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u, -1)
    if pos>=0:
        print(-1)
        break
else:
    print(max(vals)+1)

Submission status: Time Limit Exceeded

Solution code:
#ABC139 E
N = int(input())
#3 <= N <= 1000

A = [0] * N
for i in range(N):
  A[i] = list(map(int, input().split()))
  
#print(A)  
finish = [[] for i in range(N)]  
day = 1
#一試合もできないのに、まだ全ての試合が終わっていない→ -1 を出力
T = True
while T:
  today = [0] * N
  x = 0
  for i in range(N):
    if today[i] == 0:
      today[i] = 1
      if A[i] != []:
        next_ = A[i][0]
        if (A[next_ - 1] != []) and (today[next_ - 1] == 0):
          if A[next_ - 1][0] == i + 1:
            A[i].pop(0)
            A[next_ - 1].pop(0)
            today[next_ - 1] = 1
            x = 1
          
  if A == finish:
    T = False
  if x == 0:
    T = False
    day = -1
  if T:  
    day += 1  
  #print(day, T, A)
print(day)

Submission status: Time Limit Exceeded

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
    
q=deque()
P=[0]*M
for i in range(M):
  if len(F[i])==0:
    q.append((i,0))

r=[]
while q:
  v1,cnt=q.popleft()
  r.append((v1,cnt))
  for v2 in D[v1]:
    P[v2]+=1
    if P[v2]==len(F[v2]):
      q.append((v2,cnt+1))

if len(r)!=M:
  print(-1)
else:
  print(r[-1][-1]+1)

Submission status: Time Limit Exceeded

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
ans=0
def bfs(u):
  P[u]=0
  B.append(u)
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if i in B:
        print(-1)
        exit()
      if P[v]+1>P[i]:
        P[i]=P[v]+1
        queue.append(i)
for i in range(M):
  B=[]
  if len(F[i])==0:
    bfs(i)
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

Submission status: Time Limit Exceeded

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
ans=0
def bfs(u):
  P[u]=0
  B.append(u)
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if i in B:
        ans==-1
        break
      if P[v]+1>P[i]:
        P[v]+1>P[i]
        P[i]=P[v]+1
        queue.append(i)
for i in range(M):
  B=[]
  if len(F[i])==0:
    bfs(i)
  if ans==-1:
    print(-1)
    exit()
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

Submission status: Time Limit Exceeded

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if P[v]+1>P[i]:
        P[v]+1>P[i]
        P[i]=P[v]+1
        queue.append(i)
for i in range(M):
  if len(F[i])==0:
    bfs(i)
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

Submission status: Time Limit Exceeded

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      P[i]=P[v]+1
      queue.append(i)
for i in range(M):
  if len(F[i])==0:
    bfs(i)
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      P[i]=P[v]+1
      queue.append(i)
for i in range(M):
  if len(F[i])==0:
    bfs(i)
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
import bisect as bi
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())
N=n*(n-1)//2
def ind(i,j):
    if i==0: return j-1
    return n*(i)- i*(i+1)//2 +j-i-1
G=[[] for i in range(n*(n-1)//2)]
iG=[[] for i in range(n*(n-1)//2)]
for i in range(n):
    l=list(map(int,input().split()))
    for j in range(n-2):
        a = ind( min(l[j]-1,i), max(l[j]-1,i) )
        b = ind( min(l[j+1]-1,i), max(l[j+1]-1,i))
        G[a].append(b)
        iG[b].append(a)

seen=[0]*(n*(n-1)//2)
seen[0]=1
#queue=deque([i for i in G[0]])
#seen=[0 for i in range(n)]
kaeri=[0 for i in range(n*(n-1)//2)]
hist=deque([]) #頂点の訪問履歴
pos=-1  #サイクルの1成分 -1はサイクル未発見

def dfs(x,p):  #pはxの親
    global pos #global!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    seen[x]=1
    hist.append(x)  #訪れたらhistにappend
    for to in G[x]:
        if to==p:continue  #親なら無視
        if kaeri[to]: continue
        if seen[to]==1 and kaeri[to]==0:
            pos=to
            return    #サイクルを発見したら、即すべてのdfsを終える
        #残りはseen[x]=0のみ
        dfs(to,x)
        if pos != -1:return  #帰りがけ、サイクルが検出済みなら何もしない
    hist.pop()  #stackの末尾を消す
    kaeri[x]=1
    #ループなく平和に終わったらpopできる
    return  #まあなくてもいいけどreturnは終了であることを強調

dfs(0,-1)

#print(G,iG)

if pos!=-1:print(-1);exit()

# import numpy as np
def bfs(i, inv=0):
    global iG, G
    if inv==1: G1=iG
    else: G1 = G
    dist=[-1]*N
    dist[i]=0
    queue=deque([[i,j] for j in G1[i]])
    while queue:
        now,to=queue.pop() ; #print(now,to,inv)
        #if dist[to]!=-1 : continue
        dist[to]=dist[now]+1
        for p in G1[to]:
            queue.appendleft([to,p])
        #print(dist)
    # return np.argmax(dist), np.max(dist)
    p=max(dist) ; j=dist.index(p)
    return j,p  #PyPy3 なら

v,_ = bfs(0)  #0からのdistが最大の点がv, そのdistが _(使わないと思う)
u,R= bfs(v,1)  #vからのdistが最大の点がu, 直径が R (直径を構成する端点はu,v)
#print(v,_,u,R)
print(R+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
import bisect as bi
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())
N=n*(n-1)//2
def ind(i,j):
    if i==0: return j-1
    return n*(i)- i*(i+1)//2 +j-i-1
G=[[] for i in range(n*(n-1)//2)]
iG=[[] for i in range(n*(n-1)//2)]
for i in range(n):
    l=list(map(int,input().split()))
    for j in range(n-2):
        a = ind( min(l[j]-1,i), max(l[j]-1,i) )
        b = ind( min(l[j+1]-1,i), max(l[j+1]-1,i))
        G[a].append(b)
        iG[b].append(a)

seen=[0]*(n*(n-1)//2)
seen[0]=1
#queue=deque([i for i in G[0]])
#seen=[0 for i in range(n)]
kaeri=[0 for i in range(n*(n-1)//2)]
hist=deque([]) #頂点の訪問履歴
pos=-1  #サイクルの1成分 -1はサイクル未発見

def dfs(x,p):  #pはxの親
    global pos #global!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    seen[x]=1
    hist.append(x)  #訪れたらhistにappend
    for to in G[x]:
        if to==p:continue  #親なら無視
        if kaeri[to]: continue
        if seen[to]==1 and kaeri[to]==0:
            pos=to
            return    #サイクルを発見したら、即すべてのdfsを終える
        #残りはseen[x]=0のみ
        dfs(to,x)
        if pos != -1:return  #帰りがけ、サイクルが検出済みなら何もしない
    hist.pop()  #stackの末尾を消す
    kaeri[x]=1
    #ループなく平和に終わったらpopできる
    return  #まあなくてもいいけどreturnは終了であることを強調

dfs(0,-1)

#print(G,iG)

if pos!=-1:print(-1);exit()

import numpy as np
def bfs(i, inv=0):
    global iG, G
    if inv==1: G1=iG
    else: G1 = G
    dist=[-1]*N
    dist[i]=0
    queue=deque([[i,j] for j in G1[i]])
    while queue:
        now,to=queue.pop() ; #print(now,to,inv)
        #if dist[to]!=-1 : continue
        dist[to]=dist[now]+1
        for p in G1[to]:
            queue.appendleft([to,p])
        #print(dist)
    return np.argmax(dist), np.max(dist)
    # p=max(dist) ; j=dist.index(p)
    # return p,j  #PyPy3 なら

v,_ = bfs(0)  #0からのdistが最大の点がv, そのdistが _(使わないと思う)
u,R= bfs(v,1)  #vからのdistが最大の点がu, 直径が R (直径を構成する端点はu,v)
#print(v,_,u,R)
print(R+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
lis=[[] for i in range(n*(n-1)//2)]
num=[-1]*(n**2)
cnt=-1
for x in range(n**2):
	if x//n<x%n:
		cnt+=1
		num[x]=cnt
for i in range(n):
	a=list(map(int,input().split()))
	for j in range(n-2):
		x=a[j]-1
		y=a[j+1]-1
		px=num[min(i*n+x,x*n+i)]
		py=num[min(i*n+y,y*n+i)]
		lis[px].append(py)
node_in=[0]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
	for x in lis[i]:
		node_in[x]+=1
zero=deque([])
days=[10**9]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
	if node_in[i]==0:
		zero.append(i)
		days[i]=1
while zero:
	r=zero.popleft()
	for x in lis[r]:
		node_in[x]-=1
		if node_in[x]==0:
			zero.append(x)
			days[x]=days[r]+1
if any([x==10**9 for x in days]):
	print(-1)
else:
	print(max(days))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
N = int(input())
As = [[]]
iset = [0]*(N+1)
for _ in range(N):
  As.append(list(map(int, input().split())))

cnt = 0
eset = set()
while len(eset) < N:
  cnt += 1
  fset = set()
  f = 1
  for i in range(1, N+1):
    if i not in eset and i not in fset:
      vis = As[i][iset[i]]
      if As[vis][iset[vis]] == i and vis not in fset:
        iset[i] += 1
        iset[vis] += 1
        fset.add(i)
        fset.add(vis)
        if iset[i] == N-1:
          eset.add(i)
        if iset[vis] == N-1:
          eset.add(vis)
        f = 0
  if f == 1:
    print('-1')
    exit()
      
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def binary_search(A,p):
  if A[0]<=p and p<=A[-1]:
    if p == A[bisect_left(A,p)]:
      return True
    return False
  return False
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  cnt = 0
  while cnt<N*(N-1)//2:
    lis = [[] for _ in range(N)]
    flag = False
    for i in range(N):
      if not stacks[i]:
        continue
      if lis[i] and binary_search(lis[i],stacks[i][-1]):
        stacks[stacks[i][-1]].pop(-1)
        stacks[i].pop(-1)
        cnt += 1
        flag=True
      else:
        lis[stacks[i][-1]].append(i)
    if flag==False:
      return -1
    ans += 1
  return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  cnt = 0
  while cnt<N*(N-1)//2:
    lis = [[] for _ in range(N)]
    flag = False
    for i in range(N):
      if not stacks[i]:
        continue
      if lis[i] and stacks[i][-1] in lis[i]:
        stacks[stacks[i][-1]].pop(-1)
        stacks[i].pop(-1)
        cnt += 1
        flag=True
      else:
        lis[stacks[i][-1]].append(i)
    if flag==False:
      return -1
    ans += 1
  return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
g = dict()
head = set()
for i in range(1, n+1):
    a = list(map(int, input().split()))

    j = a[0]
    p = (i, j) if i < j else (j, i)
    if not p in g:
        head.add(p)
        g[p] = []
    next_match_list = g[p]
    for j in a[1:]:
        p = (i, j) if i < j else (j, i)
        if p in head:
            head.remove(p)
        if not p in g:
            g[p] = []
        next_match_list.append(p)
        next_match_list = g[p]
if not head:
    print(-1)
    quit()

max_depth = 0
for h in head:
    stack = [(h, 1)]
    visited = set()
    path = []
    depth = 0
    while stack:
        (p, i) = stack.pop()
        while i <= depth:
            visited.remove(path.pop())
            depth -= 1
        depth = i
        max_depth = max(max_depth, depth)
        if p in visited:
            print(-1)
            quit()
        visited.add(p)
        path.append(p)
        for q in g[p]:
            stack.append((q, depth + 1))
print(max_depth)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N= int (input())
battles_set = set()
graph_dict = defaultdict(set)
visited_set = set()
caliculated_set = set()

for j in range(1,N+1):
    battles = [tuple(sorted([int(j),int(i)])) for i in input().split(" ")]
    battles_set = battles_set | set(battles)
    for k,battle in enumerate(battles,1):
        graph_dict[battle] = graph_dict[battle] | set(battles[k:])

dp=dict()

def path_long(battle:frozenset):
    if battle in visited_set:
        if battle not in caliculated_set:
            print(-1)
            exit()
        else:
            return dp[battle]
    else:
        visited_set.add(battle)
        ret = 1
        for v in graph_dict[battle]:
            ret= max(ret,path_long(v)+1)
        caliculated_set.add(battle)
        dp[battle] = ret
        return ret
# print(battles_set)
# print(graph_dict)
ans = max([path_long(battle) for battle in battles_set])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = []
    for i in range(N):
        A.append(deque(map(lambda x: int(x)-1, input().split())))
    
    ans = 0
    while True:
        match = defaultdict(lambda : -1)
        mathced = False
        cleared = True
        for i,a in enumerate(A):
            if len(a) == 0:
                continue
            cleared = False
            if match[a[0]] == i:
                A[a[0]].popleft()
                a.popleft()
                mathced = True
            else:
                match[i] = a[0]
        if not mathced:
            break
        ans += 1
    print(ans if ans > 0 and cleared else -1)




    

    ans = 0

    

    
   
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
As = [deque([])]
for _ in range(N):
  As.append(deque(list(map(int, input().split()))))

cnt = 0
eset = set()
while len(eset) < N:
  cnt += 1
  fset = set()
  f = 1
  for i in range(1, N+1):
    if len(As[i]) == 0:
      eset.add(i)
    if i not in eset and i not in fset:
      if As[As[i][0]][0] == i and As[i][0] not in fset:
        fset.add(As[As[i][0]].popleft())
        fset.add(As[i].popleft())
        if len(As[i]) == 0:
          eset.add(i)
        f = 0
  if f == 1:
    print('-1')
    exit()
      
print(cnt)

Submission status: Time Limit Exceeded

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

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
in_cnt = {k:0 for k in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = {k:1 for k in nodes}
q = [i for i in nodes if not in_cnt[i]]

if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)