AT_abc319_g [ABC319G] Counting Shortest Paths

题目描述

对于一个有 $N$ 个顶点的无向完全图 $G$，进行如下操作：

对于每个 $i = 1, 2, \ldots, M$，删除连接顶点 $u_i$ 和顶点 $v_i$ 的无向边。

在操作后的 $G$ 中，判断是否存在从顶点 $1$ 到顶点 $N$ 的路径。如果存在，请求出从顶点 $1$ 到顶点 $N$ 的最短路径的个数，并对 $998244353$ 取模。

这里，从顶点 $1$ 到顶点 $N$ 的最短路径是指所有从顶点 $1$ 到顶点 $N$ 的路径中，所经过的边数最少的路径。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

如果操作后的 $G$ 中不存在从顶点 $1$ 到顶点 $N$ 的路径，则输出 -1。如果存在，则输出从顶点 $1$ 到顶点 $N$ 的最短路径的个数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

-1

说明/提示

限制条件

• $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$
• 所有输入均为整数

样例解释 1

操作后的 $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

操作后的 $G$ 中没有任何边，因此不存在从顶点 $1$ 到顶点 $N$ 的路径，输出 -1。

由 ChatGPT 4.1 翻译