103196: [Atcoder]ABC319 G - Counting Shortest Paths

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.

问题描述

我们将对一个具有$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$的最短路径如下三个，每个包含三个边。

• 顶点$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$到顶点$N$没有路径，所以打印-1。