Message Route - Implementation

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: $O(N + M)$. Space: $O(N)$ for visited and parent arrays.