Problem: 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.

Submission attempts (in order):
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: float('inf'))
        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]

inputs=[]
n,m=map(int,input().split())
for i in range(m):
    a=[int(j) for j in input().split()]
    inputs.append((a[0],a[1],1))
S,T=map(int,input().split())

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, S)   
ans=d.shortest_distance(T)

if ans>10**9+7:
    print(ans)
else:
    if ans%3==0:
        print(ans//3)
    else:
        print(-1)






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: float('inf'))
        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]

inputs=[]
n,m=map(int,input().split())
for i in range(m):
    a=[int(j) for j in input().split()]
    inputs.append((a[0],a[1]+10**5,1))
    inputs.append((a[0]+10**5,a[1]+2*10**5,1))
    inputs.append((a[0]+2*10**5,a[1],1))
S,T=map(int,input().split())

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)

d = Dijkstra(g, S)   
ans=d.shortest_distance(T)

if ans>10**9+7:
    print(-1)
else:
    if ans%3==0:
        print(ans//3)
    else:
        print(-1)






Verdicts: Wrong Answer

Accepted