In general, the shortest path from vertex \(s\) to vertex \(t\) on an undirected graph \(H\) can be counted as follows:

• Step \(1\): Perform Breadth-First Search (BFS) to find the distance \(\mathrm{dist}[v]\) from \(s\) to each vertex \(v\).
• Step \(2\): Count the number of paths from \(s\) to \(t\) in which all edges \(u \rightarrow v\) satisfies \(\mathrm{dist}[u] + 1 = \mathrm{dist}[v]\). This can be counted by a Dynamic Programming (DP) where \(\mathrm{dp}[v]\), the number of conforming paths from \(s\) to each vertex \(v\), is obtained in ascending order of \(\mathrm{dist}[v]\).

If vertex \(t\) turns out to be unreachable by step \(1\), we can determine that there is no path from \(s\) to \(t\).

Based on the idea so far, we consider the solution to this problem. The graph \(G\) we are interested in is a complete graph with \(N\) vertices, where the \(M\) edges specified by the input are blocked. Since there are at most \(\Theta(N^2)\) edges on \(G\), there is no hope that step \(1\) and \(2\) can be finished within the execution time limit. Instead, we do some tricks on each of step \(1\) and step \(2\), using the fact that there are as few as \(O(M)\) blocked edges.

- Trick on step \(1\)

In an ordinary BFS, we enumerate all the unvisited vertices adjacent to \(v\), and mark them as visited. However, if we here inspect all the edges connected to \(v\), it costs \(\Theta(N^2)\) at worst in this problem. To counter this issue, we maintain a set of unvisited vertex \(L\). When enumerating the vertices adjacent to \(v\), it is sufficient to scan only those contained in \(L\), mark all vertices \(u\) such that edge \(\lbrace v, u\rbrace\) is not blocked, and remove them from \(L\).

One can determine if an edge \(\lbrace v, u\rbrace\) is blocked with a balanced binary tree containing the \(M\) blocked edges in an \(O(\log M)\) time.

Every time a vertex \(u\) contained in \(L\) is inspected as a candidate of a vertex adjacent to \(v\), exactly one of the following happens:

• edge \(\lbrace v, u\rbrace\) is passable, so vertex \(u\) that used to be unvisited is now marked as visited; or
• edge \(\lbrace v, u\rbrace\) is blocked.

During the BFS, the former event happens at most \(N\) times, while the latter \(M\) times; thus, the step \(1\) can be processed in a total of \(O((N+M) \log M)\) time.

- Trick on step \(2\)

We find \(\mathrm{dp}[v]\) in ascending order of the distance \(\mathrm{dist}[v]\) found by step \(1\).

According to the original procedure of step \(2\), when finding \(\mathrm{dp}[v]\) for the vertices \(v\) distant by \(d\), one can find the sum of \(\mathrm{dp}[u]\) over all vertices \(u\) distant by \((d-1)\) such that edge \(\lbrace u, v\rbrace\) is passable.

However, inspecting all the vertices adjacent to \(v\) costs \(\Theta(N^2)\) time at worst. Instead, we find \(\mathrm{dp}[v]\) by subtracting \(\mathrm{dp}[u]\) for each vertex \(u\) distant by \((d-19\) such that edge \(\lbrace u, v\rbrace\) is blocked, from the sum \(\mathrm{sum}[d-1]\) of \(\mathrm{dp}\) over all vertices distant by \((d-1)\).

Every time the \(\mathrm{dp}\) of the vertices distant by \(d\) are found, we find their sum \(\mathrm{sum}[d]\) before advancing to the vertices distant by \((d+1)\).

Preparing a list of the blocked edges connected to each vertex, the procedure above can be done in a total of \(O(N + M)\) time.