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

Solution (Python):
import sys
from io import StringIO
import unittest
import os
from collections import deque
import itertools


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    n, m = map(int, input().split())
    u_s = [list(map(int, input().split())) for i in range(m)]
    s, t = map(int, input().split())

    point_s = [[] for i in range(n + 1)]
    [point_s[u[0]].append(u[1]) for u in u_s]

    
    ans = [999999999 for i in range(n + 1)]
    bef = [999999999 for i in range(n + 1)]
    ans[s] = 0
    bef[s] = 0

    que = deque()
    que.appendleft(s)

    arrived1 = {}
    arrived2 = {}
    arrived3 = {}

    
    while len(que) is not 0:
        now = que.pop()

        
        work_s = point_s[now]
        ken = []
        for work in work_s:
            if arrived1.get(work, 0) == 0:
                ken.append(work)
                arrived1[work] = 1

        
        work_s = [point_s[k] for k in ken]
        work_s = list(itertools.chain.from_iterable(work_s))
        kenken = []
        for work in work_s:
            if arrived2.get(work, 0) == 0:
                kenken.append(work)
                arrived2[work] = 1

        work_s = [point_s[k] for k in kenken]
        work_s = list(itertools.chain.from_iterable(work_s))
        kenkenpa = []
        for work in work_s:
            if arrived3.get(work, 0) == 0:
                kenkenpa.append(work)
                arrived3[work] = 1

        for ken in kenkenpa:
            if ans[ken] == 999999999:
                ans[ken] = ans[now] + 1
                bef[ken] = now
                
                que.appendleft(ken)
            elif ans[ken] > ans[now] + 1:
                bef[ken] = now

    if ans[t] == 999999999:
        print(-1)
        return

    aa = bef[t]
    cnt = 1
    for i in range(9999999):
        if aa == s:
            break
        cnt += 1
        aa = bef[aa]

    print(cnt)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4
1 2
2 3
3 4
4 1
1 3"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 3
1 2
2 3
3 1
1 2"""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2 0
1 2"""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6"""
        output = """2"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
from collections import deque
import sys

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

graph = [[] for _ in range(3*n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b+n)
    graph[a+n].append(b+2*n)
    graph[a+2*n].append(b)

dist = [-3] * (3*n+1)
dist[0] = 0
s, t = map(int, input().split())
dist[s] = 0

d = deque()
d.append(s)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -3:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

print(dist[t]//3)

Solution (Python):
N,M=map(int,input().split())
list=[[] for i in range(3*N)]
for i in range(M):
  u,v=map(int,input().split())
  list[3*u-3].append(3*v-2)
  list[3*u-2].append(3*v-1)
  list[3*u-1].append(3*v-3)
s,t=map(int,input().split())
def bfs(a,b):
  visited=[-1 for i in range(3*N)]
  visited[a]=0
  h=[]
  h.append(a)
  while h:
    v=h.pop(0)
    for k in list[v]:
      if visited[k]==-1:
        visited[k]=visited[v]+1
        h.append(k)
  return visited[b]

print(bfs(3*s-3,3*t-3)//3)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
adj = [ [] for _ in range(N) ]
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)

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

INF = float('inf')
dist = [ [INF]*3 for _ in range(N) ]
q = deque([(S,0)])
dist[S][0] = 0

while q:
  n,d = q.popleft()
  for v in adj[n]:
    nd = (d+1)%3
    if dist[v][nd] != INF: continue
    dist[v][nd] = dist[n][d]+1
    q.append((v,nd))

if dist[T][0] == INF:
  print(-1)
else:
  print(dist[T][0]//3)

Solution (Python):
import copy
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u, v = map(int,input().split())
    graph[u].append(v)
s, g = map(int,input().split())

INF = 10**7
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = nq
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Solution (Python):



import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[u].append(v)
S,T = map(int,input().split())

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)

Solution (Python):
import copy
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u, v = map(int,input().split())
    graph[u].append(v)
s, g = map(int,input().split())

INF = 10**7
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Solution (Python):
import copy
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**18
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Solution (Python):
import copy

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**11
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Solution (Python):
import copy

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**18
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

Solution (Python):

"""
タグ: bfs、拡張グラフ
"""

import sys
input = sys.stdin.readline
from collections import deque


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.visited = set()
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        p, t = start, time
        self.visited.add((p,0))
        next_set = deque([(p, t)])
        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if (q, (t+1)%3) in self.visited:
                    continue
                if q == goal and (t+1)%3==0:
                    return (t+1)//3
                self.visited.add((q,(t+1)%3))
                next_set.append((q, t + 1))
        return -1



N, M = map(int, input().split())
graph = Graph(N, directed=True, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)
S, T = map(int, input().split())
print(graph.bfs(start=S, goal=T))

Solution (Python):
from collections import deque
INF = 10**9

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

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

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

dist = [INF] * (3*N)
dist[s] = 0

Q = deque([s])
while len(Q) > 0:
    u = Q.popleft()
    for v in G[u]:
        if dist[v] == INF:
            dist[v] = dist[u] + 1
            Q.append(v)

if dist[t] == INF:
    print(-1)
else: 
    print(dist[t] // 3)

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque



N, M = map(int, input().split())
adj = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    adj[      u].append(  N + v)
    adj[  N + u].append(2*N + v)
    adj[2*N + u].append(      v)

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


q = deque([S])
depth = [10 ** 9] * (3*N)
depth[S] = 0
while q:
    node = q.popleft()
    if node == T:
        break
    for next_node in adj[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.append(next_node)

if depth[T] == 10 ** 9:
    print(-1)
else:
    print(depth[T] // 3)

Solution (Python):

from heapq import heappop, heappush

N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())

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

INF = 10 ** 9 + 7
d = [[INF] * 3 for _ in range(N + 1)]
d[S][0] = 0
pq = []
heappush(pq, (0, S))

while pq:
    _, u = heappop(pq)
    for v in graph[u]:
        for i in range(3):
            if d[v][(i + 1) % 3] > d[u][i] + 1:
                d[v][(i + 1) % 3] = d[u][i] + 1
                heappush(pq, (d[v][(i + 1) % 3], v))

if d[T][0] == INF:
    print(-1)
else:
    print(d[T][0] // 3)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()
graph = [[] for i in range(N*3)]
for _ in range(M):
  a,b = IL()
  a,b = a-1,b-1
  graph[a*3].append(b*3+1)
  graph[a*3+1].append(b*3+2)
  graph[a*3+2].append(b*3)
S,T = IL()
S,T = S-1,T-1

def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      q.append(v)
  return d

d = bfs(graph,S*3)
if d[T*3] == INF:
  print(-1)
else:
  print(d[T*3]//3)

Solution (Python):
N,M=map(int,input().split())
A=[[]for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  A[a-1].append(b-1)
S,T=map(int,input().split())  
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
D=[[-1]*3 for i in range(N)]
def bfs(x,n):
  q=deque()
  q.append((x,n)) 
  while len(q):
    x,n=q.popleft()
    for i in A[x]:
      d=(n+1)%3
      if D[i][d]==-1:
        D[i][d]=D[x][n]+1
        q.append((i,d))
D[S-1][0]=0
bfs(S-1,0)
if D[T-1][0]==-1:
  print(-1)
else:
  print(D[T-1][0]//3)

Solution (Python):
N,M=map(int,input().split())
A=[[]for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  A[a-1].append(b-1)
S,T=map(int,input().split())  
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
D=[[-1]*3 for i in range(N)]
def bfs(x,n):
  q=deque()
  q.append((x,n)) 
  while len(q):
    x,n=q.popleft()
    for i in A[x]:
      d=(n+1)%3
      if D[i][d]==-1:
        D[i][d]=D[x][n]+1
        q.append((i,d))
D[S-1][0]=0
bfs(S-1,0)
if D[T-1][0]==-1:
  print(-1)
else:
  print(D[T-1][0]//3)

Solution (Python):
from collections import  deque

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

m = 0
p = 0
d[s][0] = 0

queue = deque([(s, 0)])
while queue:
    i, p0 = queue.popleft()
    p1 = (p0 + 1) % 3
    for j in g[i]:
        if d[j][p1] >= 0:
            continue
        d[j][p1] = d[i][p0] + 1
        if j == t and p1 == 0:
            print(d[j][p1] // 3)
            quit()
        queue.append((j, p1))
print(-1)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
edge = [[] for i in range(n)]
kkp = [0] * n
for i in range(m):
    u, v = map(int, input().split())
    edge[u - 1].append(v - 1)
s, t = map(int, input().split())
que = deque([(s - 1, 0)])
while que:
    now, dis = que.popleft()
    for next in edge[now]:
        if next == t - 1 and (dis + 1) % 3 == 0:
            exit(print((dis + 1) // 3))
        if not kkp[next] & (2 ** ((dis + 1) % 3)):
            kkp[next] = kkp[next] | (2 ** ((dis + 1) % 3))
            que.append((next, dis + 1))
print(-1)

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N + N)
        g[u + N + N].add(v)

    S, T = (int(x) - 1 for x in input().split())

    dist = [-1] * (N * 3)
    dist[S] = 0

    dq = deque()
    dq.append(S)
    while dq:
        v = dq.popleft()
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = dist[v] + 1
            dq.append(u)

    if dist[T] % 3:
        print(-1)
        return

    print(dist[T] // 3)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()
G = {}
for i in range(1,N+1):
    G[(i,0)] = []
    G[(i,1)] = []
    G[(i,2)] = []
for _ in range(M):
    u,v = MI()
    G[(u,0)].append((v,1))
    G[(u,1)].append((v,2))
    G[(u,2)].append((v,0))

S,T = MI()

flag = [[-1]*3 for i in range(N+1)]

from collections import deque

q = deque([(S,0,0)])  
while q:
    n,m,r = q.pop()
    for d,e in G[(n,m)]:
        if flag[d][e] != -1:
            continue
        else:
            flag[d][e] = r+1
            q.appendleft((d,e,r+1))

print(flag[T][0]//3)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
to = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a].append(b)
start,end = map(int,input().split())
start -= 1;end -= 1

INF = float("inf")
Q = deque([(start,0)]) 
visit = [[INF,INF,INF] for _ in range(N)] 
visit[start][0] = 0
while Q: 
  v,step = Q.popleft()
  now = visit[v][step]
  step = (step+1)%3 
  for w in to[v]:
    
    if visit[w][step] != INF:
      continue
    Q.append((w,step)) 
    if step %3 == 0:
      visit[w][step] = min(visit[w][step],now+1)
    else:
      visit[w][step] = min(visit[w][step],now)

if visit[end][0] == INF:
  ans = -1
else:
  ans = visit[end][0]
print(ans)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1

INF = float("inf")
Q = deque([start*3])
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Q:
  v = Q.popleft()
  for w in to[v]:
    if visit[w] != INF:
      continue
    visit[w] = visit[v]+1
    if w == end*3:
      print(visit[w]//3)
      exit()
    Q.append(w) 


if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
E = defaultdict(list)
for i in range(M):
	u, v = rl()
	E[u-1].append(v-1)
S, T = rl()
S -= 1
T -= 1

queue = deque()
queue.append((S,0,0))
visited = set()
while queue:
	n, r, d = queue.popleft()
	if n == T and r == 0:
		print(d//3)
		exit()
	nr = (r+1)%3
	for m in E[n]:
		if (m, nr) in visited: continue
		visited.add((m, nr))
		queue.append((m, nr, d+1))
print(-1)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
E = defaultdict(list)
for i in range(M):
	u, v = rl()
	E[u-1].append(v-1)
S, T = rl()
S -= 1
T -= 1

dp = [[float('inf')]*3 for i in range(N)]

heap = []
heappush(heap, (0, S, 0))
while heap:
	d, n, r = heappop(heap)
	if n == T and r == 0:
		continue
	
	
	nr = (d+1)%3
	for m in E[n]:
		if dp[m][nr] > d+1:
			dp[m][nr] = d+1
			heappush(heap, (d+1, m, nr))

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

Solution (Python):
n,m=map(int,input().split())
g=[[] for _ in range(n)]
gg=[[] for _ in range(3*n)]
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  gg[a].append(n+b)
  gg[n+a].append(2*n+b)
  gg[2*n+a].append(b)
s,t=map(int,input().split())
s,t=s-1,t-1
from collections import deque
todo=deque([s])
seen=[-1]*(3*n)
seen[s]=0
while todo:
  v=todo.popleft()
  for l in gg[v]:
    if seen[l]==-1:
      todo.append(l)
      seen[l]=seen[v]+1
      if l==t:
        print(seen[l]//3)
        exit()
if seen[t]>0:
  print(seen[t]//3)
else:
  print(-1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, p):
        for u in edge_extend[p][v]:
            next_p = 0 if p == 2 else p + 1
            if dist[next_p][u] <= dist[p][v] + 1:
                continue
            else:
                dist[next_p][u] = dist[p][v] + 1
                dfs(u, next_p)

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

    edge_extend = []
    for _ in range(3):
        edge_extend.append(edge)

    dist = [[f_inf] * n for _ in range(3)]
    dist[0][s - 1] = 0
    que = deque([[0, s - 1]])
    while que:
        p, v = que.popleft()
        next_p = 0 if p == 2 else p + 1
        for u in edge_extend[p][v]:
            if dist[next_p][u] > dist[p][v] + 1:
                dist[next_p][u] = dist[p][v] + 1
                que.append([next_p, u])

    print(dist[0][t - 1] // 3 if dist[0][t - 1] != f_inf else -1)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
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())
s -= 1
t -= 1
q = deque([s])
INF = 10**10
dist = [[INF]*3 for _ in range(n)]
dist[s][0] = 0
while q:
    node = q.popleft()
    for c_node in graph[node]:
        flg = False
        for i in range(3):
            nd = dist[node][i]+1
            if dist[c_node][nd%3] > nd:
                dist[c_node][nd%3] = nd
                flg = True
        if flg:
            q.append(c_node)
if dist[t][0]==INF:
    print(-1)
else:
    print(dist[t][0]//3)

Solution (Python):
from collections import deque

n,m=list(map(int,input().split()))
g=[[] for _ in range(10*(n+1)+3)]


for _ in range(m):
    u,v=list(map(int,input().split()))
    g[10*u].append(10*v+1)
    g[10*u+1].append(10*v+2)
    g[10*u+2].append(10*v)

s,t=list(map(int,input().split()))
inf=10**10
q=deque([10*s])
d=[inf]*(10*(n+1)+3)
d[10*s]=0

while len(q)>0:
    u=deque.pop(q)
    res=u%10
    for i in range(3):
        nres=(res+i)%3
        for v in g[u]:
            if d[v]<inf:
                continue
            d[v]=min(d[v],d[u]+1)
            deque.appendleft(q,v)

if d[10*t]==inf:
    print(-1)
else:
    print(d[10*t]//3)

Solution (Python):
from collections import deque
 
N, M = map(int,input().split())
 
edges = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int,input().split())
    edges[u-1].append(v-1)
 
S, T = map(int,input().split())
S -= 1
T -= 1
 
visited = {}
q = deque()
q.append((S, 0))
d = -1
while q:
    s, c = q.popleft()
    if s in visited and (c % 3) in visited[s]:
        continue
    if s not in visited:
        visited[s] = set()
    visited[s].add(c % 3)
    for n in edges[s]:
        if n == T and c % 3 == 2:
            d = c + 1
            break
        q.append((n, c+1))
 
    if d % 3 == 0:
        break
 
if d == -1:
    print(-1)
else:
    print(d//3)