Here is the full solution for Message Route:
function messageRoute(n, adj):
dist = [infinity] * (n + 1)
parent = [0] * (n + 1)
dist[1] = 0
queue.push(1)
while queue is not empty:
u = queue.pop_front()
for each v in adj[u]:
if dist[v] == infinity:
dist[v] = dist[u] + 1
parent[v] = u
queue.push(v)
if dist[n] == infinity:
print "IMPOSSIBLE"
else:
path = []
current = n
while current != 0:
path.append(current)
current = parent[current]
path.reverse()
print path.length
print path
This pattern appears in many BFS problems that ask you to report the actual shortest path.
This runs in time and uses space.