最短路径计数

题目描述

我们将在具有 $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$ 取模的值。

样例

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

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$

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

-1

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

数据范围

• $2 \le N \le 2 \times 10^5$
• $0 \le M \le \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• $i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace$
• 所有输入值均为整数。