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: Accepted

Solution code:
from queue import Queue
import heapq
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print(x, file=sys.stderr)
# template


class Graph():
    """
    Graph のテンプレート。デフォルトは重みなしの有向グラフの隣接リスト形式での定義。
    Parameters
    --------
        n (int): グラフのサイズ。
    Options
    --------
        Weighted = False: 重み付きかどうか
        Directed = True: 有向かどうか
        Matrix = False:　グラフの表現を隣接リストにするか隣接行列にするか。デフォルトは隣接リスト。
    Methods
    -------
        add_edge(start,end,(weight))
            start から end に重さ weight の辺を張る。重みなしグラフの場合は weight を省略する。
        dijkstra(start): O((E+V)logV)
            start から各頂点への最短距離を返す。負の辺があると無理。
        bellman_ford(start): O(EV)
            start から各頂点への最短距離を返す。負の辺があってもいけるが遅い。
    """

    def __init__(self, n, Weighted=False, Directed=True, Matrix=False):
        self.sz = n
        self.is_Weighted = Weighted
        self.is_Directed = Directed
        self.is_Matrix = Matrix
        if Matrix:
            if Weighted:
                self.graph = [[float('inf') for _i in range(n)]
                              for _j in range(n)]
            else:
                self.graph = [[0 for _i in range(n)] for _j in range(n)]
        else:
            self.graph = [[] for _i in range(n)]

    def _weighted_add_edge(self, x, y, w):
        if self.is_Matrix:
            self.graph[x][y] = w
        else:
            self.graph[x].append((y, w))

    def _unweighted_add_edge(self, x, y):
        if self.is_Matrix:
            self.graph[x][y] = 1
        else:
            self.graph[x].append(y)

    def add_edge(self, x, y, *w):
        if self.is_Directed:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
            else:
                self._unweighted_add_edge(x, y)
        else:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
                self._weighted_add_edge(y, x, w[0])
            else:
                self._unweighted_add_edge(x, y)
                self._unweighted_add_edge(y, x)

    def _convert_to_maxrix(self):
        if self.is_Matrix:
            return self
        mat_g = self.__class__(
            self.sz,
            Weighted=self.is_Weighted,
            Directed=self.is_Directed,
            Matrix=True)
        if self.is_Weighted:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j[0], j[1])
        else:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j)
        return mat_g

    def __getitem__(self, n):
        return self.graph[n]

    # def __setitem__(self, n, v):
    #     if not self.is_Weighted and not self.is_Matrix:
    #         self.graph[n] = v

    def __str__(self):
        return str([self.graph[i] for i in range(self.sz)])

    def dijkstra(self, s):
        """
        単一始点最短距離を求める関数。dijkstra(s)でsからの任意の頂点への最短距離を求める。到達できなければfloat('inf')を返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならば bfs を使うか，グラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        b = [-1 for _ in range(self.sz)]  # 最短経路で各頂点の直前を表す list （経路復元）
        q = []
        d[s] = 0
        heapq.heappush(q, (d[s], s))
        while not len(q) == 0:
            p = heapq.heappop(q)
            v = p[-1]
            if d[v] < p[0]:
                continue
            if self.is_Weighted:
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[u] > d[v] + c:
                        d[u] = d[v] + c
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
            else:
                for e in self.graph[v]:
                    u = e
                    if d[u] > d[v] + 1:
                        d[u] = d[v] + 1
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
        return d

    def bellman_ford(self, s):
        """
        単一始点最短距離を求める関数。bellman_ford(s)でsからの任意の頂点への最短距離を求める。到達できなければ　float('inf')　を返す。負のサイクルがある場合は False のみを返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = [float('inf') for _ in range(self.sz)]
        d[s] = 0
        for i in range(self.sz - 1):
            for v in range(self.sz):
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[v] == float('inf'):
                        continue
                    d[u] = min(d[u], d[v] + c)
        for v in range(self.sz):
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[v] == float('inf'):
                    continue
                if d[u] > d[v] + c:
                    return False
        return d

    def warshall_froyd(self):
        """
        全頂点間最短距離を求める関数。warshall_froyd()で任意の頂点間の最短距離を求める。到達できなければ　float('inf')　を返す。
        負のサイクルがあるかどうかは自分自身との最短距離 d[i][i] の中に負のものがあるかどうかで分かる。

        Warning
        ----------
            隣接行列形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = self._convert_to_maxrix()
        for i in range(self.sz):
            d[i][i] = 0
        for k in range(self.sz):
            for i in range(self.sz):
                for j in range(self.sz):
                    if d[i][k] != float('inf') and d[k][j] != float('inf'):
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d


def AOJ_ALDS_1_11_A():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    mat_g = g._convert_to_maxrix()
    for i in range(n):
        print(*mat_g[i])
# verified on 2019/07/02


def AOJ_ALDS_1_11_B():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    d = [-1] * n
    f = [-1] * n
    time = 0

    def dfs(G, v):
        nonlocal time
        time += 1
        d[v] = time
        for nv in G[v]:
            if d[nv] != -1:
                continue
            dfs(G, nv)
        time += 1
        f[v] = time

    for v in range(n):
        if d[v] != -1:
            continue
        dfs(g, v)
    for i in range(n):
        print(i + 1, d[i], f[i])
# verified on 2019/07/02


def AOJ_ALDS_1_11_C():
    """
    各頂点の0からの最短距離を bfs で求める
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    q = Queue()
    n = ii()
    dist = [-1 for _ in range(n)]
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    q.put(0)
    dist[0] = 0
    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                q.put(nv)
    for i in range(n):
        print(i + 1, dist[i])
# verified on 2019/07/02


def AOJ_GRL_1_A():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"""
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    for i in g.dijkstra(start):
        if i == float('inf'):
            print('INF')
        else:
            print(i)
    # debug(g)
# verified on 2019/07/02


def AOJ_ALDS_1_11_C_kai():
    """
    各頂点の0からの最短距離を dijkstra で求める。
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    n = ii()
    g = Graph(n, Weighted=True)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1, 1)
    dist = g.dijkstra(0)
    for i in range(n):
        if dist[i] == float('inf'):
            print(i + 1, -1)
        else:
            print(i + 1, dist[i])
# verified on 2019/07/02


def AOJ_GRL_1_B():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp"""
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.bellman_ford(start)
    if d == False:
        print("NEGATIVE CYCLE")
    else:
        d = list(map(lambda x: x if x != float('inf') else 'INF', d))
        for i in d:
            print(i)
# verified on 2019/07/02


def AOJ_GRL_1_C():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp"""
    n, m = mi()
    g = Graph(n, Weighted=True, Directed=True, Matrix=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.warshall_froyd()
    d = [list(map(lambda x: x if x != float('inf') else 'INF', d[i]))
         for i in range(n)]
    for i in range(n):
        if d[i][i] < 0:
            print('NEGATIVE CYCLE')
            sys.exit()
    for i in d:
        print(*i)
# verified on 2019/07/02


def ABC132_E():
    """
    頂点3倍するdijkstra法。頂点倍加の典型例として
    https://atcoder.jp/contests/abc132/tasks/abc132_e
    """
    N, M = mi()
    g = Graph(3 * N)
    for i in range(M):
        a, b = mi()
        g.add_edge(a - 1, b + N - 1)
        g.add_edge(a + N - 1, b + 2 * N - 1)
        g.add_edge(a + 2 * N - 1, b - 1)
    S, T = mi()
    ans = g.dijkstra(S - 1)[T - 1]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans // 3)


def ABC079_D():
    """https://atcoder.jp/contests/abc079/tasks/abc079_d"""
    H, W = mi()
    mat = [[] for __ in range(10)]
    for i in range(10):
        mat[i] = lmi()
    g = Graph(10, Matrix=True, Weighted=True)
    g.graph = mat
    cost = g.warshall_froyd()
    field = [[] for _ in range(H)]
    for i in range(H):
        field[i] = lmi()
    ans = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] != -1:
                ans += cost[field[i][j]][1]
    print(ans)


if __name__ == '__main__':
    # AOJ_ALDS_1_11_A()
    # AOJ_ALDS_1_11_B()
    # AOJ_ALDS_1_11_C()
    # AOJ_GRL_1_A()
    # AOJ_ALDS_1_11_C_kai()
    # AOJ_GRL_1_B()
    # AOJ_GRL_1_C()
    ABC132_E()
    # ABC079_D()

Submission status: Accepted

Solution code:
import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
queue = []
def bfs(arr,jump):
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
queue=deque()
queue.append([s,0])
while(len(queue)>0 ):
    next=queue.popleft()
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
        if jumpValue[t][0]!=-1:
            break
print(max(jumpValue[t][0]//3,-1))

Submission status: Accepted

Solution code:
import heapq
 
N , M = map(int,input().split())
 
# edges , costs
nodes = [[] for _ in range(3 * N)]
 
confilm = [False] * (3 * N)  # 確定フラグ
 
costs = [-1] * (3 * N)  # 最短経路
 
# 辺の入力
for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3
 
    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))
 
 
# スタート ゴール
startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1

startNode *= 3
endNode *= 3
 
costs[startNode] = 0
 
q = [(0,startNode)]
 
# 探索
while q : # 空になるまで
    nowCost , nowNode = heapq.heappop(q)
 
    if confilm[nowNode] :
        continue
 
    confilm[nowNode] = True
 
    # 長さを更新
    for nextNode , cost in nodes[nowNode] :
        # if not confilm[nextNode] :  # 確定ノード以外
        nextCost = nowCost + cost
        if costs[nextNode] == -1 or nextCost < costs[nextNode] :
            costs[nextNode] = nextCost  # コストを更新
            heapq.heappush(q,(nextCost,nextNode))
 
if costs[endNode] < 0 :
    print(-1)
else :
    print(costs[endNode] // 3)

Submission status: Accepted

Solution code:
def dijkstra(edge,start,end) :
    import heapq

    minCosts = [float('inf') for _ in range(len(edge))]

    nodeHeap = []
    heapq.heappush(nodeHeap, (0, start))  # (cost, node)

    while nodeHeap :
        cost, node = heapq.heappop(nodeHeap)

        if minCosts[node] <= cost :
            continue

        minCosts[node] = cost

        for nextNode , weight in edge[node] :
            newCost = cost + weight
            heapq.heappush(nodeHeap, (newCost, nextNode))
    dist = minCosts[endNode]
    if dist == float('inf') :
        return -1
    return dist

N , M = map(int,input().split())

# edges , costs
nodes = [[] for _ in range(3 * N)]

# 辺の入力
for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3

    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))

# スタート ゴール
startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1
startNode *= 3
endNode *= 3

ans = dijkstra(nodes,startNode,endNode)

if ans == -1 :
    print(ans)
else :
    print(ans // 3)

Submission status: Accepted

Solution code:
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    a, b = set(), set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        v = set()
        for j in e[i]:
            if j in a: continue
            a.add(j)
            for k in e[j]:
                if k in b: continue
                b.add(k)
                v.update(e[k])
        if t in v:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(v)]
    return -1


print(BC132_E())

Submission status: Accepted

Solution code:
from collections import*
n, m, *t = map(int, open(0).read().split())       
*w, s, t = [a-1for a in t]         
e = [[]for _ in range(n)]        
for u, v in zip(w[::2], w[1::2]):      
    e[u].append(v)

INF = 10**10
f = [[INF]*3for _ in range(n)]        
f[s][0] = 0        
q = deque([(s, 0)])           
while q:
    vi, j = q.popleft()         
    if vi == t and j == 0:
        print(f[vi][0]//3)
        break
    for ui in e[vi]:           
        if f[ui][(j+1)%3] < INF: continue           
        f[ui][(j+1)%3] = f[vi][j] + 1
        q.append((ui, (j+1)%3))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))

def f(D, S, T):
    close = [[False] * N, [False] * N, [False] * N]
    Q = []
    index = 0
    Q.append((S, 0, 0))

    while len(Q) > index:
        p, c, l = Q[index]
        index += 1
        
        if close[l][p]:
            continue
        
        if l == 0 and p == T:
            return c // 3
        close[l][p] = True

        l, c = (l + 1) % 3, c + 1
        for n in D[p]:
            if close[l][n]:
                continue
            Q.append((n, c, l))
    return -1

if __name__ == "__main__":
    D = {n: set() for n in range(N)}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D[u].add(v)

    S, T = list(map(int, input().split()))
    S -= 1
    T -= 1

    print(f(D, S, T))

Submission status: Accepted

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

#+++++
		
def main():
	n, m = map(int, input().split())
	
	nn=[ [] for _ in range(n+1)]
	
	for _ in range(m):
		u, v = map(int, input().split())
		nn[u].append(v)
		
	start, goal = map(int, input().split())
	
	arrived = set()
	opened = [start]
	cc=1
	while len(opened) > 0:
		#print(arrived)
		#print(opened)
		for i in opened:
			arrived.add(i)
		tt =opened.copy()
		opened=[]
		
		
		for i in range(3):
			temp=set()
			for p in tt:
				for i in nn[p]:
					temp.add(i)
			tt=list(temp)
			#print('tt:'+str(tt))
		#print('ccccc'+str(goal)+':'+str(tt))
		if goal in tt:
			return cc
		cc+=1
		
		for ttt in tt:
			if ttt not in arrived:
				opened.append(ttt)
	return -1
		
		

	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# SからTの長さが3の倍数の最短バスを求める
N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)

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

from collections import deque

def bfs(start, terminal):
    q = deque([(start, 0)])
    color = [[0]*3 for _ in range(N)]
    d = [[-1]*3 for _ in range(N)]
    d[start][0] = 0
    l = 0
    while len(q) > 0:
        u, l = q.popleft()
        nl = (l + 1) % 3
        for v in G[u]:
            if color[v][nl] == 0:
                q.append((v, nl))
                color[v][nl] = 1
                d[v][nl] = d[u][l] + 1
    
    if d[terminal][0] == -1:
        return -1
    else:
        return d[terminal][0] // 3 

print(bfs(S, T))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v+N)
    graph[u+N].append(v+2*N)
    graph[u+2*N].append(v)
S, T = map(int,input().split())
S, T = S-1, T-1
visit = [False for i in range(3 * N)]
length = [0 for i in range(3 * N)]
def bfs(v):
    Q = []
    Q.append(v)
    visit[v] = True
    while Q:
        v = Q.pop(0)
        for u in graph[v]:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
bfs(S)
#print(length)
if visit[T]:
    print(int(length[T] //3))
else:
    print(-1)

Submission status: Accepted

Solution code:
from queue import Queue
import heapq
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print(x, file=sys.stderr)
# template


class Graph():
    """
    Graph のテンプレート
    Parameters
    --------
        n (int): グラフのサイズ。
    Options
    --------
        Weighted = False: 重み付きかどうか
        Directed = False: 有向かどうか
        Matrix = False:　グラフの表現を隣接リストにするか隣接行列にするか。デフォルトは隣接リスト。
    Methods
    -------
        add_edge(start,end,(weight))
            start から end に重さ weight の辺を張る。重みなしグラフの場合は weight を省略する。
        dijkstra(start): O((E+V)logV)
            start から各頂点への最短距離を返す。負の辺があると無理。
        bellman_ford(start): O(EV)
            start から各頂点への最短距離を返す。負の辺があってもいけるが遅い。
    """

    def __init__(self, n, Weighted=False, Directed=False, Matrix=False):
        self.sz = n
        self.is_Weighted = Weighted
        self.is_Directed = Directed
        self.is_Matrix = Matrix
        if Matrix:
            if Weighted:
                self.graph = [[float('inf') for _i in range(n)]
                              for _j in range(n)]
            else:
                self.graph = [[0 for _i in range(n)] for _j in range(n)]
        else:
            self.graph = [[] for _i in range(n)]

    def _weighted_add_edge(self, x, y, w):
        if self.is_Matrix:
            self.graph[x][y] = w
        else:
            self.graph[x].append((y, w))

    def _unweighted_add_edge(self, x, y):
        if self.is_Matrix:
            self.graph[x][y] = 1
        else:
            self.graph[x].append(y)

    def add_edge(self, x, y, *w):
        if self.is_Directed:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
            else:
                self._unweighted_add_edge(x, y)
        else:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
                self._weighted_add_edge(y, x, w[0])
            else:
                self._unweighted_add_edge(x, y)
                self._unweighted_add_edge(y, x)

    def __getitem__(self, n):
        return self.graph[n]

    def __setitem__(self, n, v):
        if not self.is_Weighted and not self.is_Matrix:
            self.graph[n] = v

    def __str__(self):
        return str([self.graph[i] for i in range(self.sz)])

    def dijkstra(self, s):
        """
        単一始点最短距離を求める関数。dijkstra(s)でsからの任意の頂点への最短距離を求める。到達できなければfloat('inf')を返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならば bfs を使うか，グラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        b = [-1 for _ in range(self.sz)]  # 最短経路で各頂点の直前を表す list （経路復元）
        q = []
        d[s] = 0
        heapq.heappush(q, (d[s], s))
        while not len(q) == 0:
            p = heapq.heappop(q)
            v = p[-1]
            if d[v] < p[0]:
                continue
            if self.is_Weighted:
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[u] > d[v] + c:
                        d[u] = d[v] + c
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
            else:
                for e in self.graph[v]:
                    u = e
                    if d[u] > d[v] + 1:
                        d[u] = d[v] + 1
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
        return d

    def bellman_ford(self, s):
        """
        単一始点最短距離を求める関数。bellman_ford(s)でsからの任意の頂点への最短距離を求める。到達できなければ　float('inf')　を返す。負のサイクルがある場合は False のみを返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = [float('inf') for _ in range(self.sz)]
        d[s] = 0
        for i in range(self.sz - 1):
            for v in range(self.sz):
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[v] == float('inf'):
                        continue
                    d[u] = min(d[u], d[v] + c)
        for v in range(self.sz):
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[v] == float('inf'):
                    continue
                if d[u] > d[v] + c:
                    return False
        return d

    def warshall_froyd(self):
        d = self.graph
        for i in range(self.sz):
            d[i][i] = 0
        for k in range(self.sz):
            for i in range(self.sz):
                for j in range(self.sz):
                    if d[i][k] != float('inf') and d[k][j] != float('inf'):
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d


def AOJ_ALDS_1_11_A():
    # 隣接リスト形式の重みなしグラフ
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        g[u - 1] = list(map(lambda x: x - 1, v))
    # 隣接行列形式の重みなしグラフ
    mat_g = Graph(n, Matrix=True)
    for i in range(n):
        for j in g[i]:
            mat_g[i][j] = 1
    for i in range(n):
        print(*mat_g[i])
# verified on 2019/07/02
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A&lang=jp


def AOJ_ALDS_1_11_B():
    # 隣接リスト形式の重みなしグラフ
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        g[u - 1] = list(map(lambda x: x - 1, v))
    d = [-1] * n
    f = [-1] * n
    time = 0

    def dfs(G, v):
        nonlocal time
        time += 1
        d[v] = time
        for nv in G[v]:
            if d[nv] != -1:
                continue
            dfs(G, nv)
        time += 1
        f[v] = time

    for v in range(n):
        if d[v] != -1:
            continue
        dfs(g, v)
    for i in range(n):
        print(i + 1, d[i], f[i])
# verified on 2019/07/02
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=jp


def AOJ_ALDS_1_11_C():
    """
    各頂点の0からの最短距離を bfs で求める
    """
    q = Queue()
    n = ii()
    dist = [-1 for _ in range(n)]
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        g[u - 1] = list(map(lambda x: x - 1, v))
    q.put(0)
    dist[0] = 0
    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                q.put(nv)
    for i in range(n):
        print(i + 1, dist[i])
# verified on 2019/07/02
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp


def AOJ_GRL_1_A():
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    for i in g.dijkstra(start):
        if i == float('inf'):
            print('INF')
        else:
            print(i)
    # debug(g)
# verified on 2019/07/02
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp


def AOJ_ALDS_1_11_C_kai():
    """
    各頂点の0からの最短距離を dijkstra で求める
    """
    n = ii()
    g = Graph(n, Directed=True)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    dist = g.dijkstra(0)
    for i in range(n):
        if dist[i] == float('inf'):
            print(i + 1, -1)
        else:
            print(i + 1, dist[i])
# verified on 2019/07/02
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp


def AOJ_GRL_1_B():
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.bellman_ford(start)
    if d == False:
        print("NEGATIVE CYCLE")
    else:
        d = list(map(lambda x: x if x != float('inf') else 'INF', d))
        for i in d:
            print(i)
# verified on 2019/07/02
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp


def AOJ_GRL_1_C():
    n, m = mi()
    g = Graph(n, Weighted=True, Directed=True, Matrix=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.warshall_froyd()
    d = [list(map(lambda x: x if x != float('inf') else 'INF', d[i]))
         for i in range(n)]
    for i in range(n):
        if d[i][i] < 0:
            print('NEGATIVE CYCLE')
            sys.exit()
    for i in d:
        print(*i)
# verified on 2019/07/02
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp


def ABC132_E():
    N, M = mi()
    g = Graph(3 * N, Directed=True)
    for i in range(M):
        a, b = mi()
        g.add_edge(a - 1, b + N - 1)
        g.add_edge(a + N - 1, b + 2 * N - 1)
        g.add_edge(a + 2 * N - 1, b - 1)
    S, T = mi()
    ans = g.dijkstra(S - 1)[T - 1]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans // 3)


if __name__ == '__main__':
    # AOJ_ALDS_1_11_A()
    # AOJ_ALDS_1_11_B()
    # AOJ_ALDS_1_11_C()
    # AOJ_GRL_1_A()
    # AOJ_ALDS_1_11_C_kai()
    # AOJ_GRL_1_B()
    # AOJ_GRL_1_C()
    ABC132_E()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    u,v=map(int,input().split())
    branch[u-1]|={v-1}
s,t=map(int,input().split())
s-=1
t-=1
dist=[[float('inf')]*3 for i in range(n)]
check={(s,0)}
dist[s][0]=0
while len(check)>0:
    now,nowd=check.pop()
    for nex in branch[now]:
        if dist[nex][(nowd+1)%3]>dist[now][nowd]+1:
            dist[nex][(nowd+1)%3]=dist[now][nowd]+1
            check|={(nex,(nowd+1)%3)}
if dist[t][0]>10**18:
    print(-1)
else:
    print(dist[t][0]//3)