Problem:


Score : 500 points

Problem Statement

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G.
G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq \min(10^5, N (N-1))

1 \leq u_i, v_i \leq N(1 \leq i \leq M)

u_i \neq v_i (1 \leq i \leq M)

If i \neq j, (u_i, v_i) \neq (u_j, v_j).

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Sample Input 1

4 4
1 2
2 3
3 4
4 1
1 3

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Sample Output 4

2



Sample input:
4 4
1 2
2 3
3 4
4 1
1 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    edge = [[] for i in range(N)]
    for i in range(M):#木の場合M=N-1
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
    S, T = map(int, input().split())
    S-=1;T-=1

    def dfs():
        q=deque([(0,S)])
        visited=[False]*N
        while len(q):
            
            d,e=q.popleft()#ここをpopleftにすると幅優先探索BFSになる
            
            if d%3==0 and visited[e]:continue
            elif d%3==0:

                if e==T:
                    print(d//3)
                    return 
                visited[e]=True
            
            for ne in edge[e]:
                q.append((d+1,ne))
        print(-1)
    dfs()
    




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    vis[now][step] = cnt
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            q.append((x,cnt+1))
if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while q:
    now,cnt = q.popleft()
    step = cnt % 3
    vis[now][step] = cnt
    if now == T and step  == 0:  
        print(cnt//3)
        exit()
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            q.append((x,cnt+1))
print(-1)
exit()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q) > 0:
    now,cnt = q.popleft()
    step = cnt % 3
    vis[now][step] = cnt
    if now == T and step  == 0:  
        print(cnt//3)
        exit()
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            q.append((x,cnt+1))
print(-1)
exit()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        step = cnt % 3
        vis[now][step] = cnt
        if now == T and step  == 0:  
            return cnt
        for x in path[now]:
            if vis[x][(step+1)%3] < 0:
                q.append((x,cnt+1))
    return -3
vis[S][0] = 1
q.append([S,0])
print(bfs()//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        step = cnt % 3
        vis[now][step] = cnt
        if now == T and step  == 0:  
            return cnt
        for x in path[now]:
            if vis[x][(step+1)%3] == -1:
                q.append((x,cnt+1))
    return -3
vis[S][0] = 1
q.append([S,0])
print(bfs()//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import queue

q = queue.Queue()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while not q.empty():
        now,cnt = q.get()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.put((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.put([S,0])
print(bfs()//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        if time.time() -start_t > 1.99:
            return -3
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.append((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.append([S,0])
print(bfs()//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        if start_t - time.time() > 1.9999:
            return -3
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.append((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.append([S,0])
print(bfs()//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.append((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.append([S,0])
print(bfs()//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        for x in path[now]:
            if vis[x] == -1:
                q.append((x,cnt+1))
    return -3
vis[S] = 1
q.append([S,0])
print(bfs()//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        for x in path[now]:
            if vis[x] == -1:
                q.append((x,cnt+1))
vis[S] = 1
q.append([S,0])
ans = bfs()
if vis[T] == -1: print(-1)
else: print(ans//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [10**10 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = min(vis[now],cnt)
        if now == T: 
            return cnt
        for x in path[now]:
            if vis[x] == 10**10:
                q.append([x,cnt+1])
vis[S] = 1
q.append([S,0])
ans = bfs()
if vis[T] == 10**10: print(-1)
else: print(ans//3)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [10**10 for _ in range(N*3+3)]
def bfs():
    for _ in range(10**6):
        if len(q) == 0: break
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = min(vis[now],cnt)
        if now == T: 
            return cnt
        for x in path[now]:
            if vis[x] == 10**10:
                q.append([x,cnt+1])
vis[S] = 1
q.append([S,0])
ans = bfs()
if vis[T] == 10**10: print(-1)
else: print(ans//3)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, readline().split())
        G[u - 1].append(v - 1)
    S, T = map(int, readline().split())
    S -= 1
    T -= 1

    seen = [[False] * 4 for _ in range(N)]

    def dfs(G, v, step, seen):
        if step == 0:
            if v == T:
                return 0
            else:
                step = 3

        ans = INF
        for nv in G[v]:
            if seen[nv][step - 1]:
                continue
            seen[nv][step - 1] = True
            tmp = dfs(G, nv, step - 1, seen) + 1
            seen[nv][step - 1] = False
            if ans > tmp:
                ans = tmp

        return ans

    ans = dfs(G, S, 3, seen)
    if ans == INF:
        print(-1)
    else:
        print(ans // 3)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, M = map(int, input().split())
  edge = [[] for _ in range(N)]
  for i in range(M):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)
  d = [-1]*N
  S, T = map(int, input().split())
  d[S-1] = 0
  que = [S-1]
  while len(que)>0:
    now = que.pop(0)
    for i in edge[now]:
      for j in edge[i]:
        for k in edge[j]:
          if d[k] == -1:
            que.append(k)
            d[k] = d[now]+1 
  print(d[T-1])
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# ぱっと思いつくのはダイクストラで3回で到達できる点を探索していくとかかなぁ
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret

    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


def bfs(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素はノード
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    '''
    # pq = PriorityQueue([])
    cnt = 0
    pq = deque([])
    D = [2**31] * N
    D[s] = 0
    is_visited = [False] * N
    is_visited[s] = True
    pq.append((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.popleft()
        # 探索するのはgraph[v]じゃなくてケンケンパしてたどり着くことのできるノード
        for to in next_node(v, graph):
            cnt += 1
            assert cnt < 10**7  # 10**7じゃなくてもTLEになっている...
            if is_visited[to]:
                continue
            cost = 1
            D[to] = d + cost
            is_visited[to] = True
            pq.append((D[to], to))
    return D


def next_node(v, graph):
    # 距離3のノードの集合を集めてくる
    ret = set()
    q = deque([(0, v)])
    while q:
        d, u = q.popleft()
        if d == 3:
            ret.add(u)
            continue
        for to in graph[u]:
            q.append((d + 1, to))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v)
S, T = mina(*read_ints())

# D = bfs(graph, S, N)
s = S
cnt = 0
pq = deque([])
D = [2**31] * N
D[s] = 0
is_visited = [False] * N
is_visited[s] = True
pq.append((D[s], s))  # (最短距離, 次のノード)
while pq:
    d, v = pq.popleft()
    # 探索するのはgraph[v]じゃなくてケンケンパしてたどり着くことのできるノード
    for to in next_node(v, graph):
        cnt += 1
        assert cnt < 10**7  # 10**7じゃなくてもTLEになっている...
        if is_visited[to]:
            continue
        cost = 1
        D[to] = d + cost
        is_visited[to] = True
        pq.append((D[to], to))
print(D[T] if D[T] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# ぱっと思いつくのはダイクストラで3回で到達できる点を探索していくとかかなぁ
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret

    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


def bfs(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素はノード
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    '''
    # pq = PriorityQueue([])
    pq = deque([])
    D = [2**31] * N
    D[s] = 0
    is_visited = [False] * N
    is_visited[s] = True
    pq.append((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.popleft()
        # 探索するのはgraph[v]じゃなくてケンケンパしてたどり着くことのできるノード
        for to in next_node(v, graph):
            if is_visited[to]:
                continue
            cost = 1
            D[to] = d + cost
            is_visited[to] = True
            pq.append((D[to], to))
    return D


def next_node(v, graph):
    # 距離3のノードの集合を集めてくる
    ret = []
    q = deque([(0, v)])
    while q:
        d, u = q.popleft()
        if d == 3:
            ret.append(u)
            continue
        for to in graph[u]:
            q.append((d + 1, to))
    # print(ret)
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v)
S, T = mina(*read_ints())
D = bfs(graph, S, N)
print(D[T] if D[T] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# ぱっと思いつくのはダイクストラで3回で到達できる点を探索していくとかかなぁ
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret

    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


def bfs(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素はノード
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    '''
    # pq = PriorityQueue([])
    pq = deque([])
    D = [2**31] * N
    D[s] = 0
    is_visited = [False] * N
    is_visited[s] = True
    pq.append((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.popleft()
        # 探索するのはgraph[v]じゃなくてケンケンパしてたどり着くことのできるノード
        for to in next_node(v, graph):
            if is_visited[to]:
                continue
            cost = 1
            D[to] = d + cost
            pq.append((D[to], to))
            is_visited[to] = True
    return D


def next_node(v, graph):
    # 距離3のノードの集合を集めてくる
    ret = set()
    q = deque([(0, v)])
    while q:
        d, u = q.popleft()
        if d == 3:
            ret.add(u)
            continue
        for to in graph[u]:
            q.append((d + 1, to))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v)
S, T = mina(*read_ints())
D = bfs(graph, S, N)
print(D[T] if D[T] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# ぱっと思いつくのはダイクストラで3回で到達できる点を探索していくとかかなぁ
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret


    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


def bfs(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素はノード
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    '''
    # pq = PriorityQueue([])
    pq = deque([])
    D = [2**31] * N
    D[s] = 0
    is_visited = [False] * N
    is_visited[s] = True
    pq.append((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.popleft()
        # 探索するのはgraph[v]じゃなくてケンケンパしてたどり着くことのできるノード
        for to in next_node(v):
            if is_visited[to]:
                continue
            cost = 1
            D[to] = d + cost
            pq.append((D[to], to))
            is_visited[to] = True
    return D


def next_node(v):
    # 距離3のノードの集合を集めてくる
    ret = set()
    q = deque([(0, v)])
    while q:
        d, u = q.popleft()
        if d == 3:
            ret.add(u)
            continue
        for to in graph[u]:
            q.append((d + 1, to))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v)
S, T = mina(*read_ints())
D = bfs(graph, S, N)
print(D[T] if D[T] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc132/tasks/abc132_e
# ぱっと思いつくのはダイクストラで3回で到達できる点を探索していくとかかなぁ
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret

    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def dijkstra(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素はノード
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    P ... 最短経路木における親
    '''
    # pq = PriorityQueue([])
    pq = deque([])
    D = [2**31] * N
    D[s] = 0
    pq.append((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.popleft()
        if D[v] < d:  # この辺を扱っても最短距離にならない
            continue  # is_visitedなくてもこれを使うことで最小のものを再び探索するのを防げる
        # 探索するのはgraph[v]じゃなくてケンケンパしてたどり着くことのできるノード
        for to in next_node(v):
            cost = 1
            if D[to] > D[v] + cost:  # v周りにおける最短経路の候補の更新
                D[to] = D[v] + cost
                pq.append((D[to], to))
    return D


def next_node(v):
    # 距離3のノードの集合を集めてくる
    ret = set()
    q = deque([(0, v)])
    while q:
        d, u = q.popleft()
        if d == 3:
            ret.add(u)
            continue
        for to in graph[u]:
            q.append((d + 1, to))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, M = read_ints()
graph = defaultdict(lambda: [])
for _ in range(M):
    u, v = mina(*read_ints())
    graph[u].append(v)
S, T = mina(*read_ints())
D = dijkstra(graph, S, N)
print(D[T] if D[T] != INF else -1)