CF1276B Two Fairs

在 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$ 的任意路径都必须经过 $a$ 和 $b$（经过的顺序不限）。形式化地说，你需要求出有多少对城市 $x, y$，使得从 $x$ 到 $y$ 的任意路径都经过 $a$ 和 $b$（顺序不限）。 请输出所需的对数。对于一对城市，$(x, y)$ 和 $(y, x)$ 只算一次。

输入的第一行包含一个整数 $t$（$1 \le t \le 4 \cdot 10^4$），表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含四个整数 $n$、$m$、$a$ 和 $b$（$4 \le n \le 2 \cdot 10^5$，$n - 1 \le m \le 5 \cdot 10^5$，$1 \le a, b \le n$，$a \ne b$），分别表示城市数、道路数以及两个集市所在的城市编号。 接下来的 $m$ 行，每行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示一条连接城市 $u_i$ 和 $v_i$ 的双向道路。 每条道路都是双向的，且连接两个不同的城市。保证任意两个城市之间都可以通过道路连通。两个城市之间可能有多条道路。 所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 的总和不超过 $5 \cdot 10^5$。

输出 $t$ 个整数，按输入顺序分别表示每个测试用例的答案。

由 ChatGPT 4.1 翻译