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

Solution (Python):

import sys
input = sys.stdin.readline









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

S,T = S-1,T-1

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

from collections import deque
dq = deque([S])
inf = float("inf")
dist = [inf]*(3*N)
dist[S] = 0

while dq:
    v = dq.popleft()
    for e in E[v]:
        if dist[e] != inf:
            continue
        dist[e] = dist[v]+1
        if e==T:
            print(dist[e]//3)
            sys.exit()
        dq.append(e)

print(-1)

Solution (Python):


import sys




from collections import deque                
from collections import defaultdict          
















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    
    
    
    

    
    
    
    
    
    
    
        
    
    
    

    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    """
    set を作るところで最悪 O(n^2) より 2 つくらい TLE
    経路長 3 の倍数というところで start からの経由数の剰余 (mod 3) を管理する、という方針は思いついたが... それをノードを増やすことで管理するという発想に至らず。
    """
    n, m = mi()
    adj = [[] for _ in range(n * 3)]
    for _ in range(m):
        a, b = mi_0()
        adj[a * 3].append(b * 3 + 1)
        adj[a * 3 + 1].append(b * 3 + 2)
        adj[a * 3 + 2].append(b * 3)
    
    start, goal = mi_0()
    start *= 3
    goal *= 3

    q = deque([(start, 0)])
    visited = [False] * (n * 3)
    while q:
        u, dist = q.popleft()
        if dist > 3 * n:
            break
        if u == goal:
            assert (dist % 3 == 0)
            print(dist // 3)
            return
        if not visited[u]:
            visited[u] = True
            for v in adj[u]:
                if not visited[v]:
                    q.append((v, dist + 1))
    print(-1)

        

if __name__ == "__main__":
    main()

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

s,t=map(int,input().split())
s-=1
t-=1
from collections import deque
dist=[[-1]*3 for i in range(n)]
dist[s][0]=0
q=deque()
q.append([s,0])
while q:
  cur,parity=q.popleft()
  for nx in G[cur]:
    nx_parity=(parity+1)%3
    if dist[nx][nx_parity]==-1:
      dist[nx][nx_parity]=dist[cur][parity]+1
      q.append([nx,nx_parity])
if dist[t][0]==-1:
  print(-1)
else:
  print(int(dist[t][0]//3))

Solution (Python):
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N,M= map(int,input().split())
g = defaultdict(list)

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

dq = deque([S])
inf = 10**15
d = [inf for i in range(3*N+1)]
d[S] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[nv] > d[v] + 1:
            d[nv] = d[v] + 1
            dq.append(nv)

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

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

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


visited=[]
for i in range(N+1):
  visited.append([False]*3)
  
queue=[S]
t=0
while queue:
  new_queue=set()
  for u in queue:
    if u==T and t%3==0:
      print(t//3)
      sys.exit(0)
    
    visited[u][t%3]=True
    for v in graph[u]:
      if not visited[v][(t+1)%3]:
        new_queue.add(v)
        
  queue=list(new_queue)
  t+=1
  
print(-1)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
for _ in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    path[u].add(v)

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

que = deque([(s-1,0)])
d = [[float('inf')]*n for _ in range(3)]
d[0][s-1] = 0
while que:
    p,i = que.popleft()
    j = (i+1)%3
    for to in path[p]:
        if d[j][to] == float('inf'):
            d[j][to] = d[i][p] + 1
            que.append((to,j))
if d[0][t-1] == float('inf'):
    d[0][t-1] = -3
print(d[0][t-1]//3)

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = 10**18
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
s,t = map(int,input().split())

def dijkstra_heap(s,g,p):
    d = [[INF] * p for i in range(n)] 
    used = [[True] * p for i in range(n)] 
    used[s][0] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[1,es,1]) 
    while len(ed_list):
        ken,v,md = heapq.heappop(ed_list)
        if not used[v][md]:
            continue
        d[v][md] = ken
        used[v][md] = False
        if not used[g][0]:
            break
        for e in edge[v]:
            if used[e][(md+1)%p]:
              if (md+1)%p == 1:
                heapq.heappush(ed_list,[ken+1,e,1])
              else:
                heapq.heappush(ed_list,[ken,e,(md+1)%p])
    return d[g][0]

ans = dijkstra_heap(s-1,t-1,3)
if ans == INF:
  print(-1)
else:
  print(ans)

Solution (Python):
from collections import deque
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())
m = iter(uv)
UV = zip(m, m)
graph = [[] for _ in range(3 * n)]
for u, v in UV:
    u -= 1
    v -= 1
    graph[u].append(v + n)
    graph[u + n].append(v + 2 * n)
    graph[u + 2 * n].append(v)
s -= 1
t -= 1
infi = 10 ** 20
dist = [-1] * (3 * n)


def bfs(s):
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        v = que.popleft()
        if v == t:
            return dist[t]
        d = dist[v]
        for u in graph[v]:
            if dist[u] > 0:
                continue
            dist[u] = d + 1
            que.append(u)
    return -1


ans = bfs(s)
if ans > 0:
    ans //= 3
print(ans)

Solution (Python):

import sys
from collections import deque

def solve(N: int, M: int, G, S: int, T: int):
    S -= 1
    T -= 1
    now = deque([S])
    dist = [0 for _ in range(N * 3)]
    while now:
        p = now.popleft()
        for n in G[p]:
            if dist[n] != 0:
                continue
            dist[n] = dist[p] + 1
            if n == T:
                print(dist[n] // 3)
                exit()
            now.append(n)
    print(-1)
    return



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))  
    G = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = int(next(tokens)) - 1, int(next(tokens))-1
        G[u].add(v + N)
        G[u + N].add(v + 2 * N)
        G[u + 2 * N].add(v)

    S = int(next(tokens))  
    T = int(next(tokens))  
    solve(N, M, G, S, T)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    inf = 10**17
    

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] 
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
    s,t = map(int, input().split())
    s -= 1
    t -= 1

    d1 = [inf]*n
    d2 = [inf]*n
    d0 = [inf]*n
    d0[s] = 0
    d = deque([[s, 0]])
    while d:
        v, hosuu = d.popleft()
        hosuu += 1
        for nv in adj[v]:
            if hosuu%3==1 and d1[nv]>hosuu:
                d1[nv] = hosuu 
                d.append([nv, hosuu])
            if hosuu%3==2 and d2[nv]>hosuu:
                d2[nv] = hosuu
                d.append([nv, hosuu])
            if hosuu%3==0 and d0[nv]>hosuu:
                d0[nv] = hosuu
                d.append([nv, hosuu])
    if d0[t]==inf:
        print(-1)
    else:
        print(d0[t]//3)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
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] += [3*v+1]
  graph[3*u+1] += [3*v+2]
  graph[3*u+2] += [3*v]

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

def bfs(s):
  q = deque([s])
  dist = [float('inf')]*(3*N)
  dist[s] = 0

  while q:
    u = q.popleft()
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

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

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

INF = float('inf')

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


def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2 in adjList[vNow]:
            c2 = cNow + 1
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs

costs = Dijkstra(adjL, 3*S)


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

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

INF = float('inf')

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


def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2 in adjList[vNow]:
            c2 = cNow + 1
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs

costs = Dijkstra(adjL, 3*S)


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

Solution (Python):
def bfs(g, N, s, t):
    from collections import deque

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

    dq = deque()
    dq.append(s)

    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = d + 1
            if u == t:
                return dist[t] // 3  
            dq.append(u)
    return -1


def main():
    import sys
    input = sys.stdin.readline

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

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

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

    ans = bfs(g, N, S, T)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    for j in range(3):
        edges[to_v(u, j)].append(to_v(v, (j+1) % 3))
s, t = list(map(lambda x: int(x)-1, input().split()))
init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

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

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
UV = [[]for _ in range(n)]
for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    UV[u].append(v)
s, t = list(map(lambda x: int(x)-1, input().split()))

NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for i in range(n):
    for i2 in UV[i]:
        for j in range(3):
            edges[to_v(i, j)].append(to_v(i2, (j+1) % 3))

init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

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

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
UV = [[]for _ in range(n)]
for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    UV[u].append(v)
s, t = list(map(lambda x: int(x)-1, input().split()))

NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for i in range(n):
    for i2 in UV[i]:
        for j in range(3):
            edges[to_v(i, j)].append(to_v(i2, (j+1) % 3))

init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

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

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n,m = map(int,input().split())
    G = [[] for _ in range(3*n)]
    for _ in range(m):
        u,v = map(int,input().split())
        u -= 1
        v -= 1
        for i in range(3):
            G[u*3 + i].append(v*3 + (i + 1)%3)
    
    s,g = map(int,input().split())
    s -= 1
    g -= 1

    q = deque([3*s])
    dist = [-1] * (3*n)
    dist[3*s] = 0
    while q:
        p = q.popleft()
        for e in G[p]:
            if dist[e] < 0:
                dist[e] = dist[p] + 1
                q.append(e)
                
    print(dist[3*g]//3 if dist[3*g] >= 0 else -1)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

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


class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: 10 ** 18)
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

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

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]



n,m = map(int, input().split())
uv = [list(map(int, input().split())) for i in range(m)]
s,t = map(int, input().split())
g = Graph()
for u,v in uv:
  g.add_edge(u*3-3,v*3-2)
  g.add_edge(u*3-2,v*3-1)
  g.add_edge(u*3-1,v*3-3)
dist = Dijkstra(g,(s-1)*3)
ans = dist.shortest_distance((t-1)*3)
if ans == 10 ** 18:
  print(-1)
else:
  print(ans // 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):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[3*u].append(3*v+1)
  graph[3*u+1].append(3*v+2)
  graph[3*u+2].append(3*v)

S, T = map(int, input().split())
S -= 1; T -= 1
dist = [-1] * (3*N)
dist[3*S] = 0
d = deque([3*S])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append(child)

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[] for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1].append(graf2-1)
S, T = map(int, input().split())
S, T = S-1, T-1


dist[S][0] = 0
q = deque()
q.append((S, 0))
while q:
    v, l = q.popleft()
    for i in vector[v]:
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.append((i, new_l))

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

Solution (Python):

"""
グラフを3倍して、
ある二頂点u→vに辺が存在する時
余り0の頂点u→1の頂点v
余り1の頂点u→2の頂点v
余り2の頂点u→0の頂点v
にそれぞれ辺を張った時に、
スタート(頂点S)の余り0の頂点から、
ゴール(頂点T)の余り0への最短パスが答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
g = [[] for _ in range(3*n)]
for i in range(m):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append([1,y+n])
    g[x+n].append([1,y+n+n])
    g[x+n+n].append([1,y])




import heapq
def dijkstra_heap(s,edge):
    
    n = len(edge)
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(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,readline().split())
s,t = s-1,t-1

res = dijkstra_heap(s,g)[t]

print(-1 if res == float("inf") else res//3)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
edge = [[] for i in range(n+1)]

for _ in range(m):
    u, v = map(int, input().split())
    edge[u].append(v)
s,t = map(int, input().split())
queue = deque()
queue.append((s, 0))
visited = [[False] * 3 for _ in range(n+1)]
while queue:
    u, d = queue.popleft()
    if visited[u][d % 3]:
        continue
    visited[u][d % 3] = True
    if d % 3 == 0 and u == t:
        print(d // 3);exit()
    for v in edge[u]:
        queue.append((v, d+1))
print(-1)

Solution (Python):
import copy
n,m = map(int,input().split())
graph = [[] for _ in range(n*3)]
for i in range(m):
  u,v = map(int,input().split())
  for j in range(3):
    graph[n*j+u-1].append((n*(j+1)+v-1)%(3*n))
s,t = map(int,input().split())
wait = [s-1]
cnt = 0
done = [0]*(3*n)
while wait:
  cnt += 1
  now = copy.copy(wait)
  wait = []
  for i in now:
    for j in graph[i]:
      if not done[j]:
        done[j] = 1
        wait.append(j)
      if j == t-1:
        print(cnt//3)
        quit()
print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
def MI():
  return map(int,input().split())
def main():
  n,m=MI()
  G=[[] for _ in range(n)]
  for _ in range(m):
    u,v=MI()
    u-=1
    v-=1
    G[u].append(v)
  s,t=MI()
  s-=1
  t-=1
  
  fi=[True]*n
  se=[True]*n
  th=[True]*n
  th[s]=False

  dq=[s]
  depth=0
  
  while dq:
    depth+=1
    tank1=[]
    tank2=[]
    tank3=[]
    
    for p in dq:
      for c in G[p]:
        if fi[c]:
          fi[c]=False
          tank2.append(c)
    for p in tank2:
      for c in G[p]:
        if se[c]:
          se[c]=False
          tank3.append(c)
    for p in tank3:
      for c in G[p]:
        if th[c]:
          th[c]=False
          tank1.append(c)
        if c==t:
          print(depth)
          exit()
    dq=tank1
  print(-1)  
if __name__=='__main__':
  main()

Solution (Python):

import sys
input = sys.stdin.readline
def MI():return map(int,input().split())
def main():
  n,m=MI()
  G=[[] for _ in range(n)]
  for _ in range(m):
    u,v=MI()
    u-=1
    v-=1
    G[u].append(v)
  s,t=MI()
  s-=1
  t-=1
  
  fi=[True]*n
  se=[True]*n
  th=[True]*n
  th[s]=False
  
  
  
  dq=[s]
  depth=0
  
  while dq:
    depth+=1
    tank1=[]
    tank2=[]
    tank3=[]
    
    for p in dq:
      for c in G[p]:
        if fi[c]:
          fi[c]=False
          tank2.append(c)
    for p in tank2:
      for c in G[p]:
        if se[c]:
          se[c]=False
          tank3.append(c)
    for p in tank3:
      for c in G[p]:
        if th[c]:
          th[c]=False
          tank1.append(c)
        if c==t:
          print(depth)
          exit()
    dq=tank1
  print(-1)  
if __name__=='__main__':
  main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
def MI():return map(int,input().split())
def main():
  n,m=MI()
  G=[[] for _ in range(n)]
  for _ in range(m):
    u,v=MI()
    u-=1
    v-=1
    G[u].append(v)
  s,t=MI()
  s-=1
  t-=1
  
  fi=[True]*n
  se=[True]*n
  th=[True]*n
  th[s]=False
  
  dq=deque([])
  dq.append(s)
  depth=0
  
  while dq:
    depth+=1
    tank1=[]
    tank2=[]
    tank3=[]
    
    for p in dq:
      for c in G[p]:
        if fi[c]:
          fi[c]=False
          tank2.append(c)
    for p in tank2:
      for c in G[p]:
        if se[c]:
          se[c]=False
          tank3.append(c)
    for p in tank3:
      for c in G[p]:
        if th[c]:
          th[c]=False
          tank1.append(c)
        if c==t:
          print(depth)
          exit()
    dq=deque(tank1)
  print(-1)  
if __name__=='__main__':
  main()

Solution (Python):


import heapq as hq

def bfs(connections:list,s,t):
    inf = float('inf')
    costs =[[inf,inf,inf] for i in connections]
    visited = [[False,False,False] for i in connections]
    costs[s][0]=0
    q =[]
    hq.heappush(q,(0,0,s))

    while q:
        cost,step,node = hq.heappop(q)
        if visited[node][step]:
            continue
        visited[node][step] = True
        
        for target in connections[node]:
            if costs[target][(step+1)%3]>cost+1:
                costs[target][(step+1)%3]=cost+1
                hq.heappush(q,(cost+1,(step+1)%3,target)) 

    ans = costs[t][0]

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


    



def resolve():
    N,M = map(int,input().split())

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

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

    bfs(connections,S-1,T-1)



if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque

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

s, t = map(int, input().split())
dist = [-1] * (3 * n)
queue = deque([3 * s - 3])
dist[3 * s - 3] = 0
while queue:
  vertex = queue.popleft()
  for next_vertex in adj_list[vertex]:
    if dist[next_vertex] != -1:
      continue
    dist[next_vertex] = dist[vertex] + 1
    queue.append(next_vertex)
t_distance = dist[3 * t - 3]
if t_distance == -1:
  print(-1)
else:
  print(t_distance // 3)

Solution (Python):
from heapq import heappop, heappush, heapify

INF = float("inf")
n, m = map(int, input().split())
idx = [[i*3 + j for j in range(3)] for i in range(n)]
g = [[] for _ in range(n*3)]
for _ in range(m):
    u, v = map(lambda x: int(x)-1, input().split())
    for i in range(3):
        g[idx[u][i]].append((idx[v][(i+1) % 3], 1))
s, t = map(lambda x: int(x)-1, input().split())

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s], q = 0, []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

res = dijkstra(g, n*3, idx[s][0])[idx[t][0]]
print(-1 if res == INF else res // 3)

Solution (Python):




from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
n,m=map(int,input().split())
edge=[[]for _ in range(n*3)]
for _ in range(m):
	u,v=map(int,input().split())
	u-=1
	v-=1
	edge[u*3].append([v*3+1,1])
	edge[u*3+1].append([v*3+2,1])
	edge[u*3+2].append([v*3,1])
s,t=map(int,input().split())
s-=1
t-=1
dij=dijkstra(s*3,n*3,edge)
if dij[t*3]==10**20:print(-1)
else:print(dij[t*3]//3)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
graph = [[[] for _ in range(3)] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u][0].append([v, 1])
    graph[u][1].append([v, 2])
    graph[u][2].append([v, 0])


s, t = map(int, input().split())
q = deque([[s, 0]])
visited = [[False] * 3 for _ in range(n+1)]
visited[s][0] = True
dist = [[-3] * 3 for _ in range(n+1)]
dist[s][0] = 0
while q:
    num, cnt = q.popleft()
    for i, j in graph[num][cnt]:
        if visited[i][j]:
            continue
        q.append([i, j])
        visited[i][j] = True
        dist[i][j] = dist[num][cnt] + 1

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

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    from collections import deque
    n,m = map(int,input().split())
    Es = [[] for i in range(n)]
    Et = [[] for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        Es[a].append(b)
        Et[b].append(a)
    s,t = map(int,input().split())

    diss = [[float("INF")] for i in range(n)]
    dist = [[float("INF")] for i in range(n)]
    diss[s-1] = [0]
    dist[t-1] = [0]
    def bfs(x,E,dis):
        q = deque([])
        q.append((x,0))
        while q:
            now,d = q.popleft()
            for nex in E[now]:
                if dis[nex] == [float("INF")]:
                    dis[nex] = [d+1]
                    q.append((nex,d+1))
                else:
                    check = True
                    for i in dis[nex]:
                        if i%3 == (d+1)%3:
                            check = False
                    if check:
                        q.append((nex,d+1))
                        dis[nex].append(d+1)

    bfs(s-1,Es,diss)
    bfs(t-1,Et,dist)

    ans = float("INF")
    for i in range(n):
        for j in diss[i]:
            for k in dist[i]:
                if (j+k)%3 == 0:
                    ans = min(ans,(j+k)//3)
    if ans == float("INF"):
        print(-1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

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

def bfs():
    dist = [-1]*(3*N)
    dist[serial[S][0]] = 0
    q = deque([serial[S][0]])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist[serial[T][0]]

N, M = map(int, input().split())
serial = [[-1]*3 for _ in range(N)]
c = 0

for i in range(N):
    for j in range(3):
        serial[i][j] = c
        c += 1

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

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

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

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