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
N, M = map(int, input().split())

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node
        self.flag = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return "({})".format(self.id)

nodes = [Node(i) for i in range(N+1)]

for ui, vi in (map(int, input().split()) for _ in range(M)):
    Bridge(nodes[ui], nodes[vi])

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


s = [(None, nodes[S], 0)]
idx = 0
isOK = False
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1
    nxtlevel = level + 1
    nxtflag = 1 << (nxtlevel % 3)

    for nxt in cur.bridges:
        if (nxt.flag & nxtflag) == 0:
            nxt.flag |= nxtflag 
            if nxt.node is nodes[T] and nxtflag == 1:
                isOK = True
                break
            s.append((cur, nxt.node, nxtlevel))
    else:
        continue
    break
if isOK:
    print(nxtlevel//3)
else:
    print(-1)

Solution (Python):
import sys
import collections


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    graph = collections.defaultdict(set)
    for _ in range(m):
        u, v = [int(s) for s in sys.stdin.readline().strip().split()]
        graph[u].add(v)
    s, t = [int(s) for s in sys.stdin.readline().strip().split()]

    shortest = dict()
    shortest[s] = 0
    q = collections.deque()
    q.append((0, s, 0))
    seen = dict()
    while q:
        level, loc, turn = q.popleft()
        children = graph[loc]
        child_turn = turn + 1
        child_level = (level+1) % 3
        for child in children:
            if (child_level, child) not in seen:
                if child_level == 0 and child == t:
                    print(child_turn // 3)
                    return
                seen[(child_level, child)] = child_turn
                q.append((child_level, child, child_turn))

    print(-1)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
def main():
    INF = float("inf")
    input = sys.stdin.readline
    N, M = map(int,input().split())
    G = [[] for k in range(N)]
    for k in range(M):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        G[u] += [v]
    S, T = map(int,input().split())
    S -= 1
    T -= 1
    D = [[INF,INF,INF] for k in range(N)]
    D[S][0] = 0
    Q = deque([[S,0]])
    while len(Q) > 0:
        t = Q.popleft()
        ima = t[0]
        k = t[1]
        for tsugi in G[ima]:
            if D[tsugi][(k+1)%3] != INF:
                pass
            else:
                D[tsugi][(k+1)%3] = D[ima][k] + 1
                Q.append([tsugi,(k+1)%3])
    if D[T][0] == INF or D[T][0]%3 != 0:
        print(-1)
    else:
        print(D[T][0]//3)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
MAX= 10**5+5
INF= 10**9
def resolve():
    n,m = map(int,input().split())
    net = [[] for i in range(MAX)]
    vn = [[INF]*3 for i in range(n+1)]
    for i in range(m):
        u,v = map(int,input().split())
        net[u].append(v)
    s,t = map(int,input().split())
    vn[s][0]=0
    q = deque()
    q.appendleft((s,0))
    while q:
        data = q.pop()
        v = data[0]
        l = data[1]
        nl=(l+1)%3
        for u in net[v]:
            if vn[u][nl]==INF:
                vn[u][nl] = vn[v][l]+1
                q.appendleft((u,nl))
    ans = vn[t][0]
    if( ans==INF):
        print(-1)
    else:
        print(ans//3)

if __name__ == "__main__":
    resolve()

Solution (Python):
N, M = [int(c) for c in input().split()]
path = [[] for _ in range(N)]
for i in range(M):
    u, v = [int(c) for c in input().split()]
    path[u-1].append(v-1)

S, T = [int(c)-1 for c in input().split()]

reach = [[-1 for _ in range(N)] for _ in range(3)]
reach[0][S] = 0

queue={S}

time = 1
for _ in range(4*N):
    queue_new = set()
    for q in queue:
        for v in path[q]:
            if reach[time%3][v]==-1:
                reach[time%3][v]=time
                queue_new.add(v)
		
    queue = queue_new
    time += 1

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

Solution (Python):
from collections import deque

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

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

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

visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])

while queue :
    q, cost = queue.popleft()
    p = (cost + 1) % 3
    for i in vec[q] :
        if p == 0 and i == T :
            print((cost + 1) // 3)
            exit()
        if not visited[p][i] :
            visited[p][i] = True
            queue.append((i, cost + 1))

print(-1)

Solution (Python):
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    
    for nxt in dst[v]:
        
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    
    
print(-1)

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

N,M = map(int,input().split())
S = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S[u-1].append(v-1)
St,T = map(int,input().split())

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = deque([St-1,-1])
i = 1
while 1:
    q = queue.popleft()
    if q == -1:
        queue.append(-1)
        i += 1
        if queue == deque([-1]):
            break
    else:
        for j in S[q]:
            if D[j][i%3] > i:
                D[j][i%3] = i
                queue.append(j)
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

Solution (Python):
import sys
import queue

input = sys.stdin.readline

N, M = map(int,input().split())
vy = [list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
s, t = map(lambda x:int(x)-1,input().split())

nlist = [[[] for j in range(3)] for i in range(N)]
for v, y in vy:
    nlist[v][0].append([y,1])
    nlist[v][1].append([y,2])
    nlist[v][2].append([y,0])

visit = [[False]*3 for i in range(N)]

def bfs(visit):
    Q = queue.Queue()
    visit[s][0] = True
    Q.put([[s,0],0])
    while not Q.empty():
        node = Q.get()
        if node[0][0] == t and node[0][1] == 0:
            return node[1]
        for i in nlist[node[0][0]][node[0][1]]:
            if not visit[i[0]][i[1]]:
                visit[i[0]][i[1]] = True
                Q.put([[i[0],i[1]],node[1]+1])
    return -1

ans = bfs(visit)
if visit[t][0]:
    print(ans//3)
else:
    print(ans)

Solution (Python):
n, m = map(int, input().split())
d = {i+1 : [] for i  in range(n)}
for _ in range(m):
    u, v = map(int, input().split())
    d[u].append(v)

visited1 = [False for i in range(n+1)]
visited2 = [False for i in range(n+1)]
visited3 = [False for i in range(n+1)]

s, t = map(int, input().split())
q = set([s])
c = 1
def solve():
    global visited1, visited2,visited3,  c, q
    while True:
        q2 = list(q)
        q = set([])
        for v in q2:
            for e1 in d[v]:
                if visited1[e1]:
                    continue
                visited1[e1] = True
                for e2 in d[e1]:
                    if visited2[e2]:
                        continue
                    visited2[e2] = True
                    for e3 in d[e2]:
                        if visited3[e3]:
                            continue
                        visited3[e3] = True
                        if e3 == t:
                            return c
                        else:
                            q.add(e3)
        if not len(q):
            return -1
        c += 1
print(solve())

Solution (Python):
import heapq, sys
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	
	
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v in self.list[u]:
				if self.dist[v] > u_dist + 1:
					self.dist[v] = u_dist + 1
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

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

d = DijkstraList(adj, s)
d.solve()
ans = d.distance(t)
print(ans//3 if ans != 10**30 else -1)

Solution (Python):
from collections import deque

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

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

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


dist = [-1] * (3*N)
dist[3*(S-1)] = 0
q = deque([3*(S-1)])
while q:
    v = q.popleft()
    d = dist[v]
    Vs = G[v]
    for u in Vs:
        if dist[u] == -1:
            q.append(u)
            dist[u] = d + 1

ans = dist[3*(T-1)]
print(-1 if ans == -1 else ans//3)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
uv = LIR(M)
S, T = LI()
S, T = S-1, T-1

utov = [[] for i in range(N)]

for u, v in uv:
    utov[u-1].append(v-1)


ken1 = deque()
ken2 = deque()
pa = deque()

ken1_used = [False]*N
ken2_used = [False]*N
pa_used = [False]*N

pa.append(S)
pa_used[S] = True

ans = -1

while ken1 or ken2 or pa:
    ans += 1

    while ken1:
        u = ken1.popleft()
        for v in utov[u]:
            if (not ken2_used[v]):
                ken2_used[v] = True
                ken2.append(v)

    while ken2:
        u = ken2.popleft()
        for v in utov[u]:
            if (not pa_used[v]):
                if (v==T):
                    print(ans)
                    quit()
                pa_used[v] = True
                pa.append(v)    

    while pa:
        u = pa.popleft()
        for v in utov[u]:
            if (not ken1_used[v]):
                ken1_used[v] = True
                ken1.append(v)

print(-1)




"""
kenken = []

def bfs(s):
    ret = []
    bfs_map = [-1]*N
    q = deque()
    q.append(s)
    bfs_map[s] = 0
    while q:
        u = q.popleft()
        for v in utov[u]:
            if (edge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (bfs_map[v] == 3):
                    ret.append(v)
                else:
                    q.append(v)
    return ret

for i in range(N):
    ret = bfs(i)
    kenken.append(ret)

kenkenedge = [[0]*N for i in range(N)]
for u, vs in enumerate(kenken):
    for v in vs:
        kenkenedge[u][v] = 1

def bfs_dist(S, T):
    bfs_map = [-1]*N
    q = deque()
    q.append(S)
    bfs_map[S] = 0
    while q:
        u = q.popleft()
        for v in kenken[u]:
            if (kenkenedge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (v==T):
                    return bfs_map[T]
                else:
                    q.append(v)
    return -1

print(bfs_dist(S, T))
"""

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
uv = LIR(M)
S, T = LI()
S, T = S-1, T-1

utov = [[] for i in range(N)]

for u, v in uv:
    utov[u-1].append(v-1)


ken1 = deque()
ken2 = deque()
pa = deque()

ken1_used = [False]*N
ken2_used = [False]*N
pa_used = [False]*N

pa.append(S)
pa_used[S] = True

ans = -1

while ken1 or ken2 or pa:
    ans += 1

    while ken1:
        u = ken1.popleft()
        for v in utov[u]:
            if (not ken2_used[v]):
                ken2_used[v] = True
                ken2.append(v)

    while ken2:
        u = ken2.popleft()
        for v in utov[u]:
            if (not pa_used[v]):
                if (v==T):
                    print(ans)
                    quit()
                pa_used[v] = True
                pa.append(v)    

    while pa:
        u = pa.popleft()
        for v in utov[u]:
            if (not ken1_used[v]):
                ken1_used[v] = True
                ken1.append(v)

print(-1)




"""
kenken = []

def bfs(s):
    ret = []
    bfs_map = [-1]*N
    q = deque()
    q.append(s)
    bfs_map[s] = 0
    while q:
        u = q.popleft()
        for v in utov[u]:
            if (edge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (bfs_map[v] == 3):
                    ret.append(v)
                else:
                    q.append(v)
    return ret

for i in range(N):
    ret = bfs(i)
    kenken.append(ret)

kenkenedge = [[0]*N for i in range(N)]
for u, vs in enumerate(kenken):
    for v in vs:
        kenkenedge[u][v] = 1

def bfs_dist(S, T):
    bfs_map = [-1]*N
    q = deque()
    q.append(S)
    bfs_map[S] = 0
    while q:
        u = q.popleft()
        for v in kenken[u]:
            if (kenkenedge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (v==T):
                    return bfs_map[T]
                else:
                    q.append(v)
    return -1

print(bfs_dist(S, T))
"""

Solution (Python):
import heapq, sys
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	
	
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v in self.list[u]:
				if self.dist[v] > u_dist + 1:
					self.dist[v] = u_dist + 1
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

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

d = DijkstraList(adj, s)
d.solve()
ans = d.distance(t)
print(ans//3 if ans != 10**30 else -1)

Solution (Python):
N, M = [int(i) for i in input().split()]
E = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = [int(i) - 1 for i in input().split()]
    E[3 * u].append(3 * v + 1)
    E[3 * u + 1].append(3 * v + 2)
    E[3 * u + 2].append(3 * v)
S, T = [3 * (int(i) - 1) for i in input().split()]

from collections import deque
Q = deque()
Q.append((S, 0))

visited = [False] * (3 * N)
visited[S] = True

ans = -1
while Q:
    a, d = Q.popleft()
    if a == T:
        ans = d
        break
    for b in E[a]:
        if not visited[b]:
            Q.append((b, d + 1))
            visited[b] = True

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

Solution (Python):
import copy
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s,t=map(int,input().split())

connection=[[] for i in range(3*n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1+n)
  connection[l[i][0]-1+n].append(l[i][1]-1+2*n)
  connection[l[i][0]-1+2*n].append(l[i][1]-1)
distance=[-1 for i in range(3*n)]
distance[s-1]=0
L=[s-1]
L2=[]
L3=[]
ct=1
while len(L2)!=3*n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      if distance[connection[L[j]][k]]==-1:
        distance[connection[L[j]][k]]=ct
        L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
if distance[t-1]==-1:
  print(-1)
else:
  x=distance[t-1]-distance[s-1]
  if x%3==0:
    print(x//3)
  else:
    print(-1)

Solution (Python):
from collections import defaultdict
from queue import Queue

n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [[MX, MX, MX] for i in range(n)]
reached = [[False, False, False] for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s][0] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        reached[next_node][next_step] = True
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

if dist[t][0] == MX:
    print(-1)
else:
    print(dist[t][0])

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

n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n*3)]
for i in range(m):
    u, v = [int(item) for item in input().split()]
    u -= 1; v -= 1
    edge[u*3].append(v*3 + 1)
    edge[u*3 + 1].append(v*3 + 2)
    edge[u*3 + 2].append(v*3)
s, t = [int(item) for item in input().split()]
s -= 1; t -= 1

distance = [INF] * (n * 3)
dq = deque()
dq.append([0, s*3])
while(dq):
    dist, node = dq.popleft()
    if len(edge[node]) == 0:
        distance[node] = dist 
        continue
    if distance[node] != INF:
        continue
    distance[node] = dist 
    dist += 1
    for item in edge[node]:
        dq.append([dist, item])
if distance[t*3] == INF:
    print(-1)
else:
    print((distance[t*3]) // 3)

Solution (Python):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = [False] * (3*N+1)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)

Solution (Python):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = defaultdict(bool)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)

Solution (Python):
from heapq import heappop, heappush

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

INF = 10 ** 15

dd = [[INF, INF, INF] for _ in range(n)]
visited = [[False, False, False] for _ in range(n)]

s, t = map(int, input().split())
s -= 1
t -= 1
dd[s] = [0, 0, 0]
q = [(0, s)]
ans = -1

while q:
    d, v = heappop(q)
    if visited[v][d%3]:
        continue
    visited[v][d%3] = True
    if v == t and d % 3 == 0:
        ans = d//3
        break
    to_d = d+1
    for to_v in MAP[v]:
        if visited[to_v][to_d % 3]:
            continue
        heappush(q, (to_d, to_v))

print(ans)

Solution (Python):
from collections import deque


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


repn = [[[] for l in range(3)] for u in range(N)]
for j in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    repn[a][0].append((b, 1))
    repn[a][1].append((b, 2))
    repn[a][2].append((b, 0))


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










color = [['WHITE' for l in range(3)] for u in range(N)]
d = [[-1, -1, -1] for u in range(N)]
Q = deque([])

color[s][0] = 'GRAY'
d[s][0] = 0
Q.append((s, 0))

while len(Q) != 0:
    u, l = Q.popleft()
    for x in repn[u][l]:
        v, r = x
        if color[v][r] == 'WHITE':
            color[v][r] = 'GRAY'
            d[v][r] = d[u][l] + 1
            Q.append(x)
    color[u][l] = 'BLACK'

print(d[t][0] // 3)

Solution (Python):
from collections import deque


def bfs(graph, start, end):
    queue = deque([start])
    visited = [-1] * len(graph)
    visited[start] = 0
    while queue:
        pos = queue.popleft()
        if pos == end: return visited[pos]
        for next_pos in graph[pos]:
            if visited[next_pos] == -1:
                visited[next_pos] = visited[pos] + 1
                queue.append(next_pos)
    return -1

def solve():
    N, M = map(int, input().split())
    graph = [[] for i in range(N * 3)]
    for i in range(M):
        u, v = map(lambda s: int(s) - 1, input().split())
        graph[N * 0 + u].append(N * 1 + v)
        graph[N * 1 + u].append(N * 2 + v)
        graph[N * 2 + u].append(N * 0 + v)
    S, T = map(lambda s: int(s) - 1, input().split())
    dist = bfs(graph, S, T)
    return dist // 3 if dist != -1 else -1


print(solve())

Solution (Python):
from collections import deque
import sys
inputs = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,inputs().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[] for i in range(3*N)]
for u,v in UV:
    es[u].append(v+N)
    es[u+N].append(v+2*N)
    es[u+2*N].append(v)

q = deque([S])
INF = float('inf')
dist = [INF] * (3*N)
dist[S] = 0

while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] != INF: continue
        dist[to] = dist[v] + 1
        if to==T:
            print(dist[to] // 3)
            exit()
        q.append(to)
print(-1)

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

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

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

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

DIS=[[-1,-1,-1] for i in range(N+1)]
DIS[S][0]=0

from collections import deque

S=deque([S])
i=1

while S:
    
    NEWS=deque()
    while S:     
        x=S.pop()

        for to in ELIST[x]:
            if DIS[to][i%3]==-1:
                DIS[to][i%3]=i
                NEWS.append(to)

    i+=1
    S=NEWS

print(DIS[G][0]//3)

Solution (Python):
N, M = map(int, input().split())

to = [[] for _ in range(N)]
dist = [[0 for _ in range(3)] for _ in range(100005)]
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  to[a].append(b)

sv, tv = map(int, input().split())
sv -= 1
tv -= 1

for i in range(N):
  for j in range(3):
    dist[i][j] = float("inf")
q = [[sv, 0]]
dist[sv][0] = 0
while len(q) != 0:
  v = q[0][0]
  l = q[0][1]
  q.pop(0)
  for u in to[v]:
    nl = (l + 1) % 3
    if dist[u][nl] != float("inf"):
      continue
    dist[u][nl] = dist[v][l] + 1
    q.append([u, nl])
ans = dist[tv][0]
if ans == float("inf"):
  ans = -1
else:
  ans //= 3
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if j==t:
                         print(cnt//3)
                         return
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
                         
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N, M = map(int, input().split())

X = [[] for i in range(N*3)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y+N-1)
    X[x+N-1].append(y+N*2-1)
    X[x+N*2-1].append(y-1)

S, T = map(int, input().split())
S -= 1
T -= 1
Q = deque([S])
D = [999999] * N * 3

D[S] = 0
while Q:
    x = Q.popleft()
    for c in X[x]:
        if D[c] == 999999:
            D[c] = D[x]+1
            Q.append(c)
print(-1 if D[T] == 999999 else D[T]//3)

Solution (Python):
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N*3)]
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].add(N*1+v)
        adj[N*1+u].add(N*2+v)
        adj[N*2+u].add(v)
    S, T = map(int, input().split())
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost//3)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()