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

class Dijkstra():
    class Edge():
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]  
        self._E = 0  
        self._V = V  
    @property
    def E(self):
        return self._E
    @property
    def V(self):
        return self._V
    def add(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
    def shortest_path(self, s):
        import heapq
        que = []  
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  
        while len(que) != 0:
            cost, v = heapq.heappop(que)
            
            if d[v] < cost: continue
            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
        return d

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

djk=Dijkstra(3*n+1)
for u,v in uv:
	djk.add(u,v+n,1)
	djk.add(u+n,v+n*2,1)
	djk.add(u+n*2,v,1)
d = djk.shortest_path(s)
print(d[t]//3 if d[t]!=float("inf") else -1)

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
E = defaultdict(list)
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())
R = [-1 for _ in range(3*N)]
R[S-1] = 0

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

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

UV = []
for _ in range(M):
    u, v = map(int, input().split())
    UV.append((u, v))
    
S, T = map(int, input().split())

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: 
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    
    return [0 if x is None else x for x in A]

from collections import defaultdict
graph = defaultdict(lambda: {})

for a,b in UV:
    graph[a][b+N] = 1
    graph[a+N][b+N*2] = 1
    graph[a+N*2][b] = 1
    
shortest = dijkstra(graph, S, N*3)

if shortest[T] % 3 == 0 and shortest[T] != 0:
    print(shortest[T]//3)
else:
    print(-1)

Solution (Python):
def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

N,M = map(int,input().split())
UV = [list(map(int,input().split())) for _ in [0]*M]
S,T = map(int,input().split())

S-=1;T-=1
E = [[] for _ in [0]*3*N]
for u,v in UV:
    u-=1;v-=1
    for i in range(3):
        v = (v+N)%(3*N)
        E[u+i*N].append(v)

print(dist_bfs(3*N,E,S)[T]//3)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    G[3 * u + 0].append(3 * v + 1)
    G[3 * u + 1].append(3 * v + 2)
    G[3 * u + 2].append(3 * v + 0)
S, T = map(int, input().split())
S, T = S - 1, T - 1
INF = float('inf')
d = [INF] * (3 * N)
d[3 * S] = 0


que = deque([3 * S])
while que:
    u = que.popleft()
    for w in G[u]:
        if d[w] == INF:
            d[w] = d[u] + 1
            que.append(w)


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

Solution (Python):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
edge=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  for j in range(3):
    edge[u-1+j*n].append([1,(v-1+(j+1)*n)%(3*n)])
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*(3*n)
  used=[True]*(3*n)
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d
s,t=map(int,input().split())
ans=dijkstra_heap(s-1)[t-1]
print(ans//3 if ans%3==0 else -1)

Solution (Python):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
edge=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  for j in range(3):
    edge[u-1+j*n].append([1,(v-1+(j+1)*n)%(3*n)])
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*(3*n)
  used=[True]*(3*n)
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d
s,t=map(int,input().split())
ans=dijkstra_heap(s-1)[t-1]
print(ans//3 if ans%3==0 else -1)

Solution (Python):


import sys
input = sys.stdin.readline
N, M = map(int, input().split())


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

INF = 10 ** 9
used1 = [INF] * (N + 1) 
used2 = [INF] * (N + 1) 
used3 = [INF] * (N + 1) 

def solve(s): 
    from collections import deque
    used3[s] = 0
    
    
    from1 = deque() 
    from2 = deque() 
    from3 = deque() 

    f1append = from1.append
    f2append = from2.append
    f3append = from3.append

    f1pop = from1.popleft
    f2pop = from2.popleft
    f3pop = from3.popleft

    for i in edge[s]:
        
        f3append(i)

    
    count = 0
    while from1 or from2 or from3: 
        count += 1
        
        for _ in range(len(from3)):
            
            v = f3pop()
            if used1[v] == INF:
                used1[v] = count
                for i in edge[v]:
                    f1append(i)
        
        for _ in range(len(from1)): 
            
            v = f1pop()
            if used2[v] == INF:
                used2[v] = count
                for i in edge[v]:
                    f2append(i)
        
        for _ in range(len(from2)):
            
            v = f2pop()
            if used3[v] == INF:
                used3[v] = count
                for i in edge[v]:
                    f3append(i)
        
    return


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

solve(S)




if used3[T] == INF:
    print (-1)
else:
    print (used3[T])

Solution (Python):
from collections import deque
N, M = map(int, input().split())
R = [[] for i in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    R[a].append(b)
S,T = map(int, input().split())
answer = -1
queue =  deque()
queue.append([S,0])
visited = {}
visited[S] = 1
visited2 = {}
while queue != deque():
    tmp = queue.popleft()
    if tmp[0] == T:
        answer = tmp[1]
        break
    tmp_queue = deque()
    tmp_queue.append(tmp[0])
    for i in range(3):
        tmp2_queue = tmp_queue
        tmp_queue = deque()
        for j in tmp2_queue:
            if (j, i) in visited2:
                continue
            else:
                visited2[j,i] = 1
                tmp_queue += R[j]
    for i in tmp_queue:
        if i in visited:
            continue
        else:
            visited[i] = 1
            queue.append([i,tmp[1]+1])
            
print(answer)

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

INF = float('inf')

def bfsMinCosts(adjList, vSt):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = 0
    Q = deque([vSt])
    while Q:
        vNow = Q.popleft()
        cNow = costs[vNow]
        for v2 in adjList[vNow]:
            if costs[v2] == INF:
                costs[v2] = cNow + 1
                Q.append(v2)
    return costs

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

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

costs = bfsMinCosts(adjL, 3*S+0)

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

Solution (Python):
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

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

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

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

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

while d:
    next_node = d.pop()
    for v in e[next_node]:
        if(dist[v] > dist[next_node] + 1):
            dist[v] = dist[next_node] + 1
            if(v == (T, 0)):
                break
            d.appendleft(v)

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

Solution (Python):
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

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

Solution (Python):
from collections import deque

inf = float('inf')

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

g = [set() for _ in range(n * 3)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].add(v + n)
    g[u + n].add(v + n * 2)
    g[u + n * 2].add(v)

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

dq = deque()
dq.append(s)

dist = [inf] * (n * 3)
dist[s] = 0
while dq:
    v = dq.popleft()
    if v == t:
        break
    for u in g[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

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

Solution (Python):
def add_edge(s, d, edges):
    if s in edges:
        edges[s].append(d)
    else:
        edges[s] = [d]


N, M = [int(x) for x in input().split()]
edges = {}
for _ in range(M):
    s, d = [int(x) for x in input().split()]
    add_edge(s*3 + 0, d*3 + 1, edges)
    add_edge(s*3 + 1, d*3 + 2, edges)
    add_edge(s*3 + 2, d*3 + 0, edges)
S, T = [int(x)*3 + 0 for x in input().split()]

reached = set()
curs = [S]
count = 0
success = False

while curs:
    if T in curs:
        success = True
        break
    nexts = []
    for c in curs:
        if not c in edges:
            continue
        ns = edges[c]
        for n in ns:
            if not n in reached:
                reached.add(n)
                nexts.append(n)
    curs = nexts
    count += 1

if success:
    print(count // 3)
else:
    print(-1)

Solution (Python):
from collections import deque

N,M = map(int,input().split())
ad = [[[] for _ in range(3)] for _ in range(N)]
for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    for j in range(3):
        ad[u][j].append((v,(j+1)%3))
S,T = map(int,input().split())
S -= 1
T -= 1

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

while dq:
    v,j,d = dq.popleft()
    nd = d + 1
    for nv,nj in ad[v][j]:
        if (nv,nj) == (T,0):
            print(nd//3)
            exit()
        if visited[nv][nj]:
            continue
        visited[nv][nj] = True
        dq.append((nv,nj,nd))
        
print(-1)

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

edges = defaultdict(lambda: [])
for i in range(m):
    u, v = map(int, input().split())
    u1, v1 = (0, u), (1, v)
    u2, v2 = (1, u), (2, v)
    u3, v3 = (2, u), (0, v)
    edges[u1].append(v1)
    edges[u2].append(v2)
    edges[u3].append(v3)
    
    
    
    
    
    


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

dist = {}
dist[s] = 0
visiting = deque()
visiting.append(s)
while len(visiting) > 0:
    
    v = visiting.popleft()
    
    neighbors = edges[v]
    for neighbor in neighbors:
        if neighbor in dist:
            continue
        visiting.append(neighbor)
        if neighbor in dist:
            dist[neighbor] = min([dist[neighbor], dist[v] + 1])
        else:
            dist[neighbor] = dist[v] + 1
        


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

Solution (Python):
from collections import defaultdict as dd
from collections import deque
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
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())
S += 2 * N
T += 2 * N
stopped = [inf] * (3 * (N + 1))
Q = deque()
Q.append(S)
stopped[S] = 0
while len(Q) != 0:
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    if stopped[q] > stopped[p] + 1:
      Q.append(q)
      stopped[q] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T] // 3)

Solution (Python):
from collections import defaultdict as dd
from collections import deque
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
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())
S += 2 * N
T += 2 * N
stopped = [inf] * (3 * (N + 1))
Q = deque()
Q.append(S)
stopped[S] = 0
while len(Q) != 0:
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    if stopped[q] > stopped[p] + 1:
      Q.append(q)
      stopped[q] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T] // 3)

Solution (Python):
import copy
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(b)]
s,t=map(int,input().split())
s=3*s
t=3*t
dd=[[]for i in range(a+1)]
for i in range(b):
  da=c[i][0]
  db=c[i][1]
  dd[da].append(db)
  

d=[[]for i in range(3*(a+1))]
for i in range(len(dd)):
  for j in dd[i]:
      d[3*i].append(3*j+1)
      d[3*i+1].append(3*j+2)
      d[3*i+2].append(3*j)
e=[-1 for i in range(3*a+3)]
f=[s]
h=0
for i in range(1,3*a+3):
  g=[]
  for j in f:
    for k in d[j]:
      if e[k]==-1:
        e[k]=1
        g.append(k)
        if k==t:
          print(i//3)
          h=1
          break
    if h==1:
      break
  if h==1:
    break
  if g==[]:
    print(-1)
    break
  f=copy.copy(g)

Solution (Python):
from collections import defaultdict, deque

def bfs(start, end, V, E):
    V[start] = 0
    Q = deque()
    Q.append(start)
    while(len(Q) > 0 and V[end] < 0):
        q = Q.popleft()
        d = V[q] + 1
        for v in E[q]:
            if V[v] > 0:
                continue
            V[v] = d
            Q.append(v)
    return V

n, m = map(int, input().split())
E = defaultdict(list)
for i in range(m):
    u, v = map(int, input().split())
    E[u].append(n + v)
    E[n + u].append(2 * n + v)
    E[2 * n + u].append(v)
s, t = map(int, input().split())
V = [-1] * (3 * n + 1)
V = bfs(s, t, V, E)
if V[t] < 0:
    print(-1)
else:
    print(V[t] // 3)

Solution (Python):

import sys
from collections import deque

def solve(N, M, to, start, goal):
    costs = [float('inf')] * (3*N+3)
    costs[start] = 0

    q = deque([start])

    while len(q) != 0:
        u = q.popleft()
        for v in to[u]:
            if costs[u] + 1 < costs[v]:
                costs[v] = costs[u] + 1
                if v == goal: return costs[v] // 3
                q.append(v)
    return -1



def main():
    N, M = map(int, input().split())
    to = [ [] for _ in range(3*N+3) ]
    for _ in range(M):
        u, v = map(int, input().split())
        for i in range(3):
            to[u + (N+1)*i].append(v + (N+1) * ((i+1)%3))
    S, T = map(int, input().split())
    print(solve(N, M, to, S, T))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

inf = float('inf')

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

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

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

dq = deque()
dq.append(s)

can = False
dist = [inf] * (n * 3)
dist[s] = 0

while dq:
    v = dq.popleft()
    if v == t:
        can = True
        break
    for nv in es[v]:
        if dist[nv] == inf:
            dq.append(nv)
            dist[nv] = dist[v] + 1

if not can:
    print(-1)
else:
    print(dist[t] // 3)

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

edges = []
for i in range(M):
  edges.append([u[i]*3-3, v[i]*3-2])
  edges.append([u[i]*3-2, v[i]*3-1])
  edges.append([u[i]*3-1, v[i]*3-3])

def edges_to_pt(edges,n):
  '''
  input
    edges: 枝の[始点,終点]を格納した2次元配列　edges=[[0,1],[1,2],[2,0]]
    n:  頂点数 n=3

  output
    pt: 各点との結合場所を格納した2次元配列 pt=[[1],[2],[0]]
  '''
  pt = [[] for i in range(n)]
  while edges:
    temp_edge = edges.pop()
    pt[temp_edge[0]].append(temp_edge[1])
  return pt

def bfs(pt,v):
  '''
  input
    pt: 各点との結合場所を格納した2次元配列　pt=[[1, 2, 3], [0], [5, 0], [6, 0], [6], [2], [3, 4]]
    v: 初期点 v=0

  output
    d: 初期点からの距離を格納した配列 d=[0, 1, 1, 1, 3, 2, 2]
  '''
  n=len(pt)
  d=[-1]*n
  d[v]=0
  q=[v]
  c=1
  while q:
    q1=[]
    for i in q:
      for j in pt[i]:
        if d[j]==-1:
          d[j]=c
          q1.append(j)
    q=q1
    c+=1
  return d

pt = edges_to_pt(edges,3*N)
ans = bfs(pt,3*S-3)[3*T-3] // 3

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

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

S,T=map(int,input().split())
S=S-1
T=T-1
L[S]=0
Now=[S]
while Now:
  x=Now.pop(0)
  for i in range(len(G[x])):
    
    
    g=G[x]
    if L[g[i]]<0:
      L[g[i]]=L[x]+1
      Now.append(g[i])
print(L[T]//3)

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

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

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


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

visited = [[-1]*3 for j in range(n)]

l = 0
queue = deque([[s, l]])
visited[s][l] = 0
while queue:
  x, l = queue.popleft()
  if [x, l] == [t, 0]:
    print(visited[x][l]//3)
    exit()
  for x_ in g[x]:
    new_x, new_l = x_, (l+1)%3
    if visited[new_x][new_l] == -1:
      visited[new_x][new_l] = visited[x][l]+1
      queue.append([new_x, new_l])
    
print(visited[t][0])

Solution (Python):
from collections import deque


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


N, M = inpl()
UV = [inpl() for i in range(M)]
S, T = inpl()
S -= 1
T -= 1

ans = [[-1, -1, -1] for i in range(N)]

uv = [[] for i in range(N)]
for u, v in UV:
    u -= 1
    v -= 1
    uv[u].append(v)

ans[S][0] = 0
que = deque()
que.append((S, 0))
t = 0
while que:
    v, t = que.popleft()
    nt = (t + 1) % 3
    for nv in uv[v]:
        if ans[nv][nt] != -1:
            continue
        elif nv == T and nt == 0:
            ans[nv][nt] = (ans[v][t] + 1) // 3
            break
        ans[nv][nt] = ans[v][t] + 1
        que.append((nv, nt))

print(ans[T][0])

Solution (Python):

import sys
from operator import itemgetter

from fractions import gcd

from math import ceil, floor

from copy import deepcopy

from itertools import accumulate






from collections import Counter
import math
from functools import reduce
import heapq




input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())



class Graph():
    """
    Graph のテンプレート。デフォルトは重みなしの有向グラフの隣接リスト形式での定義。

    Parameters
    --------
        n (int): グラフのサイズ。

    Options
    --------
        Weighted = False: 重み付きかどうか
        Directed = True: 有向かどうか
        Matrix = False:　グラフの表現を隣接リストにするか隣接行列にするか。デフォルトは隣接リスト。

    Methods
    -------
        add_edge(start,end,(weight))
            start から end に重さ weight の辺を張る。重みなしグラフの場合は weight を省略する。
        dijkstra(start): O((E+V)logV)
            start から各頂点への最短距離を返す。負の辺があると無理。
        bellman_ford(start): O(EV)
            start から各頂点への最短距離を返す。負の辺があってもいけるが遅い。
    """

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

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

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

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

    
    
    
    
    
    
    
    
    
    
    
    
    
    

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

    
    
    

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

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

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならば bfs を使うか，グラフ構築時にあらかじめ重み　1　にしておく。

        Parameters
        ----------
            s (int): 最短距離を求める start の頂点

        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        b = [-1 for _ in range(self.sz)]  
        q = []
        d[s] = 0
        heapq.heappush(q, (d[s], s))
        while not len(q) == 0:
            p = heapq.heappop(q)
            v = p[-1]
            if d[v] < p[0]:
                continue
            if self.is_Weighted:
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[u] > d[v] + c:
                        d[u] = d[v] + c
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
            else:
                for e in self.graph[v]:
                    u = e
                    if d[u] > d[v] + 1:
                        d[u] = d[v] + 1
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
        return d

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

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。

        Parameters
        ----------
            s (int): 最短距離を求める start の頂点

        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        d[s] = 0
        for i in range(self.sz - 1):
            for v in range(self.sz):
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[v] == float('inf'):
                        continue
                    d[u] = min(d[u], d[v] + c)
        for v in range(self.sz):
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[v] == float('inf'):
                    continue
                if d[u] > d[v] + c:
                    return False
        return d

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

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。隣接行列だと重み付きで重み0の辺がバグります。重みなしグラフならばグラフ構築時にあらかじめ重み付きで入力しておく。

        Parameters
        ----------
            s (int): 最短距離を求める start の頂点

        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        if not self.is_Weighted:
            raise TypeError("重み付きグラフを入力してください。")
        d = Graph(self.sz, Weighted=True, Directed=True, Matrix=True)
        d.graph = [[float('inf') for _i in range(self.sz)]
                   for _j in range(self.sz)]
        if not self.is_Matrix:
            for i in range(self.sz):
                for j in self.graph[i]:
                    d.add_edge(i, j[0], j[1])
                d[i][i] = 0
        else:
            TypeError("隣接リスト形式で入力してください")
        for k in range(self.sz):
            for i in range(self.sz):
                for j in range(self.sz):
                    if d[i][k] == float('inf') or d[k][j] == float('inf'):
                        continue
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    g = Graph(3*N, Directed=True)
    for i in range(M):
        g.add_edge(u[i] - 1, v[i] - 1 + N)
        g.add_edge(u[i] - 1+N, v[i] - 1 + 2*N)
        g.add_edge(u[i] - 1+2*N, v[i] - 1)
    ans = g.dijkstra(S - 1)[T - 1]
    if ans % 3 == 0:
        print(ans // 3)
    else:
        print("-1")


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    u = [int()] * (M)  
    v = [int()] * (M)  
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  
    T = int(next(tokens))  
    solve(N, M, u, v, S, T)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N, M = map(int, input().split())
link = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    link[a-1].append(b-1)
s, t = map(lambda x: int(x)-1, input().split())

INF = 10 ** 10
dist = [[INF] * 3 for _ in range(N)]
dist[s][0] = 0

que = deque([[s, 0]])

while len(que):
    pv, pl = que.popleft()
    for nv in link[pv]:
        nl = (pl + 1) % 3
        if dist[nv][nl] != INF:
            continue
        dist[nv][nl] = dist[pv][pl] + 1
        que.append([nv, nl])

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

print(ans)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

N, M = map(int, input().split())
edge = [[] for _ in range(N)]

for _ in range(M):
	u, v = map(int, input().split())
	u -= 1
	v -= 1
	edge[u].append(v)
	
S, T = map(int, input().split())
S -= 1
T -= 1
has_reached = [[-1] * N for _ in range(3)]
q = [deque() for _ in range(3)]
q[0].append(S)
has_reached[0][S] = 0
i = 0

while q[0] or q[1] or q[2]:
	if q[i]:
		now_node = q[i].popleft()
		for next_node in edge[now_node]:
			if has_reached[i - 2][next_node] < 0:
				has_reached[i - 2][next_node] = has_reached[i][now_node] + int(i == 0)
				q[i - 2].append(next_node)
			
	i = (i + 1) % 3
	
print(has_reached[0][T])
'''
for i in range(3):
	print(has_reached[i])
'''