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$ 取模。

## 限制条件 - $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 翻译