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 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 = next_kenp(node, edges, dones)
        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:
import heapq
n, m = map(int, input().split())
G = [[] for _ in range(n)]
G2 = []
for _ in range(m):
    u, v = map(int, input().split())
    G[u-1].append(v-1)
s, t = map(int, input().split())
s -= 1
t -= 1
for i in range(n):
    x = {i}
    for _ in range(3):
        y = set()
        for u in x:
            y |= set(G[u])
        x = y
    G2.append(list(x))
d = [float("inf")]*n
d[s] = 0
h = []
heapq.heappush(h, (0, s))
while h:
    x, v = heapq.heappop(h)
    if d[v] < x:
        continue
    for u in G2[v]:
        if d[v] + 1 < d[u]:
            d[u] = d[v] + 1
            heapq.heappush(h, (d[u], u))
if d[t] == float("inf"):
    print(-1)
else:
    print(d[t])

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 = [float("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]:
                newedge[num].append(k)
    nnewedge = [[] for i in range(n)]
    for num,i in enumerate(newedge):
        for j in i:
            for k in edge[j]:
                if num == k:
                    continue
                nnewedge[num].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 search(now):   #今いる頂点からけんけんぱでいける点を列挙する
    ret = []
    for v in edge[now]:
        for v2 in edge[v]:
            for v3 in edge[v2]:
                ret.append(v3)
    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:
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 for i in range(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

        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

        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:
#
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 = []
    for n1 in edges[node]:
        for n2 in edges[n1]:
            for n3 in edges[n2]:
                if n3 in dones:
                    continue
                nodes.append(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 = next_kenp(node, edges, dones)
        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:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


from heapq import heappop, heappush


def dijkstra(graph, start):
    """ Uses Dijkstra's algortihm to find the shortest path between in a graph. """
    n = len(graph)
    dist, parents = [10**9] * n, [-1] * n
    dist[start] = 0

    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if path_len == dist[v]:
            for w, edge_len in graph[v]:
                if edge_len + path_len < dist[w]:
                    dist[w], parents[w] = edge_len + path_len, v
                    heappush(queue, (edge_len + path_len, w))

    return dist


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u - 1].append(v - 1)
    s, t = map(int, input().split())

    new_graph = [set() for _ in range(n)]
    for i in range(n):
        for child in graph[i]:
            for grandchild in graph[child]:
                for greatgrandchild in graph[grandchild]:
                    new_graph[i].add((greatgrandchild, 1))

    dist = dijkstra(new_graph, s - 1)[t - 1]
    print(-1 if dist == 10**9 else dist)




# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def make_3hop(g):
    gg = []
    for start in xrange(len(g)):
        nei = [start]
        for _ in xrange(3):
            new = []
            for u in nei:
                new.extend(g[u])
            nei = new
        gg.append(list(set(nei) - {start}))
    return gg


def bfs(gg, start, goal):
    visited = [False] * len(gg)
    now = [start]
    visited[start] = True
    step = 1
    while now:
        nex = []
        for u in now:
            for v in gg[u]:
                if visited[v]:
                    continue
                if v == goal:
                    return step
                visited[v] = True
                nex.append(v)
        now = nex
        step += 1
    return -1


def main():
    n, m = map(int, raw_input().split())
    g = [[] for _ in xrange(n)]
    for _ in xrange(m):
        u, v = map(int, raw_input().split())
        g[u - 1].append(v - 1)
    s, t = map(int, raw_input().split())
    gg = make_3hop(g)
    print bfs(gg, s - 1, t - 1)


if __name__ == '__main__':
    main()

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 = [float("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]:
                newedge[num].append(k)
    nnewedge = [[] for i in range(n)]
    for num,i in enumerate(newedge):
        for j in i:
            for k in edge[j]:
                nnewedge[num].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:
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())
    def kenkenpa(v):
        return (v3 for v1 in G[v] for v2 in G[v1] for v3 in G[v2])
    visited={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            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 math

import sys
input = sys.stdin.readline

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


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

    for i in range(edge_num):
        a, b = map(int, input().split())
        graph_data[a].add(b)

    start, goal = map(int, input().split())
    visit_flg = [0 for i in range(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

        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

        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:
import sys
from collections import deque


input = sys.stdin.readline
n, m = map(int, input().split())
info = tuple(map(int, input().split()) for i in range(m))
s, t = map(int, input().split())

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)


graph2 = [[] for i in range(n)]
q = deque()
q.append((s - 1, 0))
INF = float("inf")
visited = [INF] * n
visited[0] = 0

while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 != 0:
            q.append((i, times + 1))
        if (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append((i, times+1))

if visited[t-1] == float("inf"):
    print(-1)
else:
    print(visited[t-1]//3)

Submission status: Time Limit Exceeded

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

def next_kenp(node, edges):
    nodes = []
    for n1 in edges[node]:
        for n2 in edges[n1]:
            for n3 in edges[n2]:
                nodes.append(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 = [(s, 0)]
    while que:
        node, step = que.pop(0)
        next_nodes = next_kenp(node, edges)
        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:
N,M = (int(x) for x in input().split())
v_dict = {}
for _ in range(M):
    u,v = (int(x) for x in input().split())
    v_dict.setdefault(u, [])
    v_dict[u].append(v)
S,T = (int(x) for x in input().split())

def dfs(n, visited_set):
    if n in visited_set:
        return
    if step_left == 1:
        return v_dict[n]
    ans = []
    for v in v_dict[n]:
        ans.append(dfs(v, step_left-1))
    return ans

v2_dict = {}
for n in v_dict.keys():
    tmp = []
    for v in v_dict[n]:
        tmp += v_dict.get(v, [])
    v2_dict[n] = tmp
v3_dict = {}
for n in v_dict.keys():
    tmp = []
    for v in v_dict[n]:
        tmp += v2_dict.get(v, [])
    v3_dict[n] = tmp

visited = set()
found = set()

if S == T:
    print("0")
    exit()

nsteps = 1
current_node = [S]
next_node = []
while(True):
    if len(current_node) == 0:
        print("-1")
        exit()
    for n in current_node:
        neighs = v3_dict.get(n, [])
        for neigh in neighs:
            if neigh == T:
                print(nsteps)
                exit()
            if neigh in found:
                continue
            next_node.append(neigh)
            found.add(neigh)
    nsteps += 1
    current_node = next_node
    next_node = []

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
s, t = map(int, input().split())

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)


graph2 = [[] for i in range(n)]
q = deque()
q.append([s - 1, 0])
visited = [float("inf")] * n
visited[0] = 0

while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 != 0:
            q.append([i, times + 1])
        if (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append([i, times+1])

if visited[t-1] == float("inf"):
    print(-1)
else:
    print(visited[t-1]//3)

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 = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, _ in edge[u]:
            for l, _ in edge[j]:
                for x, _ in edge[l]:
                    if dist[x] > du + 1:
                        dist[x] = du + 1
                        heappush(q, [dist[x], x])
    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,1))
    d = dijkstra(n, s, edge)
    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:
#!/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 = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in edge[u]:
            for l, m in edge[j]:
                for x, y in edge[l]:
                    if dist[x] > du + 1:
                        dist[x] = du + k
                        heappush(q, [dist[x], x])
    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,1))
    d = dijkstra(n, s, edge)
    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:
N, M = map(int, input().split())
E = [[] for _ in range(N + 1)]

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

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

cost = [[float('inf') for i in range(N + 1)] for _ in range(3)]

stack = [(S, 0)]

while len(stack):
    now = stack.pop()
    u = now[0]
    c = now[1]
    for v in E[u]:
        nc = c + 1

        if cost[nc % 3][v] > nc:
            cost[nc % 3][v] = nc
            stack.append((v, nc))

if cost[0][T] != float('inf'):
    print(cost[0][T] // 3)
else:
    print(-1)