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):
n,m=map(int,input().split())
uv=[list(map(int, input().split())) for _ in range(m)]
s,t=map(int,input().split())

graph = [[] for _ in range(n)]
for v in uv:
    graph[v[0]-1].append(v[1]-1)

s-=1
t-=1

is_checked=[[0]*3 for _ in range(n)]
is_checked[s][0]=1

ans=-1

from collections import deque
q=deque()
q.append([s,0])

while q:
    v, cnt=q.popleft()
    if v==t and cnt%3==0:
        ans=cnt//3
        break
    for i in graph[v]:
        if is_checked[i][(cnt+1)%3]==0:
            q.append([i, cnt+1])
            is_checked[i][(cnt+1)%3]=1

print(ans)

Solution (Python):
from collections import deque

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

N = 3 * (n + 1)
adj = [[] for _ in range(N)]
for u, v in uv:
    for i in range(3):
        uu = u + i * n
        vv = v + ((i + 1) % 3) * n
        adj[uu].append(vv)

dq = deque([s])
d = [-1] * N
d[s] = 0
while dq:
    u = dq.popleft()
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            dq.append(v)

ans = d[t] // 3
print(ans)

Solution (Python):
from collections import deque
def bfs(start, goal, g, n, visited):
    visited1 = [False]*(n+1)
    visited2 = [False]*(n+1)
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        if curr_node == goal: 
            return
        for next1_node in g[curr_node]:
            if visited1[next1_node]: continue
            visited1[next1_node] = True
            for next2_node in g[next1_node]:
                if visited2[next2_node]: continue
                visited2[next2_node] = True
                for next3_node in g[next2_node]:
                    if visited[next3_node] >= 0: continue
                    visited[next3_node] = visited[curr_node] + 1
                    q.append(next3_node)



def main():
    n,m = map(int, input().split())
    g = [ [] for _ in range(n+1)]

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

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

    visited = [-1]*(n+1)
    visited[0] = 0

    bfs(s, t, g, n, visited)
    print(visited[t])

if __name__ == "__main__":
    main()

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
graph = [[] for _ in range((N+1)*3)]  
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
graph = [[] for _ in range((N+1)*3)]  
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for i in graph[prev]:
            
            d1 = d + 1
            if dist[i] > d1:
                dist[i] = d1
                heappush(que, (d1, i))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
graph = [[] for _ in range((N+1)*3)]  
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
graph = [[] for _ in range((N+1)*3)]  
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)

Solution (Python):
n,m=map(int,input().split())
u=[]
v=[]
g=[[] for _ in range(n)]

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

from collections import deque
 
def bfs(u):
    queue1 = deque([u])
    queue2 = deque([0])
    d=[]
    for i in range(n):
        d.append([-1]*3)
    d[u][0]=0
    while queue1:
        v=queue1.popleft()
        l=queue2.popleft()
        nl=(l+1)%3
        for i in g[v]:
            if d[i][nl] is -1:
                d[i][nl]=d[v][l]+1
                queue1.append(i)
                queue2.append(nl)
    return d

d=bfs(s)

ans=int(d[t][0]/3)
if d[t][0]==-1:
    ans=-1
print(ans)

Solution (Python):
n,m = map(int,input().split())
if m==0:
    print(-1)
    exit()
es = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    es[u].append(v)
s,t = map(int,input().split())

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

d = 0
q = [s]

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

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

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        g[u - 1].append(v - 1)
    s, t = map(int, input().split())

    q = deque()
    q.append(s - 1)
    seen = [[-1 for _ in range(3)] for _ in range(n)]
    seen[s - 1][2] = 0

    while q:
        u = q.popleft()

        for v in g[u]:
            for i in range(3):
                if seen[u][i] != -1 and seen[v][(i + 1) % 3] == -1:
                    seen[v][(i + 1) % 3] = seen[u][i] + 1
                    q.append(v)
                    if seen[t - 1][2] != -1:
                        print(seen[t - 1][2] // 3)
                        exit()
    print(-1)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
from collections import deque

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

queue = deque()
queue.append(s)
queue.append(1)
queue.append(0)
check = [[False for _ in range(3)] for _ in range(n)]
check[s][0] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    kkp = queue.popleft()
    for next_pos in uv[pos]:
        if next_pos == t and kkp == 2:
            print(ans // 3)
            exit()
        if check[next_pos][(kkp + 1) % 3]:
            continue
        check[next_pos][(kkp + 1) % 3] = True
        queue.append(next_pos)
        queue.append(ans + 1)
        queue.append((kkp + 1) % 3)
print(-1)

Solution (Python):
from collections import deque

def bfs(s, t):
    dist = [-1] * (3 * n + 1)
    q = deque()
    q.append(s)
    dist[s] = 0
    while q:
        p = q.popleft()
        for i in G[p]:
            if dist[i] == -1:
                dist[i] = dist[p] + 1
                q.append(i)
    return dist[t]

n, m = map(int, input().split())
G = [[] for _ in range(3 * n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    G[u].append(v + n)
    G[u + n].append(v + 2 * n)
    G[u + 2 * n].append(v)
s, t = map(int, input().split())
ans = bfs(s, t)
print(ans // 3 if not ans == -1 else ans)

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

import heapq
from collections import defaultdict
g1 = defaultdict(set)
for u, v in uv:
    g1[u-1].add(v-1)

s -= 1
t -= 1

dist = [[float('inf')] * 3 for _ in range(n)]
dist[s][0] = 0

q = [(0, s, 0)] 
heapq.heapify(q)

while q:
    du, u, c = heapq.heappop(q)
    if dist[u][c] < du:
        continue
    c2 = (c + 1) % 3
    for v in g1[u]:
        if du + 1 < dist[v][c2]:
            dist[v][c2] = du + 1
            heapq.heappush(q, (dist[v][c2], v, c2))

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

Solution (Python):
from collections import deque

def read_tuple():
    return map(int, input().split())


N, M = read_tuple()
E = [[] for i in range(N+1)]
for i in range(M):
    u, v = read_tuple()
    E[u].append(v)
S, T = read_tuple()

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

Q = deque([(S,0)])
while len(Q):
    v, c = Q.popleft()
    for u in E[v]:
        k = (c + 1) % 3
        if dst[u][k] == -1:
            dst[u][k] = c + 1
            Q.append((u, c + 1))

print(dst[T][0] // 3 if dst[T][0] != -1 else -1)

Solution (Python):
def solve():
  N, M = map(int, input().split(' '))
  G = [[] for _ in range(N + 10)]
  dist = [[-1 for _ in range(3)] for _ in range(N + 10)]
  for _ in range(M):
    u, v = map(int, input().split(' '))
    G[u].append(v)
  S, T = map(int, input().split(' '))
  que = [[S, 0]]
  dist[S][0] = 0
  while que:
    q = que.pop(0)
    nv, np = q[0], q[1]
    for item in G[nv]:
      if dist[item][(np + 1) % 3] == -1:
        que.append([item, (np + 1) % 3])
        dist[item][(np + 1) % 3] = dist[nv][np] + 1
  if dist[T][0] == -1:
    return -1
  else:
    return dist[T][0] // 3
print(solve())

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

INF = 10 ** 18

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def dijkstra(n, G, s):
    dist = [[INF, INF, INF] for _ in range(n)]
    dist[s][0] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        
        d, v = heapq.heappop(h)
        if dist[v][d%3] < d:
            continue
        
        for e in G[v]:
            tmp = dist[v][d%3] + e.cost
            if dist[e.end][tmp%3] > tmp:
                dist[e.end][tmp%3] = tmp
                heapq.heappush(h, (dist[e.end][tmp%3], e.end))
    return dist

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

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

dist = dijkstra(n, g, s-1)
ans = dist[t-1][0]

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

Solution (Python):
n,m = map(int,input().split())
path = [[[],[],[]] for i in range(n)]

gone = [[0]*3 for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    path[u-1][0].append([v-1,1])
    path[u-1][1].append([v-1,2])
    path[u-1][2].append([v-1,0])

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

now = [[s-1,0]]
gone[s-1][0] = 1
for ans in range(1,1000000):
    next = []
    for point,key in now:
        for go,gokey in path[point][key]:
            if go == t-1 and gokey == 0:
                print(ans//3)
                exit()
            if gone[go][gokey] == 0:
                gone[go][gokey] = 1
                next.append([go,gokey])
    now = next
  
print(-1)

Solution (Python):
n, m = map(int, input().split())
to = [[] for _ in range(n)]
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

cnt = 0
phase = 0
q = [s]
visited = [[False] * 3 for _ in range(n)]
while q:
    nextq = []
    for v in q:
        if visited[v][phase]:
            continue
        visited[v][phase] = True
        if v == t and phase == 0:
            print(cnt)
            exit()
        nextq += to[v]
    if phase == 0:
        cnt += 1
    phase = (phase + 1) % 3
    q = nextq
print(-1)

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n*3)]
    for i in range(m):
        a,b=map(lambda x:int(x)-1,readline().split())
        for j in range(3):
            G[3*a+j].append(3*b+(j+1)%3)

    s,t=map(lambda x:int(x)-1,readline().split())
    s*=3
    t*=3
    
    d=deque([s])
    flags=[-1]*(3*n)
    flags[s]=0
    while len(d)>0:
        now=d.popleft()
        for nex in G[now]:
            if flags[nex]==-1:
                flags[nex]=flags[now]+1
                d.append(nex)

    print(flags[t]//3)

if __name__=="__main__":
    main()

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n*3)]
    for i in range(m):
        a,b=map(lambda x:int(x)-1,readline().split())
        for j in range(3):
            G[3*a+j].append(3*b+(j+1)%3)

    s,t=map(lambda x:int(x)-1,readline().split())
    s*=3
    t*=3
    
    d=deque([s])
    flags=[-1]*(3*n)
    flags[s]=0
    while len(d)>0:
        now=d.popleft()
        for nex in G[now]:
            if flags[nex]==-1:
                flags[nex]=flags[now]+1
                d.append(nex)

    print(flags[t]//3)

if __name__=="__main__":
    main()

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


def main():
    N, M = map(int, input().split())
    edge = [[] * N for _ in range(N)]
    new_edge = [[] * N 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
    d = [[float('inf')] * 3 for _ in range(N)]
    q = deque([])
    q.append((S,0))
    d[S][0] = 0
    while q:
        v,l = q.popleft()
        nl = (l + 1) % 3
        for nv in edge[v]:
            if d[nv][nl] != float('inf'):
                continue
            q.append((nv,nl))
            d[nv][nl] = d[v][l] + 1
    if d[T][0] == float('inf'):
        print(-1)
    else:
        print(d[T][0] // 3)
            



if __name__ == "__main__":
    main()

Solution (Python):
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=[]
q.append([s,0])
while q:
    v,c=q.pop(0)
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]=1
print(ans)

Solution (Python):
import collections
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=collections.deque()
q.append([s,0])
while q:
    v,c=q.popleft()
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]=1
print(ans)

Solution (Python):


N,M=map(int,input().split())
graph={(i,j):[] for i in range(1,N+1) for j in range(1,4)}
for _ in range(M):
    u,v=map(int,input().split())
    graph[(u,1)].append((v,2))
    graph[(u,2)].append((v,3))
    graph[(u,3)].append((v,1))
S,T=map(int,input().split())

import heapq
def dijkstra(s,graph):
    dist={(i,j):float("inf") for i in range(1,N+1) for j in range(1,4)}
    dist[(s,3)]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,(s,3)))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for next_node in graph[node]:
            newlen=dist[node]+1
            if newlen<dist[next_node]:
                heapq.heappush(pq,(newlen,next_node))
                dist[next_node]=newlen
    return dist
K=dijkstra(S,graph)[(T,3)]
if K==float("inf"):
    print(-1)
else:
    print(K//3)

Solution (Python):


N,M=map(int,input().split())
graph={(i,j):[] for i in range(1,N+1) for j in range(1,4)}
for _ in range(M):
    u,v=map(int,input().split())
    graph[(u,1)].append((v,2))
    graph[(u,2)].append((v,3))
    graph[(u,3)].append((v,1))
S,T=map(int,input().split())

import heapq
def dijkstra(s,graph):
    dist={(i,j):float("inf") for i in range(1,N+1) for j in range(1,4)}
    dist[(s,3)]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,(s,3)))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for next_node in graph[node]:
            newlen=dist[node]+1
            if newlen<dist[next_node]:
                heapq.heappush(pq,(newlen,next_node))
                dist[next_node]=newlen
    return dist
K=dijkstra(S,graph)[(T,3)]
if K==float("inf"):
    print(-1)
else:
    print(K//3)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(3*N)]
for _ in range(M):
  u, v = map(lambda x:int(x)-1, input().split())
  graph[3*u+0] += [[3*v+1, 1]]
  graph[3*u+1] += [[3*v+2, 1]]
  graph[3*u+2] += [[3*v+0, 1]]

def dijkstra(s):
  dist = [float('inf')]*(3*N)
  dist[s] = 0
  num = [0]*(3*N)
  num[s] = 1
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num

S, T = map(lambda x:int(x)-1, input().split())
dist, _ = dijkstra(3*S)

if dist[3*T] == float('inf'):
  print(-1)
else:
  print(dist[3*T]//3)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**6
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    root = [[] for _ in range(N)]
    node = [[INF,INF,INF] for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        root[a-1].append(b-1)
    S,T = LI()
    S -= 1; T -= 1
    q = collections.deque()
    q.append((S,0,0))
    node[S][0] = 0
    while q:
        v,n,d = q.popleft()
        t = (n+1) % 3
        for u in root[v]:
            if node[u][t] > d+1:
                node[u][t] = d+1
                q.append((u,t,d+1))
    if node[T][0] < INF:
        print(node[T][0]//3)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  roads0 = [[] for _ in range(n)]
  roads1 = [[] for _ in range(n)]
  roads2 = [[] for _ in range(n)]
  
  for i in range(m):
    u, v = map(int, input().split())
    roads0[u-1].append(v-1)
    roads1[u-1].append(v-1)
    roads2[u-1].append(v-1)
  

  s, t = map(int, input().split())
  not_yet = deque([])
  already = [[False]*3 for _ in range(n)]
  dist = [[0]*3 for _ in range(n)]
  for v in roads0[s-1]:
    not_yet.append((v, 1))
    dist[v][1] = 1
    already[v][1] = True
  already[s-1][0] = True
  while not_yet:
    key = not_yet.popleft()
    k1, k2 = key[0], key[1]
    if k2 == 0:
      for v in roads1[k1]:
        if already[v][1]:
          continue
        dist[v][1] = dist[k1][0]+1
        already[v][1] = True
        not_yet.append((v, 1))
    elif k2 == 1:
      for v in roads2[k1]:
        if already[v][2]:
          continue
        dist[v][2] = dist[k1][1]+1
        already[v][2] = True
        not_yet.append((v, 2))
    else:
      for v in roads0[k1]:
        if already[v][0]:
          continue
        dist[v][0] = dist[k1][2]+1
        already[v][0] = True
        not_yet.append((v, 0))
  if already[t-1][0]:
    print(dist[t-1][0]//3)
  else:
    print(-1)
  
    
if __name__ == "__main__":
  main()

Solution (Python):
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    ta, tb = map(int, input().split())
    E[ta-1].append(tb-1)
S, T = map(int, input().split())
S -= 1
T -= 1

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

while q:
    cp, cd = q.pop(0)
    nd = (cd + 1) % 3
    for np in E[cp]:
        if dist[nd][np] != INF:
            continue
        else:
            dist[nd][np] = dist[cd][cp] + 1
            q.append([np,nd])

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

Solution (Python):



import heapq
from collections import defaultdict

INF = int(1e18)
N, M = map(int, input().split())
G = {n: [] for n in range(N)}
for _ in range(M):
    ui, vi = map(int, input().split())
    ui -= 1; vi -= 1
    G[ui].append((1, vi))
S, T = map(int, input().split()); S -= 1; T -= 1

Gp = {}
for n in G:
    for t in [0, 1, 2]:
        Gp[(n, t)] = []
for u in G:
    for c, v in G[u]:
        Gp[(u, 0)].append((c, (v, 1))) 
        Gp[(u, 1)].append((c, (v, 2))) 
        Gp[(u, 2)].append((c, (v, 0))) 


s = (S, 0)
t = (T, 0)
d = {v: INF for v in Gp}
used = {v: True for v in Gp}
d[s] = 0
used[s] = False

edgelist = []
for e in Gp[s]:
    heapq.heappush(edgelist, e)

while len(edgelist) > 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
        continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in Gp[v]:
        if used[e[1]]:
            heapq.heappush(edgelist, (e[0] + d[v], e[1]))

if t not in d or d[t] == INF:
    print("-1")
else:
    print(d[t] // 3)

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s)) 
        v = collections.defaultdict(bool) 
        while len(q):
            
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]: 
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev
n, m = inpl()
graph=Dijkstra()
for i in range(m):
    u, v = inpl()
    graph.add(u,v+n,1,directed=True)
    graph.add(u+n,v+n+n,1,directed=True)
    graph.add(u+n+n,v,1,directed=True)
s,t=inpl()
ans = 0
d, _ = graph.Dijkstra_search(s)
ans = d[t] if d[t] != INF else - 1

print(ans//3)

Solution (Python):
inf=10**12
n,m=map(int,input().split())
node=[[]for _ in range(n)]
dis=[inf]*(n*3)
for _ in range(m):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
s,t=map(int,input().split())
dis[(s-1)*3]=0
from collections import deque
queue=deque([(s-1)*3])
while queue:
	r=queue.popleft()
	p=(r%3+1)%3
	for x in node[r//3]:
		if dis[x*3+p]==inf:
			dis[x*3+p]=dis[r]+1
			queue.append(x*3+p)
print(dis[(t-1)*3]//3 if dis[(t-1)*3]!=inf else -1)

Solution (Python):


from collections import deque


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



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

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

q = deque()
q.append(S-1)
INF = float("inf")
dist = [INF] * (3*N)
dist[S-1] = 0

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

print(-1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n, m = map(int, readline().split())
graph = [[] for _ in range(n * 3)]
for i in range(m):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    graph[u].append(v + n)
    graph[u + n].append(v + 2 * n)
    graph[u + 2 * n].append(v)
s, t = map(lambda x: int(x) - 1, readline().split())
inf = float('inf')
q = deque([s])
dist = [inf] * (3 * n)
dist[s] = 0

while q:
    now = q.popleft()
    for next in graph[now]:
        if dist[next] != inf:
            continue
        dist[next] = dist[now] + 1
        if next == t:
            print(dist[next] // 3)
            exit()
        q.append(next)
print(-1)

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

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

INF = 1001001001
dist = [[0] * 3 for _ in range(100005)]

for i in range(N):
    for j in range(3):
        dist[i][j] = INF

q = queue.Queue()
q.put((S, 0))
dist[S][0] = 0
while not q.empty():
    e = q.get()
    v = e[0]
    l = e[1]
    for u in edges[v]:
        nl = (l + 1) % 3
        if dist[u][nl] != INF:
            continue
        dist[u][nl] = dist[v][l] + 1
        q.put((u, nl))

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

Solution (Python):
from queue import Queue
import sys
N, M = map(int,input().split())
edges = [[] for _ in range(3 * N)]
flag = [0] * (3 * N)
for _ in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    edges[u % (3 * N)].append((v + N) % (3 * N))
    edges[(u + N) % (3 * N)].append((v + 2 * N) % (3 * N))
    edges[(u + 2 * N) % (3 * N)].append(v % (3 * N))

S, T = map(int,input().split())
q = Queue()
q.put([0,S-1])
while not q.empty():
    p = q.get()
    if p[1] == T-1:
        print(p[0] // 3)
        sys.exit()
    for i in edges[p[1]]:
        if flag[i] == 0:
            flag[i] = 1
            q.put([p[0]+1,i])
print(-1)

Solution (Python):
N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

N3=N*3
adj=[set() for _ in range(N3)]

for a,b in edges:
    for i in range(3):
        start = a+N*i
        dst = b+N*(i+1)
        adj[start%N3].add(dst%N3)


Q=[S]
visited={S}
dist=[-1]*N3
dist[S]=0

while Q:
    tmp=[]
    for q in Q:
        for i in adj[q]:
            if i in visited:
                continue
            else:
                dist[i]=dist[q]+1
                visited.add(i)
                tmp.append(i)
    Q = tmp
print(dist[T] if dist[T]==-1 else dist[T]//3)