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:
# 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([])
    D = [2**31] * N
    D[s] = 0
    pq.push((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.pop()
        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.push((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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1
N, M = map(int, input().split())

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

UV = np.array([tuple(map(int1, input().split())) for _ in range(M)]) * 3
frm = UV[:, 0].repeat(3) + np.tile(np.arange(3), M)
to = UV[:, 1].repeat(3) + np.tile((np.arange(3) + 1) % 3, M)

S, T = map(int1, input().split())
matr = csr_matrix((np.ones(3 * M, dtype=int), (frm, to)), shape=(3 * N, 3 * N))
way = dijkstra(matr, indices=3 * S).astype(int)

res = way[3 * T]
print(res // 3 if res >= 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1
N, M = map(int, input().split())

frm, to = [], []
for _ in range(M):
    u, v = map(int1, input().split())
    for i in range(3):
        frm.append(i + 3 * u)
        to.append((i + 1) % 3 + 3 * v)

S, T = map(int1, input().split())
matr = csr_matrix(([1] * len(frm), (frm, to)), shape=(3 * N, 3 * N))
way = dijkstra(matr, indices=3 * S).astype(int)

res = way[3 * T]
print(res // 3 if res >= 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M,*f = map(int, open(0).read().split())
uv = [f[i:i+2] for i in range(0, len(f)-2, 2)]
S = f[-2]
T = f[-1]
connected = [[] for _ in range(N+1)]
for u, v in uv:
    connected[u].append(v)

d = deque([S])
for i in range(1,N+1):
    for j in range(3):
        for k in range(len(d)):
            temp = d.popleft()
            for edge in connected[temp]:
                if edge == T:
                    if j == 2:
                        print(i)
                        exit()
                    else:
                        d.append(edge)
                else:
                    d.append(edge)
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M,*f = map(int, open(0).read().split())
uv = [f[i:i+2] for i in range(0, len(f)-2, 2)]
S = f[-2]
T = f[-1]
connected = [[] for _ in range(N+1)]
for u, v in uv:
    connected[u].append(v)

d = deque([S])
for i in range(1,N+1):
    for j in range(3):
        for k in range(len(d)):
            temp = d.popleft()
            for edge in connected[temp]:
                d.append(edge)
    if T in d:
        print(i)
        break
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
adj = [list() for _ in range(N)]
for _ in range(M):
    u, v = map(lambda s: int(s) - 1, input().split())
    adj[u].append(v)
S, T = map(lambda s: int(s) - 1, input().split())

st = [(0, S, 0)]
seen = {(0, S)}
while len(st) > 0:
    dim, v, cnt = st.pop()
    if dim == 0 and v == T:
        print(cnt // 3)
        exit(0)
    ndim = (dim + 1) % 3
    for nxt in adj[v]:
        if (ndim, nxt) not in seen:
            st.append((ndim, nxt, cnt + 1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
adj = [list() for _ in range(3 * N)]
for _ in range(M):
    u, v = map(lambda s: int(s) - 1, input().split())
    adj[u].append((v + N) % (3 * N))
    adj[u + N].append((v + 2 * N) % (3 * N))
    adj[u + 2 * N].append((v + 3 * N) % (3 * N))
S, T = map(lambda s: int(s) - 1, input().split())

st = [(S, 0)]
seen = {S}
while len(st) > 0:
    v, cnt = st.pop()
    if v == T:
        print(cnt // 3)
        exit(0)
    for nxt in adj[v]:
        if nxt not in seen:
            st.append((nxt, cnt + 1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

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

row = []
col = []
for u, v in uv:
    for i in range(3):
        uu = u + i * n
        vv = v + ((i + 1) % 3) * n
        row.append(uu)
        col.append(vv)

cost = [1] * len(row)
N = 3 * (n + 1)

g = csr_matrix((cost, (row, col)), shape=(N, N))
dist = dijkstra(g, indices=s).astype(int)
ans = dist[t]
if ans < 0:
    ans = -1
else:
    ans //= 3
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(start, goal, g, visited):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        if curr_node == goal: 
            return
        for next1_node in g[curr_node]:
            for next2_node in g[next1_node]:
                for next3_node in g[next2_node]:
                    if visited[next3_node] >= 0: continue
                    visited[next3_node] = visited[curr_node] + 1
                    q.append(next3_node)



def main():
    n,m = map(int, input().split())
    g = [ [] for _ in range(n+1)]

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

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

    visited = [-1]*(n+1)
    visited[0] = 0

    bfs(s, t, g, visited)
    print(visited[t])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,ver = d.popleft()
        check[ver][num%3] = 1
        num = num+1
        #cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num%3 == 0:
                print(num//3)
                exit()
            if check[uv[ver][j]][num%3] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,uv[ver][j]])
                
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import queue
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = queue.Queue()
d.put([0,0,s-1])
#check[s-1][0] = 1

while not d.empty():
    for i in range(d.qsize()):
        num,cnt,ver = d.get()
        check[ver][num] = 1
        num = (num+1)%3
        cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num == 0:
                print(cnt//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.put([num,cnt,uv[ver][j]])
                
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,cnt,ver = d.popleft()
        check[ver][num] = 1
        num = (num+1)%3
        cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num == 0:
                print(cnt//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,cnt,uv[ver][j]])
                
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
es = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    es[u].append(v)
to = [[] for _ in range(n+1)]
for i in range(1, n+1):
    que = deque([])
    for j in es[i]:
        que.append((j, 1))
    while que:
        v,c = que.popleft()
        if c > 3:
            continue
        elif c==3:
            if v  not in to[i]:
                to[i].append(v)
        else:
            for j in es[v]:
                que.append((j, c+1))
s,t = map(int,input().split())
visited = [False]*(n+1)
que = deque([])
for st in to[s]:
    que.append((st, 1))
ans = -1
while que:
    v,c = que.popleft()
    if visited[v]:
        continue
    elif v==t:
        ans = c
        break
    else:
        visited[v] = True
        for nx in to[v]:
            que.append((nx,c+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

visited = set()

my_dict = dict()

for i in range(m):
    u, v = map(int, input().split())
    if u not in my_dict:
        my_dict[u] = [v]
    else:
        my_dict[u].append(v)

s, t = map(int, input().split())
d = deque()
d.append((s, 0, 0))

visited.add((s, 0))

while d:
    cs, cn, ct = d.pop()
    if cs == t and cn == 0:
        print(ct // 3)
        exit()
    if cs in my_dict:
        for item in my_dict[cs]:
            if (item, (cn + 1) % 3) not in visited:
                d.append((item, (cn + 1) % 3, ct + 1))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for i, lst in enumerate(uv):
    for j in lst:
        lst2 = uv[j]
        for k in lst2:
            uv2[i].append(k)
            
for i, lst in enumerate(uv):
    for j in lst:
        lst2 = uv2[j]
        for k in lst2:
            uv3[i].append(k)

queue = deque()
queue.append(s)
queue.append(1)
check = [False for _ in range(n)]
check[s] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    for next_pos in uv3[pos]:
        if next_pos == t:
            print(ans)
            exit()
        if check[next_pos]:
            continue
        check[next_pos] = True
        queue.append(next_pos)
        queue.append(ans + 1)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for i, lst in enumerate(uv):
    for j in lst:
        lst2 = uv[j]
        for k in lst2:
            lst3 = uv[k]
            for l in lst3:
                uv3[i].append(l)
queue = deque()
queue.append(s)
queue.append(1)
check = [False for _ in range(n)]
check[s] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    for next_pos in uv3[pos]:
        if next_pos == t:
            print(ans)
            exit()
        if check[next_pos]:
            continue
        check[next_pos] = True
        queue.append(next_pos)
        queue.append(ans + 1)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

from collections import defaultdict, deque
g1 = defaultdict(set)
for u, v in uv:
    g1[u-1].add(v-1)

s -= 1
t -= 1

f = False
visited = set([s])
q = deque([(s, 0)])
while q:
    cur, d = q.popleft()

    if cur == t:
        f = True
        break
    for target1 in g1[cur]:
        for target2 in g1[target1]:
            for target3 in g1[target2]:
                if target3 not in visited:
                    q.append((target3, d + 1))

if f:
    print(d)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import deque
N, M = map(int, input().split())
graph = {i:[] for i in range(1, N+1)}
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    # graph[v].append(u)
S, T = map(int, input().split())
queue = deque([[graph[S][i], 0] for i in range(len(graph[S]))])
cnt = 0
visited = [False for _ in range(N)]
while queue:
    # print(len(queue))
    now = queue.popleft()
    # print(now)
    now[1] += 1
    # if visited[now[0]-1]:
    #     continue
    if now[1] >= 10**6:
        break
    if now[1] % 3 == 0:
        # print("visited", now[0])
        visited[now[0]-1] = True
        if now[0] == T:
            print(now[1] // 3)
            exit()
        for i in range(len(graph[now[0]])):
            queue.append([graph[now[0]][i], now[1]])
    else:
        for i in range(len(graph[now[0]])):
            queue.append([graph[now[0]][i], now[1]])
print(-1)

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, input().split())
    edge = [[] * N for _ in range(N)]
    new_edge = [set() for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
    
    def dfs(s,now,cnt):
        if cnt == 3:
            if s == now:
                return
            new_edge[s].add(now)
            return

        for v in edge[now]:
            dfs(s,v,cnt+1)
    
    for i in range(N):
        dfs(i,i,0)
    S, T = map(int, input().split())
    S -= 1
    T -= 1
    q = deque([S])
    d = [float('inf')] * N
    d[S] = 0
    while q:
        s = q.popleft()
        if s == T:
            print(d[T])
            exit()
        for v in new_edge[s]: 
            if d[v] != float('inf'):
                continue
            d[v] = d[s] + 1
            q.append(v)

    print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,n):
    #始点sから各頂点への最短距離
    d = [float('inf')] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N, M = map(int, input().split())
    edge = [[] * N for _ in range(N)]
    new_edge = [[] * N for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
    
    def dfs(s,now,cnt):
        if cnt == 3:
            new_edge[s].append((1,now))
            return

        for v in edge[now]:
            dfs(s,v,cnt+1)
    
    for i in range(N):
        dfs(i,i,0)
    S, T = map(int, input().split())
    S -= 1
    T -= 1
    d = dijkstra_heap(S,new_edge,N)
    if d[T] == float('inf'):
        print(-1)
    else:
        print(d[T])
    



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=collections.deque()
q.append([s,0])
while q:
    v,c=q.popleft()
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]==1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=[]
q.append([s,0])
while q:
    v,c=q.pop(0)
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]==1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s)) # (cost, 探索候補ノード)
        v = collections.defaultdict(bool) # 確定済かどうか
        while len(q):
            # ノードuにおけるコストはk
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]: # cost is ud from u to uv
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev
n, m = inpl()
graph=collections.defaultdict(set)
for i in range(m):
    u, v = inpl()
    graph[u].add(v)
s,t=inpl()
@lru_cache(maxsize=None)
def dfs(node, k):
    k-=1
    if k == 0:
        return graph[node]
    tmp=set()
    for i in graph[node]:
        tmp |= dfs(i, k)
    return tmp
ans = 0
new_graph = Dijkstra()
for i in range(1,n+1):
    for j in dfs(i, 3):
        new_graph.add(i, j, 1, directed=True)
d, _ = new_graph.Dijkstra_search(s)
ans=d[t] if d[t]!=INF else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys
N, M = map(int,input().split())
edges = [[] for _ in range(3 * N)]
flag = [0] * (3 * N)
for _ in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    edges[u % (3 * N)].append((v + N) % (3 * N))
    edges[(u + N) % (3 * N)].append((v + 2 * N) % (3 * N))
    edges[(u + 2 * N) % (3 * N)].append(v % (3 * N))

S, T = map(int,input().split())
q = Queue()
q.put([0,S-1])
while not q.empty():
    p = q.get()
    if p[1] == T-1:
        print(p[0] // 3)
        sys.exit()
    for i in edges[p[1]]:
        if flag[i] == 0:
            flag[i] = 1
            q.put([p[0]+1,i])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

N3=N*3
grid=[[-1]*(N3) for _ in range(N3)]

for a,b in edges:
    for i in range(3):
        start = a+N*i
        dst = b+N*(i+1)
        grid[start%N3][dst%N3]=1


Q=[S]
visited={S}
dist=[-1]*N3
dist[S]=0

while Q:
    tmp=[]
    for q in Q:
        for i in range(N3):
            nex = grid[q][i]
            if nex==-1:
                continue
            elif i in visited:
                continue
            else:
                dist[i]=dist[q]+1
                visited.add(i)
                tmp.append(i)
    Q = tmp
print(dist[T] if dist[T]==-1 else dist[T]//3)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    # n, m = mi()
    # inv_adj = [set() for _ in range(n)]
    # inv_dist_2 = [set() for _ in range(n)]
    # inv_hopstepjump = [set() for _ in range(n)]

    # for _ in range(m):
    #     u, v = mi_0()
    #     inv_adj[v].add(u)
    
    # for i in range(n):
    #     for s in inv_adj[i]:
    #         inv_dist_2[i] |= inv_adj[s]
        
    # for i in range(n):
    #     for s in inv_dist_2[i]:
    #         inv_hopstepjump[i] |= inv_adj[s]

    # start, goal = mi_0()

    # appeared_vertice_set = set([goal])
    # q = deque([(goal, 0)])
    # while q:
    #     # print(q)
    #     u, turn = q.popleft()
    #     if turn >= n:
    #         break
    #     if u == start:
    #         print(turn)
    #         exit()
    #     for v in inv_hopstepjump[u]:
    #         if v not in appeared_vertice_set:
    #             appeared_vertice_set.add(v)
    #             q.append((v, turn + 1))
    # print(-1)

    """
    set を作るところで最悪 O(n^2) より 2 つくらい TLE
    経路長 3 の倍数というところで start からの経由数の剰余 (mod 3) を管理する、という方針は思いついたが... それをノードを増やすことで管理するという発想に至らず。
    """
    n, m = mi()
    adj = [[] for _ in range(n * 3)]
    for _ in range(m):
        a, b = mi_0()
        adj[a * 3].append(b * 3 + 1)
        adj[a * 3 + 1].append(b * 3 + 2)
        adj[a * 3 + 2].append(b * 3)
    
    start, goal = mi_0()
    start *= 3
    goal *= 3

    q = deque([(start, 0)])
    visited = [False] * (n * 3)
    while q:
        u, dist = q.popleft()
        if dist > 3 * n:
            break
        if u == goal:
            assert (dist % 3 == 0)
            print(dist // 3)
            return
        if not visited[u]:
            for v in adj[u]:
                if not visited[v]:
                    q.append((v, dist + 1))
    print(-1)

        

if __name__ == "__main__":
    main()