Two Fairs

题意翻译

## 题目大意： - 给出一张有 $n$ 个结点、 $m$ 条边的无向联通图； - 图上有两个特殊点 $a$ 和 $b$ （$1\leq a,b\leq n,\ a\neq b$）； - 求出满足下列条件的二元组 $(u,v)$ 的对数： - $1\leq u < v\leq n$； - $u\neq a,v\neq a,u\neq b,v\neq b$ - **任意**一条从 $u$ 到 $v$ 的路径 $(u,e_1,e_2,...,e_k,v)$ 都经过 $a$ 和 $b$ 。 - 包含 $T$ 组测试数据。 ----- ## 数据范围： - $4\leq n \leq 2\times 10^5$ - $\ n-1\leq m\leq 5\times 10^5\ $ - $1\leq T\leq 4\times 10^4$ - $\sum n \leq 2\times 10 ^5,\ \sum m \leq 5\times 10^5$

题目描述

There are $ n $ cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from $ 1 $ to $ n $ . Two fairs are currently taking place in Berland — they are held in two different cities $ a $ and $ b $ ( $ 1 \le a, b \le n $ ; $ a \ne b $ ). Find the number of pairs of cities $ x $ and $ y $ ( $ x \ne a, x \ne b, y \ne a, y \ne b $ ) such that if you go from $ x $ to $ y $ you will have to go through both fairs (the order of visits doesn't matter). Formally, you need to find the number of pairs of cities $ x,y $ such that any path from $ x $ to $ y $ goes through $ a $ and $ b $ (in any order). Print the required number of pairs. The order of two cities in a pair does not matter, that is, the pairs $ (x,y) $ and $ (y,x) $ must be taken into account only once.

输入输出格式

输入格式

The first line of the input contains an integer $ t $ ( $ 1 \le t \le 4\cdot10^4 $ ) — the number of test cases in the input. Next, $ t $ test cases are specified. The first line of each test case contains four integers $ n $ , $ m $ , $ a $ and $ 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 $ ) — numbers of cities and roads in Berland and numbers of two cities where fairs are held, respectively. The following $ m $ lines contain descriptions of roads between cities. Each of road description contains a pair of integers $ u_i, v_i $ ( $ 1 \le u_i, v_i \le n $ , $ u_i \ne v_i $ ) — numbers of cities connected by the road. Each road is bi-directional and connects two different cities. It is guaranteed that from any city you can pass to any other by roads. There can be more than one road between a pair of cities. The sum of the values of $ n $ for all sets of input data in the test does not exceed $ 2\cdot10^5 $ . The sum of the values of $ m $ for all sets of input data in the test does not exceed $ 5\cdot10^5 $ .

输出格式

Print $ t $ integers — the answers to the given test cases in the order they are written in the input.

输入输出样例

输入样例 #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