← 返回题目列表

Codeforces · 1650/G

G. 计数快捷键

中文机器翻译题面 查看原题

给定一个具有 $$$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