Pattern: BFS for shortest unweighted path.
function messageRoute(n, adj):
visited = array of size n + 1, all false
parent = array of size n + 1, all -1
q = queue
q.push(1)
visited[1] = true
while q is not empty:
u = q.pop()
if u == n:
break
for v in adj[u]:
if not visited[v]:
visited[v] = true
parent[v] = u
q.push(v)
if not visited[n]:
print "IMPOSSIBLE"
else:
path = reconstructPath(parent, n)
print path.length
print path
Time: . Space: for visited and parent arrays.