给定一个具有 $$$n$$$ 个顶点和 $$$m$$$ 个边的无向连通图。该图不包含环(从顶点到自身的边)和多条边(即每对顶点之间不超过一条边)。图的顶点从 $$$1$$$ 到 $$$n$$$ 进行编号。
求从顶点 $$$s$$$ 到 $$$t$$$ 的路径数量,其长度与从 $$$s$$$ 到 $$$t$$$ 的最短路径相差不超过 $$$1$$$。有必要考虑所有合适的路径,即使它们多次经过同一顶点或边(即它们并不简单)。
由 $$$6$$$ 个顶点和 $$$8$$$ 个边组成的图
例如,令 $$$n = 6$$$、$$$m = 8$$$、$$$s = 6$$$ 和 $$$t = 1$$$,并让图形如上图所示。那么从$$$s$$$到$$$t$$$的最短路径长度为$$$1$$$。考虑长度至多 $$$1 + 1 = 2$$$ 的所有路径。
- $$$6 \右箭头 1$$$。路径的长度是$$$1$$$。
- $$$6 \rightarrow 4 \rightarrow 1$$$。路径长度为$$$2$$$。
- $$$6 \rightarrow 2 \rightarrow 1$$$。路径长度为$$$2$$$。
- $$$6 \rightarrow 5 \rightarrow 1$$$。路径长度为$$$2$$$。
总共有 $$$4$$$ 条匹配路径。
输入
测试的第一行包含数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
每个测试用例之前都有一个空行。
测试用例的第一行包含两个数字 $$$n, m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) - 图中顶点和边的数量。
第二行包含两个数字 $$$s$$$ 和 $$$t$$$ ($$$1 \le s, t \le n$$$, $$$s \neq t$$$) - 路径起始和结束顶点的编号。
以下 $$$m$$$ 行包含边的描述:第 $$$i$$$ 行包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$) — 连接第 $$$i$$$ 条边的顶点数。保证图是连通的并且不包含环和重边。
保证输入数据的所有测试用例上的值 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。类似地,保证输入数据的所有测试用例上的值 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个数字 - 从 $$$s$$$ 到 $$$t$$$ 的路径数量,其长度与最短路径的长度相差不超过 $$$1$$$。
由于这个数字可能太大,所以输出它对 $$$10^9 + 7$$$ 取模。
示例
输入 #1
4 4 4 1 4 1 2 3 4 2 3 2 4 6 8 6 1 1 4 1 6 1 5 1 2 5 6 4 6 6 3 2 6 5 6 1 3 3 5 5 4 3 1 4 2 2 1 1 4 8 18 5 1 2 1 3 1 4 2 5 2 6 5 7 3 8 4 6 4 8 7 1 4 4 7 1 6 6 7 3 8 8 5 4 5 4 3 8 2
输出 #1
2 4 1 11