1003. Secluded Sensei

题目描述

（来源：[Fanmade] Map of Kivotos ver. 10 (by @ayetlee_179) : r/BlueArchive）

众所周知，基沃托斯一共有数千个学院。作为一名夏莱的 Sensei，每天都要奔赴各处处理事务。但正如凯伊所指出的那样，夏莱承担着极为繁重的行政职责——因此 Sensei 可能仅仅只是走在路上，就会撞见无数意料之外、需要亲自出手解决的突发状况。

但今天不同！

某位不知名的夏莱 Sensei hezlik 早已在桃信上与小夏约好，要一同前往百鬼夜行联合学院的百夜堂，品尝新推出的限定甜品。为了能和可爱的小夏准时享用美味，Sensei 必须选择一条从夏莱通往百夜堂的最短路线。

然而，路途并不太平。每当经过的路径与其他学院的辖区接壤，就极有可能招来层出不穷的麻烦。为了把与其他学院接壤的范围压到最小，hezlik 希望在所有最短路线中，挑选那条「接触到的学院总数」最少的方案。

与此同时，为了防止邪恶的千年科技学院截获并破解出行规划，hezlik 还需要知道：满足上述所有条件的最优路线一共有多少条，以便选择一条隐秘的路径准时到达。

于是，hezlik 把这项严峻的任务，郑重地交到了你的手上。

---

给定一个包含 $n$ 个点、$m$ 条边的无向无权连通图 $G = (V, E)$，以及起点 $s$ 和终点 $t$。

对于图中的一个点集 $S \subseteq V$，定义其闭邻域为：

$$N[S] = \left|\left\{\, x \in V \;\middle|\; x \in S \ \text{或}\ \exists\, y \in S,\ (x, y) \in E \,\right\}\right|$$

即点集 $S$ 中所有点及其相邻点构成的集合的大小。

对于一条从 $s$ 到 $t$ 的路径 $P$，设其经过的点集为 $V(P)$，则该路径的闭邻域定义为 $N[V ( P) ]$。

请你在所有从 $s$ 到 $t$ 的最短路径中，求出闭邻域的最小值，以及取得该最小值的路径数量。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

第一行包含四个整数 $n, m, s, t$，分别表示点数、边数、起点和终点。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示点 $u$ 与点 $v$ 之间有一条无向边。

• $1 \le T$
• $1 \le n \le 500$
• $1\le \sum n \le 2000$
• $n-1 \le m \le \binom{n}{2}$
• $1 \le s, t \le n$，$s \ne t$
• $1 \le u, v \le n$，$u \ne v$
• 保证图中无重边、无自环
• 保证 $s$ 和 $t$ 连通

输出格式

对于每组测试数据，输出一行两个整数，用空格隔开，分别表示满足条件的路径的闭邻域的最小值和取得该最小值的路径数量。

由于路径数量可能很大，请将其对 $998244353$ 取模后输出。

样例输入

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

样例输出

4 1
6 1
6 4

提示

这是第二组样例的图与解释：

两条从 $1$ 到 $6$ 的最短路径如下：

最短路径	闭临域
1→2→4→6	{1,2,3,4,5,6,7,8}
1→3→5→6	{1,2,3,4,5,6}

可以发现，路径 1→3→5→6 的闭临域更小，因此最优闭临域大小为 $6$。

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1003