D - Number of Shortest paths Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。

道路 i を通ると都市 A_i と都市 B_i の間を双方向に 1 時間で移動することができます。

都市 1 から都市 N へ最も早く移動することができる経路は何通りありますか？
答えは非常に大きくなる可能性があるので (10^9+7) で割ったあまりを求めてください。

制約

  • 2 \leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1 \leq A_i < B_i \leq 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 つです。

入力例 2

4 3
1 3
2 3
2 4

出力例 2

1

都市 1 から都市 4 へは最短 3 時間で移動することができ、それを実現する経路は 1 \to 3 \to 2 \to 4 の 1 つです。

入力例 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

Score : 400 points

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