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:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge):

    dist = [inf for i in range(num)]
    dist[start] = 0
    q = [(dist[start], start)]
    while q:
        du, u = heappop(q)
        for j in edge[u]:
            if dist[j] > du + 1:
                dist[j] = du + 1
                heappush(q, [dist[j], j])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = [[] for i in range(n)]
    for x,y in v:
        edge[x].append((y))
    newedge = [[] for i in range(n)]
    for num, i in enumerate(edge):
        for j in i:
            for k in edge[j]:
                for l in edge[k]:
                    newedge[num].append(l)
    d = dijkstra(n, s, newedge)
    if d[t] == inf:
        print(-1)
    else:
        print(d[t])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, M = mi()

if M==0:
  print(-1)
  exit()

#けんけんぱで移動できる先（3つ先）を隣接グラフ表現で入れる
#10^5 * 3 くらいでいけると思うが... TLEが解消しなければC++にいく

#隣接グラフ表現によるグラフ情報の格納 N個の頂点の接続先をsetで格納
#けんけんぱの「けん」
ken_Adjs = [set() for _ in range(N)]
for _ in range(M):
  u, v = mi()
  u -= 1
  v -= 1 #0スタートに
  ken_Adjs[u].add(v)

S, T = mi()
S -= 1
T -= 1 #0スタートに


#けんけんぱの「けんけん」
kenken_Adjs = [set() for _ in range(N)]
for i in range(N):
  #adjがない場合にバグらないか注意
  for each_kenAdj in ken_Adjs[i]: #頂点iからいける全てのken頂点について
    kenken_Adjs[i] = kenken_Adjs[i] | ken_Adjs[each_kenAdj] #ken頂点から1つ先


# dijkstra（有向グラフ、経路復元できないパターン）
from collections import defaultdict
import heapq

#けんけんぱの「ぱ」
#pa_Adjsからdijkstra()に渡すためのグラフデータを生成する
# 生成するグラフデータはnodeIDがkeyになっているdict
Graph = defaultdict(list) #辞書をlist()で初期化

for i in range(N):
  #adjがない場合にバグらないか注意
  for each_kenkenAdj in kenken_Adjs[i]: #頂点iからいける全てのken頂点について
    for each_paAdj in ken_Adjs[each_kenkenAdj]:
      Graph[i].append((each_paAdj, 1))


# sからすべての頂点への最小距離を求める O(|E| log |V|)
# 戻り値はlist。[0への最小距離, 1への最小距離, 2への最小距離, ...]
#  辿り着けないノードの場合、関数内で定義した定数INFを返す
# s: startノード
# n: 頂点数
# グラフデータは辞書を使っている。{ノードID:[(to,cost)を格納したリスト],...}
#  graph[nodeID] = [(to1, cost1), (to2, cost2), ...]
# 存在しないキーがエラーになってしまうと困るので、
# graph = defaultdict(list)として、要素を空リストで初期化して生成する



def dijkstra(s: int, n: int, graph: dict) -> list:
  INF = 10 ** 10 #INF以上の経路が存在する可能性がある場合は注意か？？
  que = []    # [(最短距離, node番号)]
  heapq.heappush(que, (0, s))
  min_dist_list = [INF] * n
  min_dist_list[s] = 0
  while que:
    now_dist, node = heapq.heappop(que)

    if min_dist_list[node] < now_dist:
      continue

    for to, dist in graph[node]:
      new_dist = now_dist + dist
      if min_dist_list[to] > new_dist:
        min_dist_list[to] = new_dist
        heapq.heappush(que, (new_dist, to))

  return min_dist_list
ans = dijkstra(S, N, Graph)[T]
print(-1 if ans >= 10**10 else ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
V = [[]for i in range(N+1)]
for i in range(M):
    u,v = map(int,input().split())
    V[u].append(v)
S,T = map(int,input().split())
q = deque([S])
ans = 0
while True:
    ans += 1
    for _ in range(3):
        A = []
        while len(q)!=0:
            v = q.pop()
            A += V[v]
        q = deque(set(A))
    if list(q)==[S] or len(q)==0:
        ans = -1
        break
    elif q.count(T)>0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,M = inpl()
lines1 = defaultdict(set)

for _ in range(M):
    u,v = inpl()
    u -= 1
    v -= 1
    lines1[u].add(v)

S,T = inpl()
S -= 1
T -= 1

#MEMO = [[set() for i in range(3)] for _ in range(N)]
#visited = [False]*N

lines2 = defaultdict(set)
def dfs(start,s,n): #s: 今いる , n: 何歩目
    if n == 3:
        lines2[start].add(s)
    else:
        for t in lines1[s]:
            dfs(start,t,n+1)

for i in range(N):
    dfs(i,i,0)

'''
print()
for s in range(N):
    for t in lines2[s]:
        print(s,t)
'''

def search (s,w_0): #s->t
    global weight
    global q

    for t in list(lines2[s]):
        w = w_0 + 1
        if weight[t] > w:
            heapq.heappush(q, [w,t])
            weight[t] = w

weight = [INF]*N
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
    w,n = heapq.heappop(q)
    search(n,w)

if weight[T] == INF:
    print(-1)
else:
    print(weight[T])

Submission status: Time Limit Exceeded

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

N,M=map(int,input().split())
E=[list(map(int,input().split())) for i in range(M)]
S,G=map(int,input().split())

ELIST=[set() for i in range(N+1)]

for x,y in E:
    ELIST[x].add(y)

check=[float("inf")]*(N+1)
check[S]=0

def three_step_from(S,i):

    ONE=set()

    for s in S:

        ONE=ONE|ELIST[s]

    TWO=set()
    for one in ONE:
        
        TWO=TWO|ELIST[one]

    THREE=set()
    for two in TWO:
        THREE=THREE|ELIST[two]

    RET=set()

    for three in THREE:
        if check[three]!=float("inf"):
            continue
        check[three]=i
        RET.add(three)

    return RET

i=1
NOW={S}
while NOW:
    NOW=three_step_from(NOW,i)
    i+=1

if check[G]==float("inf"):
    print(-1)
else:
    print(check[G])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add(j)
    s,t=map(int,inp().split())
    cache_kenken={}
    cache_kenkenpa={}
    def kenken(v):
        if v not in cache_kenken:
            cache_kenken[v]=[v2 for v1 in G[v] for v2 in G[v1]]
        return cache_kenken[v]
    def kenkenpa(v):
        if v not in cache_kenkenpa:
            cache_kenkenpa[v]=[v3 for v2 in kenken(v) for v3 in G[v2]]
        return cache_kenkenpa[v]
    visited={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            #print('{}:{}->{}'.format(step,u,v))
            if v==t:
                return step+1
            if v not in visited:
                heapq.heappush(que,(step+1,v))
                visited.add(v)
    return -1
print(sol())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    node_num, edge_num = map(int, input().split())
    graph_data = defaultdict(set)

    abcde = [list(map(int, input().split())) for i in range(edge_num)]

    for i in range(edge_num):
        a, b = abcde[i]
        graph_data[a].add(b)

    start, goal = map(int, input().split())
    visit_flg = [0] * (node_num + 1)
    visit_flg[start] = 1

    now_set = set()
    now_set.add(start)
    next_set = set()

    ans = 0

    while len(now_set) > 0:
        ans += 1

        if visit_flg[goal]:
            break

        for now_node in now_set:
            search_now_set = set()
            search_now_set.add(now_node)
            search_next_set = set()

            for i in range(3):
                for search_now_node in search_now_set:
                    search_next_set |= graph_data[search_now_node]
                search_now_set = search_next_set
                search_next_set = set()

            for ele_check in search_now_set:
                if visit_flg[ele_check]:
                    continue
                else:
                    visit_flg[ele_check] = 1
                    next_set.add(ele_check)

                if visit_flg[goal]:
                    break

        if visit_flg[goal]:
            break

        now_set = next_set
        next_set = set()

    if visit_flg[goal]:
        print(ans)
    else:
        print(-1)












if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
from collections import deque


def follow(edges, v, d):
    if d == 3:
        return [v]
    else:
        ans = [follow(edges, u, d + 1) for u in edges[v]]
        return list(chain.from_iterable(ans))


def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        u, v = map(int, input().split())
        edges[u - 1].append(v - 1)

    converted_edges = [[] for _ in range(N)]
    for v, v_edge in enumerate(edges):
        converted_edges[v] = follow(edges, v, 0)

    S, T = map(lambda x: int(x) - 1, input().split())
    q = deque([(S, 0)])

    nodes = [-1] * N

    while q:
        cv, count = q.popleft()
        if cv == T:
            if nodes[cv] == -1:
                nodes[cv] = count
            else:
                nodes[cv] = min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in converted_edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()
    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)

    s, t = map(int, input().split())

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = list(next_kenp(node, edges, dones))
        next_nodes.reverse()
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            if n not in dones:
                que.append((n, step + 1))
                dones.add(n)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,M = inpl()
lines1 = defaultdict(set)

for _ in range(M):
    u,v = inpl()
    u -= 1
    v -= 1
    lines1[u].add(v)

S,T = inpl()
S -= 1
T -= 1

MEMO = [set() for _ in range(N)]
visited = [[False]*2 for _ in range(N)]

lines2 = defaultdict(set)
def dfs(start,s,n): #s: 今いる , n: 何歩目
    if n == 2:
        lines2[start] = copy.deepcopy(lines1[s])
    elif n == 1:
        if visited[s][1]:
            lines2[start].add(MEMO[s])
        else:
            for t in lines1[s]:
                MEMO[s].add(t)
                dfs(start,t,n+1)
    elif n == 0:
        for t in lines1[s]:
            dfs(start,t,n+1)


for i in range(N):
    dfs(i,i,0)


def search (s,w_0): #s->t
    global weight
    global q

    for t in list(lines2[s]):
        w = w_0 + 1
        if weight[t] > w:
            heapq.heappush(q, [w,t])
            weight[t] = w

weight = [INF]*N
weight[S] = 0
q = [[0,S]]
heapq.heapify(q)
while q:
    w,n = heapq.heappop(q)
    search(n,w)

if weight[T] == INF:
    print(-1)
else:
    print(weight[T])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def main():
    n, m = get_li()
    if m > 0:
        U, V = gets(m, [int, int])
    else:
        U, V = [], []
    s, t = get_li()
    edges = defaultdict(list)
    for u, v in zip(U, V):
        edges[u].append(v)
    kkpedges = defaultdict(set)
    for i in range(1, n + 1):
        for j in edges[i]:
            for k in edges[j]:
                for l in edges[k]:
                    kkpedges[i].add(l)
    q = deque()
    known = set()
    for v in kkpedges[s]:
        q.append((v, 1))
        known.add(v)
    while len(q) > 0:
        v, d = q.popleft()
        if v == t:
            print(d)
            return
        for u in kkpedges[v]:
            if u in known:
                continue
            q.append((u, d + 1))
            known.add(u)
    print(-1)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


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


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,atexit
from io import BytesIO
inp = BytesIO(sys.stdin.buffer.read())
input = lambda:inp.readline().decode('ascii')
buf = BytesIO()
sys.stdout.write = lambda s: buf.write(s.encode('ascii'))
atexit.register(lambda:sys.__stdout__.buffer.write(buf.getvalue()))

n,m = map(int,input().split())

C = [[] for _ in range(n)]

for _ in range(m):
    a,b = [int(x)-1 for x in input().split()]
    C[a].append(b)

start,end = [int(x)-1 for x in input().split()]

D = [(i,nei) for i in range(n) for nei in C[i]]
D = {(i,newnei) for i,nei in D for newnei in C[nei]}
D = {(i,newnei) for i,nei in D for newnei in C[nei]}

C = [[] for _ in range(n)]
for a,b in D:
    C[a].append(b)

from collections import defaultdict as dd, deque

res = -1
Q = deque()
Q.append((start,0))
vis = [0]*n
while Q:
    cur,dist = Q.popleft()

    if cur == end:
        res = dist
        break

    if vis[cur]: continue
    vis[cur] = 1

    for nei in C[cur]:
        Q.append((nei,dist+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge):

    dist = [inf for i in range(num)]
    dist[start] = 0
    q = [(dist[start], start)]
    while q:
        du, u = heappop(q)
        for j in edge[u]:
            if dist[j] > du + 1:
                dist[j] = du + 1
                heappush(q, [dist[j], j])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = [[] for i in range(n)]
    for x,y in v:
        edge[x].append((y))
    newedge = [[] for i in range(n)]
    for num, i in enumerate(edge):
        nn = newedge[num] 
        for j in i:
            for k in edge[j]:
                nn.append(k)
    nnewedge = [[] for i in range(n)]
    for num, i in enumerate(newedge):
        nn = nnewedge[num]
        for j in i:
            for k in edge[j]:
                if num == k:
                    continue
                nn.append(k)
    d = dijkstra(n, s, nnewedge)
    if d[t] == inf:
        print(-1)
    else:
        print(d[t])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def expands(Vs, N):
    newVs = [[] for _ in range(N + 1)]
    for s in range(N + 1):
        dist1 = set(n for n in Vs[s])
        dist2 = set(n for d1 in dist1 for n in Vs[d1])
        newVs[s] = list(n for d2 in dist2 for n in Vs[d2] if n != s)
    return newVs


def solve(N, M, UVs, S, T):
    # print(",".join([str(n) for n in [N, M, UVs, S, T]]))

    Vs = [[] for _ in range(N + 1)]
    for u, v in UVs:
        Vs[u].append(v)

    Vs = expands(Vs, N)

    MAX = 10 ** 6
    dist = [MAX for _ in range(N + 1)]
    dist[S] = 0
    q = deque()
    q.append(S)
    while q:
        s = q.popleft()
        for n in Vs[s]:
            if dist[n] == MAX:
                dist[n] = dist[s] + 1
                q.append(n)

    if dist[T] == MAX:
        return -1
    return dist[T]


# assert (solve(4, 4, [(1, 2), (2, 3), (3, 4), (4, 1)], 1, 3) == 2)
# assert (solve(3, 3, [(1, 2), (2, 3), (3, 1)], 1, 2) == -1)
# assert (solve(2, 0, [], 1, 2) == -1)
# assert (solve(6, 8, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 4), (1, 5), (4, 6)], 1, 6) == 2)

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    UVs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    S, T = tuple(map(int, input().split(" ")))
    print(solve(N, M, UVs, S, T))

Submission status: Time Limit Exceeded

Solution code:
import sys,atexit
from io import BytesIO
inp = BytesIO(sys.stdin.buffer.read())
input = lambda:inp.readline().decode('ascii')
buf = BytesIO()
sys.stdout.write = lambda s: buf.write(s.encode('ascii'))
atexit.register(lambda:sys.__stdout__.buffer.write(buf.getvalue()))

n,m = map(int,input().split())

C = [[] for _ in range(n)]

for _ in range(m):
    a,b = [int(x)-1 for x in input().split()]
    C[a].append(b)

start,end = [int(x)-1 for x in input().split()]

D = [(i,nei) for i in range(n) for nei in C[i]]
D = [(i,newnei) for i,nei in D for newnei in C[nei]]
D = [(i,newnei) for i,nei in D for newnei in C[nei]]

C = [set() for _ in range(n)]
for a,b in D:
    C[a].add(b)

from collections import defaultdict as dd, deque

res = -1
Q = deque()
Q.append((start,0))
vis = [0]*n
while Q:
    cur,dist = Q.popleft()

    if cur == end:
        res = dist
        break

    if vis[cur]: continue
    vis[cur] = 1

    for nei in C[cur]:
        Q.append((nei,dist+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点)
def dijkstra(N: int, nodes: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    # スタート位置
    que = [(0, src)]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # srcからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt in nodes[cur]:
            # 今回の経路のが短い時
            if res[cur] + 1 < res[nxt]:
                res[nxt] = res[cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxt], nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

edges2=[]
def rec(org, u, cnt):
    if cnt==3:
        edges2.append((org, u))
        return
    for v in nodes[u]:
        rec(org, v, cnt+1)
    return

for i in range(N):
    rec(i, i, 0)

nodes2=[[] for i in range(N)]
for u, v in edges2:
    nodes2[u].append(v)

res=dijkstra(N, nodes2, S)
if res[T]==INF:
    print(-1)
else:
    print(res[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def search(now):   #今いる頂点からけんけんぱでいける点を列挙する
    ret = []
    for v in edge[now]:
        for v2 in edge[v]:
            ret += edge[v2]
    return list(set(ret))

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)
S,T = map(int,input().split())
S -=1
T -=1

distance = [10**9 for _ in range(N)]
distance[S] = 0

queue = deque([S])
while queue:
    u = queue.popleft()
    for next in search(u):
        if distance[u]+1 < distance[next]:
            distance[next] = distance[u]+1
            queue.append(next)
if distance[T] < 10**9:
    print(distance[T])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, M = mi()

if M==0:
  print(-1)
  exit()

#けんけんぱで移動できる先（3つ先）を隣接グラフ表現で入れる
#10^5 * 3 くらいでいけると思うが... TLEが解消しなければC++にいく

#隣接グラフ表現によるグラフ情報の格納 N個の頂点の接続先をsetで格納
#けんけんぱの「けん」
ken_Adjs = [set() for _ in range(N)]
for _ in range(M):
  u, v = mi()
  u -= 1
  v -= 1 #0スタートに
  ken_Adjs[u].add(v)

S, T = mi()
S -= 1
T -= 1 #0スタートに


#けんけんぱの「けんけん」
kenken_Adjs = [set() for _ in range(N)]
for i in range(N):
  #adjがない場合にバグらないか注意
  for each_kenAdj in ken_Adjs[i]: #頂点iからいける全てのken頂点について
    kenken_Adjs[i] = kenken_Adjs[i] | ken_Adjs[each_kenAdj] #ken頂点から1つ先


#けんけんぱの「ぱ」
pa_Adjs = [set() for _ in range(N)]
for i in range(N):
  #adjがない場合にバグらないか注意
  for each_kenkenAdj in kenken_Adjs[i]: #頂点iからいける全てのken頂点について
    pa_Adjs[i] = pa_Adjs[i] | ken_Adjs[each_kenkenAdj] #kenken頂点から1つ先


# dijkstra（有向グラフ、経路復元できないパターン）
from collections import defaultdict
import heapq
# sからすべての頂点への最小距離を求める O(|E| log |V|)
# 戻り値はlist。[0への最小距離, 1への最小距離, 2への最小距離, ...]
#  辿り着けないノードの場合、関数内で定義した定数INFを返す
# s: startノード
# n: 頂点数
# グラフデータは辞書を使っている。{ノードID:[(to,cost)を格納したリスト],...}
#  graph[nodeID] = [(to1, cost1), (to2, cost2), ...]
# 存在しないキーがエラーになってしまうと困るので、
# graph = defaultdict(list)として、要素を空リストで初期化して生成する

#pa_Adjsからdijkstra()に渡すためのグラフデータを生成する
# 生成するグラフデータはnodeIDがkeyになっているdict
Graph = defaultdict(list) #辞書をlist()で初期化
for i, each_paAdjSet in enumerate(pa_Adjs):
  for each_paAdj_of_i in each_paAdjSet:
    Graph[i].append((each_paAdj_of_i, 1)) #コストはすべて1

def dijkstra(s: int, n: int, graph: dict) -> list:
  INF = 10 ** 10 #INF以上の経路が存在する可能性がある場合は注意か？？
  que = []    # [(最短距離, node番号)]
  heapq.heappush(que, (0, s))
  min_dist_list = [INF] * n
  min_dist_list[s] = 0
  while que:
    now_dist, node = heapq.heappop(que)

    if min_dist_list[node] < now_dist:
      continue

    for to, dist in graph[node]:
      new_dist = now_dist + dist
      if min_dist_list[to] > new_dist:
        min_dist_list[to] = new_dist
        heapq.heappush(que, (new_dist, to))

  return min_dist_list
ans = dijkstra(S, N, Graph)[T]
print(-1 if ans >= 10**10 else ans)