Consider an undirected graph consisting of nodes where each node is labeled from to and the edge between any two nodes is always of length .

ShortestReachGraph.py

'''
algorithm:
    1. Find shortest path between start and goal nodes
    and multiply distance with 6. 
    2. If distance does not exist in graph that means
    replace it with -1 because it is not connected to start node
    
'''

from collections import defaultdict

class Graph():
    def __init__(self, size):
        self.graph = defaultdict(set)

    def connect(self, x,y):
        self.graph[x].add(y)
        
    def bfs_paths(self, start, goal):
        queue = [(start, [start])]
        while queue:
            vertex, path = queue.pop(0)
            non_visited_node=self.graph[vertex] - set(path)
            for next in non_visited_node:
                if next == goal:
                    yield path + [next]
                else:
                    queue.append((next, path + [next]))

    def shortest_path(self, start, goal):
        try:
            return next(self.bfs_paths(start, goal))
        except StopIteration:
            return None
    
    def find_all_distances(self, s, n):
        #print(self.graph, n)
        s=int(s)
        ans=[-1]*n

        for i in self.graph[s]:
            lent=len((self.shortest_path(s, i))[1:])*6
            print("sdfaf", lent)
            ans[i-1]=lent
        news=[]; res=""
        for i in range(n):
            if i!=(s-1):
                res+=str(ans[i])+str(" ")
        print(res)

t = int(raw_input())
for i in range(t):
    n,m = [int(x) for x in raw_input().split()]
    graph = Graph(n)
    for i in range(m):
        x,y = [int(x) for x in raw_input().split()]
        graph.connect(x,y) 
    s = input()
    graph.find_all_distances(s, n)
    

Consider an undirected graph consisting of nodes where each node is labeled from to and the edge between any two nodes is always of length . We define node to be the starting position for a BFS. Given queries in the form of a graph and some starting node, , perform each query by calculating the shortest distance from starting node to all the other nodes in the graph. Then print a single line of space-separated integers listing node 's shortest distance to each of the other nodes (ordered sequentially by node number); if is disconnected from a node, print as the distance to that node. Input Format The first line contains an integer, , denoting the number of queries. The subsequent lines describe each query in the following format: The first line contains two space-separated integers describing the respective values of (the number of nodes) and (the number of edges) in the graph. Each line of the subsequent lines contains two space-separated integers, and , describing an edge connecting node to node . The last line contains a single integer, , denoting the index of the starting node. Constraints Output Format For each of the queries, print a single line of space-separated integers denoting the shortest distances to each of the other nodes from starting position . These distances should be listed sequentially by node number (i.e., ), but should not include node . If some node is unreachable from , print as the distance to that node. Sample Input