← 返回题目列表

AtCoder · abc319_g

G. 计算最短路径

中文机器翻译题面 查看原题

分数: 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.