Let \(G'\) be the graph formed from the given edges; the problem essentially asks for a breadth-first search on its complement graph. However, doing this naively may cost up to \(O(N^2)\), which is too much.

There are two sub-problems that must be solved: how to calculate the number of shortest paths to a given vertex, and how to efficiently discover new vertices to put on the queue.

Calculating the number of shortest paths

We do this when dequeueing a vertex, let that vertex be \(u\). Let the distance of a vertex \(u\) from vertex \(1\) be \(d(u)\); we may assume that \(ways[v]\) for all \(v : d(v) < d(u)\) have already been calculated. Then:

\[ways[u] = \sum_{v\ :\ d(v) = d(u) - 1 \wedge \{u, v\} \in G} ways[v] = \sum_{v\ :\ d(v) = d(u) - 1} ways[v] - \sum_{v\ :\ d(v) = d(u) - 1 \wedge \{u, v\} \in G'} ways[v]\]

The first term can be memoized as \(\displaystyle W[x] = \sum_{v\ :\ d(v) = x} ways[v]\), which can be added to each time we calculate \(ways[*]\); the second term can be found by iterating through the adjacency list of \(G'\), which will cost no more than \(O(N + M)\) over all vertices.

Discovering new vertices

If we maintain a list \(R\) of vertices that have not been enqueued yet, whenever we dequeue vertex \(u\), we can iterate through \(R\) to find vertices where \(\{u, v\} \notin G'\) and enqueue them. If we can check that condition in \(O(1)\) (either with a hash set, or with a boolean array where vertices \(v : \{u, v\} \in G'\) are temporarily set to true), we can note that the total number of times an element stays in \(R\) is no more than \(M\), so we spend no more than \(O(N + M)\) time here.

Thus the problem has been solved in \(O(N + M)\). Be sure to remember to print \(-1\) if vertex \(N\) is not reached.