102113: [AtCoder]ABC211 D - Number of Shortest paths

Problem Statement

The Republic of AtCoder has $N$ cities numbered $1$ through $N$ and $M$ roads numbered $1$ through $M$.

Using Road $i$, you can travel from City $A_i$ to $B_i$ or vice versa in one hour.

How many paths are there in which you can get from City $1$ to City $N$ as early as possible?
Since the count can be enormous, print it modulo $(10^9 + 7)$.

Constraints

• $2 \leq N \leq 2\times 10^5$
• $0 \leq M \leq 2\times 10^5$
• $1 \leq A_i < B_i \leq N$
• The pairs $(A_i, B_i)$ are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

Output

Print the answer. If it is impossible to get from City $1$ to City $N$, print $0$.

Sample Input 1

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

Sample Output 1

2

The shortest time needed to get from City $1$ to City $4$ is $2$ hours, which is achieved by two paths: $1 \to 2 \to 4$ and $1 \to 3 \to 4$.

Sample Input 2

4 3
1 3
2 3
2 4

Sample Output 2

1

The shortest time needed to get from City $1$ to City $4$ is $3$ hours, which is achieved by one path: $1 \to 3 \to 2 \to 4$.

Sample Input 3

2 0

Sample Output 3

0

It is impossible to get from City $1$ to City $2$, in which case you should print $0$.

Sample Input 4

7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7

Sample Output 4

4

问题描述

AtCoder共和国共有编号为1到N的N个城市和编号为1到M的M条道路。

使用第i条道路，你可以在一小时内从城市A_i前往B_i或反过来。

从城市1前往城市N的最早路径有多少条？
由于答案可能非常大，请输出答案模（10^9 + 7）的结果。

约束条件

• 2 ≤ N ≤ 2×10^5
• 0 ≤ M ≤ 2×10^5
• 1 ≤ A_i < B_i ≤ N
• (A_i, B_i)对各不相同。
• 输入中所有值都是整数。

输入

输入标准格式如下：

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

输出

输出答案。 如果无法从城市1前往城市N，请输出0。

样例输入1

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

样例输出1

2

从城市1前往城市4所需的最短时间是2小时，可以通过两条路径实现：$1 \to 2 \to 4$ 和 $1 \to 3 \to 4$。

样例输入2

4 3
1 3
2 3
2 4

样例输出2

1

从城市1前往城市4所需的最短时间是3小时，可以通过一条路径实现：$1 \to 3 \to 2 \to 4$。

样例输入3

2 0

样例输出3

0

无法从城市1前往城市2，这种情况下你应该输出0。

样例输入4

7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7

样例输出4

4