分数: 575 点
问题陈述
我们将对完全无向图执行以下操作 G 与 N 顶点。
对于每个 i = 1, 2, \ldots, M,删除连接顶点的无向边 u_i 和 v_i.
判断是否存在从顶点出发的路径 1 到顶点 N in G 操作后。如果有,求该数,取模 998244353,从顶点开始的最短路径 1 到顶点 N.
这里,从顶点开始的最短路径 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
输出
如果没有来自顶点的路径 1 到顶点 N in G 运行后,打印 -1。如果有,则打印该数字,模数 998244353,从顶点开始的最短路径 1 到顶点 N.
示例输入 1
6 7 4 3 1 3 2 4 1 6 4 6 5 1 6 2
示例输出 1
3
In 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.