← 返回题目列表

Codeforces · 1276/B

B. 两个展会

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

Berland 有 $$$n$$$ 个城市,其中一些城市通过双向道路连接。保证您可以沿着道路从任何城市前往任何其他城市。城市编号从 $$$1$$$ 到 $$$n$$$。

Berland 目前正在举办两场博览会 — 它们在两个不同的城市 $$$a$$$ 和 $$$b$$$ 举行($$$1 \le a, b \le n$$$; $$$a \ne b$$$)。

求 $$$x$$$ 和 $$$y$$$ 城市对的数量 ($$$x \ne a, x \ne b, y \ne a, y \ne b$$$),这样如果您从 $$$x$$$ 到 $$$y$$$,您将必须经历两个展会(访问顺序无关紧要)。形式上,您需要找到城市对 $$$x,y$$$ 的数量,使得从 $$$x$$$ 到 $$$y$$$ 的任何路径都经过 $$$a$$$ 和 $$$b$$$ (以任意顺序)。

打印所需的对数。一对中两个城市的顺序并不重要,也就是说,对 $$$(x,y)$$$ 和 $$$(y,x)$$$ 必须仅考虑一次。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 4\cdot10^4$$$) — 输入中测试用例的数量。接下来,指定 $$$t$$$ 测试用例。

每个测试用例的第一行包含四个整数 $$$n$$$、$$$m$$$、$$$a$$$ 和 $$$b$$$ ($$$4 \le n \le 2\cdot10^5$$$, $$$n - 1 \le m \le 5\cdot10^5$$$, $$$1 \le a,b \le n$$$, $$$a \ne b$$$) — Berland 的城市和道路数量以及举办博览会的两个城市的数量。

以下 $$$m$$$ 行包含城市之间道路的描述。每条道路描述都包含一对整数 $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) - 由道路连接的城市数量。

每条道路都是双向的,连接两个不同的城市。确保您可以从任何城市通过公路到达任何其他城市。一对城市之间可以有多条道路。

测试中所有组输入数据的$$$n$$$的值之和不超过$$$2\cdot10^5$$$。测试中所有组输入数据$$$m$$$的值之和不超过$$$5\cdot10^5$$$。

输出

打印 $$$t$$$ 整数 — 按照输入中写入的顺序给出给定测试用例的答案。

示例

输入 #1

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

输出 #1

4
0
1