G - Counting Shortest Paths Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 575 点

問題文

N 頂点の無向完全グラフ G に対して下記の操作を行います。

各 i = 1, 2, \ldots, M について、頂点 u_i と 頂点 v_i を結ぶ無向辺を削除する。

その後の G において、頂点 1 から頂点 N へのパスが存在するかどうかを判定し、 存在する場合は頂点 1 から 頂点 N への最短パスの個数を 998244353 で割った余りを求めてください。

ここで、頂点 1 から 頂点 N への最短パスとは、頂点 1 から頂点 N へのパスであって含む辺の本数が最小であるものです。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

操作後の G において、頂点 1 から頂点 N へのパスが存在しない場合は -1 を出力し、 存在する場合は頂点 1 から頂点 N への最短パスの個数を 998244353 で割った余りを出力せよ。

入力例 1

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

出力例 1

3

操作後の G における頂点 1 から頂点 N への最短パスは、3 本の辺を含む下記の 3 個のパスです。

  • 頂点 1 \rightarrow 頂点 2 \rightarrow 頂点 3 \rightarrow 頂点 6
  • 頂点 1 \rightarrow 頂点 2 \rightarrow 頂点 5 \rightarrow 頂点 6
  • 頂点 1 \rightarrow 頂点 4 \rightarrow 頂点 5 \rightarrow 頂点 6

入力例 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

出力例 2

-1

操作後の G には辺が 1 本もありません。 頂点 1 から頂点 N へのパスが存在しないため -1 を出力します。

Score : 575 points

Problem Statement

We will perform the following operation on a complete undirected graph G with N vertices.

For each i = 1, 2, \ldots, M, delete the undirected edge connecting vertices u_i and v_i.

Determine if there is a path from vertex 1 to vertex N in G after the operation. If there is, find the number, modulo 998244353, of shortest paths from vertex 1 to vertex N.

Here, a shortest path from vertex 1 to vertex N is a path from vertex 1 to vertex N that contains the minimum number of edges.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If there is no path from vertex 1 to vertex N in G after the operation, print -1. If there is, print the number, modulo 998244353, of shortest paths from vertex 1 to vertex N.

Sample Input 1

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

Sample Output 1

3

In G after the operation, the shortest paths from vertex 1 to vertex N are the following three, each containing three edges.

  • vertex 1 \rightarrow vertex 2 \rightarrow vertex 3 \rightarrow vertex 6
  • vertex 1 \rightarrow vertex 2 \rightarrow vertex 5 \rightarrow vertex 6
  • vertex 1 \rightarrow vertex 4 \rightarrow vertex 5 \rightarrow vertex 6

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

-1

G has no edges after the operation. There is no path from vertex 1 to vertex N, so print -1.