一、内容

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≤a,b≤n; a≠b).Find the number of pairs of cities x and y (x≠a,x≠b,y≠a,y≠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.

Input

The first line of the input contains an integer t(1≤t≤4⋅104) — 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≤n≤2⋅105, n−1≤m≤5⋅105, 1≤a,b≤n, a≠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 ui,vi (1≤ui,vi≤n, ui≠vi) — numbers of cities connected by the road.The following m lines contain descriptions of roads between cities. Each of road description contains a pair of integers ui,vi (1≤ui,vi≤n, ui≠vi) — numbers of cities connected by the road.

Output

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

Input

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 

Output

4
0
1

二、思路

• 题意：给定一个连通图，再给定2个展览点，问有几对点（x,y）,从x到y点的任意路径必须经过这2个展览点，问一共有多少对。
• 通过a点出发进行dfs，设置b点为禁止点（不能访问）,由于这个图是连通图，任意2点都是可达的，那么从a点出阿发不通过a的能到达的点代表必须经过b才能到达。
• 那么我们统计a点出发不经过b不能到的点（必须经过b才能到的点） * 从b出发不经过a不能到的点（必须经过a才能到的点） = ans

三、代码

#include <cstdio>
typedef long long ll;
const int N = 2e5 + 5, M = 5e5 + 5;
//ans[0]保存a不通过b不能到的点 ans[1]保存b不通过a不能到的点 
int head[N], len, cnt, t, n, m, a, b, u, v, ans[2];
bool vis[N]; //看某个点是否访问过  
struct edge{
	int v, next; 
} e[M * 2];
void add(int u, int v) {
	e[len].v = v;
	e[len].next = head[u];
	head[u] = len++;
} 
void dfs(int u, int ban) {
	cnt++; 
	vis[u] = true;
	for (int j = head[u]; j; j = e[j].next) {
		v = e[j].v;
		if (v == ban) continue; //不能通过ban点
		if (!vis[v]) dfs(v, ban); 
	}
}
int main() {
	scanf("%d", &t);
	while (t--) {
		len = 1; 		
		scanf("%d%d%d%d", &n, &m, &a, &b);
		for (int i = 1; i <= n; i++) head[i] = 0;
		for (int i = 1; i <= m; i++) {
			scanf("%d%d", &u, &v);
			add(u, v);
			add(v, u);
		}
		//统计a不能到达那些点（不通过b）
		for (int i = 1; i <= n; i++) vis[i] = false;
		cnt = 0; //a 能到的点 (不通过b) 
		dfs(a, b);  
		ans[0] = n - cnt - 1; //多减1包括a点 
 		//统计b不能到达那些点 （不通过a）
		for (int i = 1; i <= n; i++) vis[i] = false;
		cnt = 0;
		dfs(b, a); 
		ans[1] = n - cnt - 1;  
		printf("%lld\n", (ll)ans[0] * ans[1]); 
	} 
	return 0;
}