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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = LI()
    G[x - 1] += [y - 1]

dist = [[INF] * n for _ in range(3)]
s, t = LI()
dist[0][s - 1] = 0
dq = deque([(0, s - 1)])
while dq:
    cost, u = dq.popleft()
    for v in G[u]:
        if cost + 1 < dist[(cost + 1) % 3][v]:
            dist[(cost + 1) % 3][v] = cost + 1
            dq += [(cost + 1, v)]


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

Solution (Python):
from collections import deque
import sys
n,m=map(int,input().split())
g=[[] for _ in range(3*n)]
for _ in range(m):
  u,v=map(int, sys.stdin.readline().split())
  u-=1
  v-=1
  g[u].append(n+v)
  g[u+n].append(v+2*n)
  g[u+2*n].append(v)
s,t=map(int,input().split())
s-=1
t-=1
vit=set([s])
ans=[-3]*3*n
q=deque([s])
ans[s]=0
while q:
  a=q.popleft()
  for b in g[a]:
    if b in vit:
      continue
    vit.add(b)
    ans[b]=ans[a]+1 
    q.append(b)
print(ans[t]//3)

Solution (Python):
import sys
from collections import deque

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

Edge = [[] for _ in range(3*N)]

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    u -= 1
    v -= 1
    Edge[u].append(N + v)
    Edge[N + u].append(2*N + v)
    Edge[2*N + u].append(v)

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

Q = deque([S])
visited = set([S])
dist = [-3]*(3*N)
dist[S] = 0


while Q:
    vn = Q.pop()
    for vf in Edge[vn]:
        if vf in visited:
            continue
        visited.add(vf)
        dist[vf] = dist[vn] + 1
        Q.appendleft(vf)

print(dist[T]//3)

Solution (Python):

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int, input().split( ))
Ad = [[[] for _ in range(3)] for i in range(n)]


for i in range(m):
    ui,vi = map(int,input().split( ))
    ui -= 1
    vi -= 1
    Ad[ui][0].append((vi,1))
    Ad[ui][1].append((vi,2))
    Ad[ui][2].append((vi,0))


s,t = map(int, input().split( ))
s -= 1
t -= 1
Q = deque()
Q.append((s,0))
Visit = [[-1 for _ in range(3)] for i in range(n)]
Visit[s][0] = 0
while Q:
    v,i = Q.popleft()
    for u,j in Ad[v][i]:
        if Visit[u][j]<0:
            Visit[u][j] = Visit[v][i] + 1
            Q.append((u,j))
        if u==t and j==0:
            Q.clear()
            break

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

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

n, m = map(int, input().split())
INF = 10**9
to = [ [] for _ in range(n) ]
dist = [ [INF]*n for _ in range(3) ]
for _ in range(m):
    u, v = map(int, input().split())
    to[u-1].append(v-1)
s, t = map(int, input().split())
s -= 1; t -= 1

dist[0][s] = 0
que = deque([(s, 0)])
while que:
    u, prv = que.popleft()
    d = dist[prv][u]
    cur = (prv+1) % 3
    if prv == 2:
        d += 1
    for v in to[u]:
        if dist[cur][v] != INF:
            continue
        que.append((v, cur))
        dist[cur][v] = d
print( dist[0][t] if dist[0][t] < INF else -1 )

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    
    from collections import deque
    d=[-1]*(3*n)
    d[3*s]=0
    Q=deque()
    Q.append(3*s)
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(d[nv]!=-1): continue
            d[nv]=d[v]+1
            Q.append(nv)
    ans=d[3*t]
    print(ans//3 if(ans!=-1) else -1)
resolve()

Solution (Python):
from collections import deque
N,M = map(int,input().split())
node = [[10**9]*3 for i in range(N)]
KENPA = 3
side = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    side[u-1].append(v-1)
S,T = map(int,input().split())
node[S-1][2] = 0
queue = deque([[S-1,2]])
while queue:
    x,y = queue.popleft()
    y2 = (y+1)%KENPA
    for i in side[x]:
        if node[i][y2] > node[x][y]+1:
            node[i][y2] = node[x][y]+1
            queue.append([i,y2])
if node[T-1][2] == 10**9:
    print(-1)
else:
    print(node[T-1][2] // 3)

Solution (Python):
import collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,input().split())
dp = [[-3 for _ in range(3)] for _ in range(N)]
dp[S-1][0] = 0
q = collections.deque()
q.append((S-1,0))
while q:
    p,step = q.popleft()
    next_step = (step+1)%3
    for e in edge[p]:
        if dp[e][next_step] == -3:
            dp[e][next_step] = dp[p][step] + 1
            q.append((e,next_step))
            if e == T-1 and next_step == 0:
                break
print(dp[T-1][0] // 3)

Solution (Python):
from collections import deque
def bfs(n,e,fordfs):
    
    W = [-1]*n
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if W[ne] == -1:
                W[ne] = nowv+1
                len[ne] = nowlen+1
                que.append(ne)
    return W


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
V = [[] for i in range(3*N)]

for i in range(M):
    u, v = LI()
    V[u-1].append(N+v-1)
    V[N+u-1].append(2*N+v-1)
    V[2*N+u-1].append(v-1)
cou = []
S, T = LI()


cou = bfs(3*N, S-1, V)

ans = cou[T-1]//3
print(ans)

Solution (Python):
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue








def main():
    n, m = map(int, raw_input().split())
    G = [[] for i in range(n+1)]
    ss = set()
    for i in range(m):
        a, b = map(int, raw_input().split())
        G[a].append(b)
    s, t = map(int, raw_input().split())
    t = t<<2
    q = deque()
    q.append((s<<2, 0))
    ss.add(s<<2)
    while q:
        st, step = q.popleft()
        point, mod = st>>2, st&3
        
        if st == t:
            print step/3
            return

        for adj in G[point]:
            new_st = (adj<<2) + (mod+1)%3
            if new_st not in ss:
                ss.add(new_st)
                q.append((new_st, step+1))
    print -1

main()

Solution (Python):
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue








def main():
    n, m = map(int, raw_input().split())
    G = [[] for i in range(n+1)]
    ss = set()
    for i in range(m):
        a, b = map(int, raw_input().split())
        G[a].append(b)
    s, t = map(int, raw_input().split())
    t = t<<2
    q = deque()
    q.append((s<<2, 0))
    ss.add(s<<2)
    while q:
        st, step = q.popleft()
        point, mod = st>>2, st&3
        
        if st == t:
            print step/3
            return

        for adj in G[point]:
            new_st = (adj<<2) + (mod+1)%3
            if new_st not in ss:
                ss.add(new_st)
                q.append((new_st, step+1))
    print -1

main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*UV,S,T = map(int,read().split())

it = iter(UV)
G = [[] for _ in range(1+N+N+N)]
for x, y in zip(it, it):
    x1=x+N; x2=x1+N;
    y1=y+N; y2=y1+N;
    G[x].append(y1)
    G[x1].append(y2)
    G[x2].append(y)

INF = 10 ** 15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in G[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
            if y == T:
                break
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

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

adj = [list() for _ in range(N)]


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

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

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

for step in count(1):
    offset = N*(step % 3)
    nq = []
    for u in q:
        for v in adj[u]:
            if not visited[v+offset]:
                nq.append(v)
                visited[v+offset] = True
    q = nq

    if visited[T] or not q:
        break
if visited[T]:
    print(step//3)
else:
    print(-1)

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

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

Q=deque()
Q.append(s*3)
D=[-3 for _ in range(3*(n+1))]
D[s*3]=0

while Q:
    q=Q.popleft()
    for i in G[q]:
        if D[i]==-3:
            D[i]=D[q]+1
            Q.append(i)

print(D[t*3]//3)

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

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

graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
S, T = map(lambda x:int(x)-1, input().split())


q = {S}
checked = [False]*N
checked[S] = True

ok = False
c = 0
while q:
    c += 1
    qq = set()
    if c % 3 == 0:
        for p in q:
            for np in graph[p]:
                if np == T:
                    ok = True
                    break
                if not checked[np]:
                    qq.add(np)
                    checked[np] = True
    else:
        for p in q:
            for np in graph[p]:
                qq.add(np)
    if ok:
        break
    q = qq

if ok:
    print(c//3)
else:
    print(-1)

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

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

graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
S, T = map(lambda x:int(x)-1, input().split())


q = {S}
checked = [False]*N
checked[S] = True

ok = False
c = 0
while q:
    c += 1
    qq = set()
    if c % 3 == 0:
        for p in q:
            for np in graph[p]:
                if np == T:
                    ok = True
                    break
                if not checked[np]:
                    qq.add(np)
                    checked[np] = True
    else:
        for p in q:
            for np in graph[p]:
                qq.add(np)
    if ok:
        break
    q = qq

if ok:
    print(c//3)
else:
    print(-1)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict
import queue


def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, S, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.dist = [INF] * N
		self.visit = ["No"] * N
		self.Q.put(S)
		self.dist[S] = 0
		self.visit[S] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"


def main():
	
	N, M = getlist()
	G = Graph()
	for i in range(M):
		u, v = getlist()
		G.add_edge(u - 1, v - 1 + N)
		G.add_edge(u - 1 + N, v - 1 + 2 * N)
		G.add_edge(u - 1 + 2 * N, v - 1)

	S, T = getlist()
	S -= 1
	T -= 1
	
	BF = BFS(G, S, 3 * N)
	D = BF.dist
	if D[T] == INF:
		print(-1)
	else:
		print(D[T] // 3)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*UV,S,T = map(int,read().split())

it = iter(UV)
graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(it,it):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in graph[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
            if y == T:
                break
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,*UV,S,T = map(int,read().split())

it = iter(UV)
graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(it,it):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in graph[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
UVST = list(map(int,read().split()))
S,T = UVST[-2:]
UV = UVST[:-2]; U = UV[::2]; V = UV[1::2]

graph = [[] for _ in range(1+N+N+N)]
for x,y in zip(U,V):
    x1=x+N; x2=x1+N
    y1=y+N; y2=y1+N
    graph[x].append(y1)
    graph[x1].append(y2)
    graph[x2].append(y)   

INF = 10**15
dist = [INF] * (N+N+N+1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in graph[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Solution (Python):
N,M = map(int, input().split())
L = [[int(u) for u in input().split()] for i in range(M)]
S,T = map(int, input().split())

edge = [[] for i in range(N+1)]
for i in range(M):
    edge[L[i][0]].append(L[i][1])
    
q = [S]
INF = 10**9
visited = [[INF+1, INF+1, INF+1] for i in range(N+1)]
visited[S][0] = 0
cnt = 1
while len(q) > 0:
    length = len(q)
    for j in range(length):
        temp = q.pop(0)
        for i in range(len(edge[temp])):
            if visited[edge[temp][i]][cnt%3] > INF:
                q.append(edge[temp][i])
                visited[edge[temp][i]][cnt%3] = cnt
    cnt += 1
    
if visited[T][0] < INF:
    print(visited[T][0]//3)
else:
    print(-1)

Solution (Python):
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)

def bfs(v):
  distance=[-1]*(3*n)
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*(3*n)
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=3*n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

if bfs(s-1)[t-1]==-1 or bfs(s-1)[t-1]%3!=0:
  print(-1)
else:
  print(bfs(s-1)[t-1]//3)

Solution (Python):
N, M = [int(x) for x in input().strip().split(" ")]
from collections import deque
vs = set()
def bfs(v,d,t,N):
    queue=deque([v])
    dist = [0] * (N+1)
    while True:
        if len(queue) == 0:
            break
        v = queue.popleft()
        for u in d[v]:
            if u in vs:
                continue
            vs.add(u)
            dist[u] = dist[v] + 1
            if u == t:
                return dist[u]//3
            queue.append(u)
    return -1

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(bfs(s, d, t, 3*N+1))

Solution (Python):
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    s,e=map(int,input().split())
    graph[s-1].append(e+n-1)
    graph[s+n-1].append(e+2*n-1)
    graph[s+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
queue=deque([s])
length=0
dist=[-1]*(3*n)
dist[s]=0
while queue:
    v=queue.popleft()
    for i in graph[v]:
        if dist[i]!=-1:continue
        dist[i]=dist[v]+1
        queue.append(i)
print(dist[t]//3)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    s,e=map(int,input().split())
    graph[s-1].append(e+n-1)
    graph[s+n-1].append(e+2*n-1)
    graph[s+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
queue=deque([s])
length=0
dist=[-1]*(3*n)
dist[s]=0
while queue:
    v=queue.popleft()
    for i in graph[v]:
        if dist[i]!=-1:continue
        dist[i]=dist[v]+1
        queue.append(i)
print(dist[t] if dist[t]==1 else dist[t]//3)

Solution (Python):
def main():
	from collections import deque
	N,M,*L,S,T = map(int,open(0).read().split())
	G = [[] for _ in range(N)]
	step = [False]*(3*N)
	step[(S-1)*3] = True
	for u,v in zip(*[iter(L)]*2):
		G[u-1].append(v-1)
	q = deque([(S-1,0)])
	while q:
		cur,d = q.popleft()
		for nxt in G[cur]:
			if nxt==T-1 and (d+1)%3==0:
				print((d+1)//3)
				exit()
			if not step[nxt*3+(d+1)%3]:
				step[nxt*3+(d+1)%3] = True
				q.append((nxt,d+1))
	print(-1)
	
if __name__=="__main__":main()

Solution (Python):
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [0 for _ in range(N)]
step[S-1] = 1
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if not step[nxt] & 1<<((d+1)%3):
			step[nxt] |= 1<<(d+1)%3
			q.append((nxt,d+1))
print(-1)

Solution (Python):
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [False for _ in range(3*N)]
step[(S-1)*3] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if not step[nxt*3+(d+1)%3]:
			step[nxt*3+(d+1)%3] = True
			q.append((nxt,d+1))
print(-1)

Solution (Python):
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [[-1]*3 for _ in range(N)]
step[S-1][0] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if step[nxt][(d+1)%3] < 0:
			step[nxt][(d+1)%3] = d+1
			q.append((nxt,d+1))
print(-1)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[] for _ in range(n)]
for u, v in LIR(m):
    graph[u - 1] += [v - 1]


s, t = LI()
dist = [[INF for _ in range(3)] for _ in range(n)]
dist[s - 1][0] = 0
que = deque([(s - 1, 0)])
while que:
    cur, cost = que.popleft()
    for nxt in graph[cur]:
        if cost + 1 < dist[nxt][(cost + 1) % 3]:
            dist[nxt][(cost + 1) % 3] = cost + 1
            que += [(nxt, cost + 1)]



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

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

g = [set() for _ in range(3 * n)]

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].add(n + b)
    g[n+a].add(n*2 + b)
    g[n*2+a].add(b)



s -= 1
t -= 1
ans = 0
temp = set()
temp.add(s)
while 1:
    ans += 1
    next = set()
    for x in temp:
        for y in g[x]:
            next.add(y)
        g[x] = []
    if len(next) == 0:
        print(-1)
        exit()
    if t in next:
        print(ans // 3)
        exit()
    temp = next

Solution (Python):
import sys
from heapq import heappop, heappush
input = sys.stdin.readline


class Data :
    def __init__():
        pass
    def __init__(self, pos, step, cost):
        self.pos = pos
        self.step = step
        self.cost = cost
    def __lt__(self, right):
        return self.cost < right.cost

def dijkstra(N, S, T, edges):
    inf = 10 ** 9 + 7
    dis = []
    for i in range(N + 1):
        dis.append([inf, inf, inf])

    que = []
    dis[S][0] = 0
    heappush(que, Data(S, 0, 0))
    while (len(que)):
        now_d = heappop(que)
        if dis[now_d.pos][now_d.step] < now_d.cost:
            continue

        for edge in edges[now_d.pos] :
            next_d = Data(edge[0], (now_d.step + 1) % 3, now_d.cost + edge[1])
            if dis[next_d.pos][next_d.step] > next_d.cost:
                dis[next_d.pos][next_d.step] = next_d.cost
                heappush(que, next_d)
    
    if (dis[T][0] == 10 ** 9 + 7):
        return -1
    else :
        return dis[T][0] // 3

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

Solution (Python):
import sys
from heapq import heappop, heappush
input = sys.stdin.readline


class Data :
    def __init__():
        pass
    def __init__(self, pos, step, cost):
        self.pos = pos
        self.step = step
        self.cost = cost
    def __lt__(self, right):
        return self.cost < right.cost

def dijkstra(N, S, T, edges):
    inf = 10 ** 9 + 7
    dis = []
    for i in range(N + 1):
        dis.append([inf, inf, inf])

    que = []
    dis[S][0] = 0
    heappush(que, Data(S, 0, 0))
    while (len(que)):
        now_d = heappop(que)
        if dis[now_d.pos][now_d.step] < now_d.cost:
            continue

        for edge in edges[now_d.pos] :
            next_d = Data(edge[0], (now_d.step + 1) % 3, now_d.cost + edge[1])
            if dis[next_d.pos][next_d.step] > next_d.cost:
                dis[next_d.pos][next_d.step] = next_d.cost
                heappush(que, next_d)
    
    if (dis[T][0] == 10 ** 9 + 7):
        return -1
    else :
        return dis[T][0] // 3

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

Solution (Python):


import sys
from collections import deque, defaultdict
import copy
import bisect

import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


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

graph = [[] for _ in range(3*N)]

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

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)

Solution (Python):
n,m = map(int,input().split())
pst = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  pst[a].append(b)
s,t = map(int,input().split())
s -= 1
t -= 1
cnt = [[0,0,0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
  time += 1
  last = now
  now = []
  for x in last:
    for y in pst[x]:
      if cnt[y][time%3] == 0:
        cnt[y][time%3] = 1
        now.append(y)
  
  if cnt[t][0] == 1:
    print(time//3)
    break
else:
  print(-1)

Solution (Python):
n,m = map(int,input().split())
pst = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  pst[a].append(b)
s,t = map(int,input().split())
s -= 1
t -= 1
cnt = [[0,0,0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
  time += 1
  last = now
  now = []
  for x in last:
    for y in pst[x]:
      if cnt[y][time%3] == 0:
        cnt[y][time%3] = 1
        now.append(y)
  
  if cnt[t][0] == 1:
    print(time//3)
    break
else:
  print(-1)

Solution (Python):
from collections import deque
import sys

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

edges = [[] for _ in range(n + 1)]

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

s, t = list(map(int, input().split()))
visited = [[] for _ in range(n + 1)]

q = deque()
q.append((s, 0))

while q:
	node, cnt = q.popleft()

	if cnt % 3 in visited[node]:
		continue
	
	if node == t and cnt % 3 == 0:
		print(cnt // 3)
		sys.exit()
	
	else:
		visited[node].append(cnt % 3)
		for e in edges[node]:
			q.append((e, cnt + 1))
	
print(-1)

Solution (Python):
from collections import deque
import sys

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

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

for _ in range(m):
	u, v = list(map(int, input().split()))
	edges[u][0].append((v, 1))
	edges[u][1].append((v, 2))
	edges[u][2].append((v, 0))

s, t = list(map(int, input().split()))
visited = [[[] for _ in range(3)] for _ in range(n + 1)]

q = deque()
q.append((s, 0, 0))

while q:
	node, div, cnt = q.popleft()

	if visited[node][div] == 1:
		continue
	
	if (node, div) == (t, 0):
		print(cnt // 3)
		sys.exit()
	
	else:
		visited[node][div] = 1
		for e in edges[node][div]:
			q.append((e[0], e[1], cnt + 1))
	
print(-1)

Solution (Python):
from collections import defaultdict
import queue

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

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

graph = defaultdict(list)

for edge in edges:
	u, v = edge
	graph[u].append(v + n)
	graph[u + n].append(v + 2*n)
	graph[u + 2*n].append(v)

def bfs(s, t, graph):
	vis_set = set()
	dist = defaultdict(lambda: int(-1))
	dist[s] = 0
	que = queue.Queue()
	que.put(s)
	vis_set.add(s)	

	while not que.empty():
		vert = que.get()
		for nxt in graph[vert]:
			if nxt not in vis_set:
				dist[nxt] = dist[vert] + 1
				vis_set.add(nxt)
				que.put(nxt)
				if nxt == t:
					return dist[nxt]//3
	return -1
ans = bfs(s, t, graph)
print(ans)

Solution (Python):
N,M = map(int, input().split())
g = {}
for v in range(1,N*3+1):
    g[v] = []

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

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

visiting = [S]
visited = {S:0}
while visiting:
    v = visiting.pop(0)
    if v == T:
        break

    for v2 in g[v]:
        if v2 not in visited:
            visiting.append(v2)
            visited[v2] = visited[v]+1

if T in visited:
    print(visited[T] // 3)
else:
    print(-1)

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

q = []
q.append(S)
while q:
    n = q.pop(0)
    if n == T:
        break
    for t in E[n]:
        if dist[t-1] < 0:
            dist[t-1] = dist[n-1] + 1
            q.append(t)
print(-1 if dist[T-1] < 0 else dist[T-1] // 3)