from Queue import Queue

adj = {}
adj2 = {0:[(1, 2),(2, 6),(3, 9)], 1:[(2,3)], 2:[], 3:[]}
order = list()
def bfs(start):
    discovered = [False] * len(adj)
    q = Queue()
    q.put(start)
    while not q.empty():
        here = q.get()
        order.append(here)
        for there in adj[here]:
            if not discovered[there]:
                q.put(there)
                discovered[there] = True
# bfs(0)
print order

distance = {}
parent = {}
def bfs2(start):
    q = Queue()
    q.put(start)
    distance[start] = 0 # shortest distance from start to i
    parent[start] = start # parent of i
    while not q.empty():
        here = q.get()
        for there, dist in adj2[here]:
            if not distance.has_key():
                q.put(there)
                distance[there] = distance[here] + 1
                parent[there] = here
    return parent, distance

def shotestPath(v, parent):
    path = list()
    while parent[v] != v:
        v = parent[v]
        path.append(v)
    return path[::-1]

parent, distance = bfs2(0)
for i in adj.keys():
    shortest = shortestPath(n, parent)
    print shortest
