题解

BFS 同时维护 dist 与 ways。第一次发现 v 时继承 ways[u]；若后来从同一层结点 u 走到 v 且 dist[v]=dist[u]+1，说明得到另一批同长最短路，将条数累加并取模。较长路线不能计入。复杂度 $O(n+m)$。