考虑一个有 $N$ 个点的无向完全图。我们将要对它进行下述操作。

对于每个 $i =1,2,…,M$，删除连接点 $u_i$ 和 $v_i$ 的边。

判断删完边之后的图上是否有从点 $1$ 到点 $N$ 的路径。若有，求出从点 $1$ 到点 $N$ 的最短路的数量，输出这个数目除以 $998244353$ 的余数；若没有，输出 $-1$。

数据范围

• $2≤N≤2×10^5$
• $0≤M≤\min⁡{2×10^5,N(N−1)/2}$
• $1≤u_i,v_i≤N$
• $u_i \ne v_i$
• 输入的值都是整数。

输入格式

$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

输出格式

输出答案。

样例

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

3

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

-1