AtCoder Beginner Contest 211
翻译中…
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$.
翻译中…
样例
Input #1
4 5
2 4
1 2
2 3
1 3
3 4
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$.
Input #2
4 3
1 3
2 3
2 4
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$.
Input #3
2 0
Output #3
0
It is impossible to get from City $1$ to City $2$, in which case you should print $0$.
Input #4
7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7
Output #4
4
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。