题目描述

漆黑意志的盗窃者四国玫碳构筑了一个结界。结界可描述为一个有 $N$ 个点的无向完全图（即 $N$ 个点两两之间连有一条边，共 $\frac{N \times (N-1)}{2}$ 条边），每条边的长度均为 $1$。结界中流转着灵力，灵力有始源点 $S$ 和交汇点 $T$，定义结界的完整度为从 $S$ 出发到 $T$ 的最短路径数量。为了打破玫碳的重围，妖精勇者俊达萌摧毁了结界中的 $M$ 条边。但是俊达萌是毛豆妖精，所以 ta 很笨。ta 想问问已经 $AK$ 了 $IOI$ 的你在摧毁了 $M$ 条边后结界的完整度是多少。答案对 $998244353$ 取模。

特别地，如果摧毁了 $M$ 条边后不存在从 $S$ 到 $T$ 的路径，那么输出 $-1$。

输入格式

第一行四个整数 $N$，$M$，$S$，$T$。 第二至第 $M + 1$ 行每行两个整数 $u_i$、$v_i$，表示被俊达萌摧毁的 $M$ 条边。

输出格式

一行一个整数表示答案。

样例

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

3

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

-1

数据范围

$20\%$ 的数据满足 $N \leq 5$

$50\%$ 的数据满足 $\frac{N \times (N-1)}{2} \leq 1.5 \times 10^6$

$2 \leq N \leq 2 \times 10^5$，$0 \leq M \leq \min \left \{ 2 \times 10^5,\frac{N \times (N-1)}{2} \right \}$，$1 \leq S,T \leq N$，$S \ne T$。

$1 \leq u_i,v_i \leq N$，$u_i \ne v_i$，$i \ne j \Longrightarrow \left \{ u_i,v_i \right \} \ne \left \{ u_j,v_j \right \}$。