信息学奥赛一本通T1499-最短路计数

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

1
1
1
2
4

样例解释

1 到 5 的最短路有 4 条，分别为 2 条 1→2→4→5 和 2 条 1→3→4→5（由于 4→5 的边有 2 条）。

数据范围：

对于 20% 的数据，N≤100；

对于 60% 的数据，N≤1000；

对于 100% 的数据，1≤N≤100000,0≤M≤200000。