CF1650G.Counting Shortcuts

Given an undirected connected graph with $n$ vertices and $m$ edges. The graph contains no loops (edges from a vertex to itself) and multiple edges (i.e. no more than one edge between each pair of vertices). The vertices of the graph are numbered from $1$ to $n$.

Find the number of paths from a vertex $s$ to $t$ whose length differs from the shortest path from $s$ to $t$ by no more than $1$. It is necessary to consider all suitable paths, even if they pass through the same vertex or edge more than once (i.e. they are not simple).

Graph consisting of $6$ of vertices and $8$ of edges

For example, let $n = 6$, $m = 8$, $s = 6$ and $t = 1$, and let the graph look like the figure above. Then the length of the shortest path from $s$ to $t$ is $1$. Consider all paths whose length is at most $1 + 1 = 2$.

• $6 \rightarrow 1$. The length of the path is $1$.
• $6 \rightarrow 4 \rightarrow 1$. Path length is $2$.
• $6 \rightarrow 2 \rightarrow 1$. Path length is $2$.
• $6 \rightarrow 5 \rightarrow 1$. Path length is $2$.

There is a total of $4$ of matching paths.

给定一个包含 $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 \rightarrow 1$：路径长度为 $1$。
• $6 \rightarrow 4 \rightarrow 1$：路径长度为 $2$。
• $6 \rightarrow 2 \rightarrow 1$：路径长度为 $2$。
• $6 \rightarrow 5 \rightarrow 1$：路径长度为 $2$。

共有 $4$ 条满足条件的路径。

The first line of test contains the number $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

Before each test case, there is a blank line.

The first line of test case contains two numbers $n, m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$) —the number of vertices and edges in the graph.

The second line contains two numbers $s$ and $t$ ($1 \le s, t \le n$, $s \neq t$) —the numbers of the start and end vertices of the path.

The following $m$ lines contain descriptions of edges: the $i$th line contains two integers $u_i$, $v_i$ ($1 \le u_i,v_i \le n$) — the numbers of vertices that connect the $i$th edge. It is guaranteed that the graph is connected and does not contain loops and multiple edges.

It is guaranteed that the sum of values $n$ on all test cases of input data does not exceed $2 \cdot 10^5$. Similarly, it is guaranteed that the sum of values $m$ on all test cases of input data does not exceed $2 \cdot 10^5$.

测试的第一行包含一个数字 $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$。

For each test case, output a single number — the number of paths from $s$ to $t$ such that their length differs from the length of the shortest path by no more than $1$.

Since this number may be too large, output it modulo $10^9 + 7$.

对于每个测试用例，输出一个整数——即从 $s$ 到 $t$ 的路径数量，这些路径的长度与最短路径长度之差不超过 $1$。

由于该数值可能过大，请对 $10^9 + 7$ 取模后输出。