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⋅10^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 ≤ n ≤ 2⋅10^5, n - 1 ≤ m ≤ 5⋅10^5, 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 u_i, v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ 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⋅10^5. The sum of the values of m for all sets of input data in the test does not exceed 5⋅10^5.

Output

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

Example

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B {
	static PrintWriter out = new PrintWriter(System.out);
/*
1
5 6 1 2
1 2
1 3
2 3
3 5
3 4
4 5

1
7 8 3 4
1 2
1 3
2 3
3 5
3 4
4 5
4 6
6 7
 */
	static int N,M,A,B;
	static MagicComponents g;
	public static void main(String[] args) {
		FS in = new FS();
		int T = in.nextInt();
		for(int runs = 1; runs <= T; runs++) {
			N = in.nextInt();
			M = in.nextInt();
			A = in.nextInt()-1;
			B = in.nextInt()-1;
			
			g = new MagicComponents(N);
			for(int i = 0; i < M; i++) {
				int a = in.nextInt()-1;
				int b = in.nextInt()-1;
				g.addEdge(a, b);
			}
			
			g.run();
			boolean aFound = false, bFound = false;
			for(int ii : g.cuts) {
				if(ii == A) aFound = true;
				if(ii == B) bFound = true;
			}
			if(!aFound || !bFound) {
				out.println(0);
				continue;
			}
			
			//bfs from both
			boolean visA[] = bfs(A);
			boolean visB[] = bfs(B);
			long sideA = 0;
			long sideB = 0;
			for(int i = 0; i < N; i++) {
				if(i == A || i == B) continue;
				if(visA[i] && !visB[i]) sideA++;
				if(!visA[i] && visB[i]) sideB++;
			}
			out.println((sideA*sideB));
		}
	
		out.close();
	}
	
	static boolean[] bfs(int st) {
		boolean vis[] = new boolean[N];
		vis[st] = true;
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		q.add(st);
		while(!q.isEmpty()) {
			int v = q.poll();
			for(Edge e : g.adj[v]) {
				if(vis[e.v] || e.v == A || e.v == B) continue;
				vis[e.v] = true;
				q.add(e.v);
			}
		}
		return vis;
	}
	
	
	// Bi-connected Components: Remove any edge, still connected
	// Two-Connected Components: Remove any vertex, still connected
	// Articulation or cut points
	static class Edge {
	  int u, v, id;
	  public Edge(int U, int V, int i) {
	    u = U; v = V; id = i;
	  }
	  @Override
	  public String toString() {
		  return "["+u+"-"+v+"]";
	  }
	}
	static class MagicComponents { // Stack Trick!
	  int num, n, edges;
	  int[] dfsNum, low, vis;
	  ArrayList<Integer> cuts;
	  ArrayList<Edge> bridges, adj[];
	  ArrayList<ArrayList<Edge>> bccs; 
	  ArrayDeque<Edge> eStack;
	  
	  MagicComponents(int N) {
	    adj = new ArrayList[n = N];
	    for (int i = 0; i < n; i++)
	      adj[i] = new ArrayList<>();
	    edges = 0;
	  }
	  
	  void addEdge(int u, int v) {
	    adj[u].add(new Edge(u, v, edges));
	    adj[v].add(new Edge(v, u, edges++));
	  }
	  
	  void run() {
	    vis = new int[n];
	    dfsNum = new int[n];
	    low = new int[n];
	    bridges = new ArrayList<>();
	    cuts = new ArrayList<>();
	    bccs = new ArrayList<>();
	    eStack = new ArrayDeque<>();
	    num = 0;
	    
	    for (int i = 0; i < n; i++) {
	      if (vis[i] != 0) continue;
	      dfs(i, -1);
	    }
	  }
	  
	  void dfs(int node, int par) {
	    dfsNum[node] = low[node] = num++;
	    vis[node] = 1;
	    int nChild = 0;
	    for(Edge e : adj[node]) {
	      if(e.v == par) continue;
	      if(vis[e.v] == 0) {
	        ++nChild; eStack.push(e); dfs(e.v, node);
	        low[node] = Math.min(low[node], low[e.v]);
	        if(low[e.v] >= dfsNum[node]) {
	          if(dfsNum[node] > 0 || nChild > 1)
	            cuts.add(node);
	          if(low[e.v] > dfsNum[node]) {
	            bridges.add(e); pop(node);
	          } else pop(node);
	        }
	      } else if(vis[e.v] == 1) {
	        low[node] = Math.min(low[node], dfsNum[e.v]);
	        eStack.push(e);
	      } 
	    }
	    vis[node] = 2;
	  }

	  void pop(int u) {
	    ArrayList<Edge> list = new ArrayList<>();
	    for (;;) {
	      Edge e = eStack.pop(); list.add(e);
	      if(e.u == u) break;
	    }
	    bccs.add(list);
	  }
	    
	  //# Make sure to call run before calling this function.
	  // Function returns a new graph such that all two connected
	  // components are compressed into one node and all bridges
	  // in the previous graph are the only edges connecting the
	  // components in the new tree.
	  // map is an integer array that will store the mapping
	  // for each node in the old graph into the new graph. //$
	  MagicComponents componentTree(int[] map) {
	    boolean[] vis = new boolean[edges];
	    for(Edge e : bridges) vis[e.id] = true;

	    int numComp = 0;
	    Arrays.fill(map, -1);
	    for(int i = 0; i < n; ++i) {
	      if(map[i] == -1) {
	        ArrayDeque<Integer> q = new ArrayDeque<>();
	        q.add(i);
	        map[i] = numComp;
	        while(!q.isEmpty()) {
	          int node = q.poll();
	          for(Edge e : adj[node]) {
	            if(!vis[e.id] && map[e.v] == -1) {
	              vis[e.id] = true;
	              map[e.v] = numComp;
	              q.add(e.v);
	            }
	          }
	        }
	        ++numComp;
	      }
	    }
	    
	    MagicComponents g = new MagicComponents(numComp);
	    Arrays.fill(vis, false);
	    for(int i = 0; i < n; ++i) {
	      for(Edge e : adj[i]){
	        if(!vis[e.id] && map[e.v] < map[e.u]) {
	          vis[e.id] = true;
	          g.addEdge(map[e.v], map[e.u]);
	        }
	      }
	    }
	    
	    return g;
	  }
	  
	  //# Make sure to call run before calling this function.
	  // Function returns a new graph such that all biconnected 
	  // components are compressed into one node. Cut nodes will 
	  // be in multiple components, so these nodes will also have 
	  // their own component by themselves. Edges in the graph 
	  // represent components to articulation points 
	  // map is an integer array that will store the mapping
	  // for each node in the old graph into the new graph.
	  // Cut points to their special component, and every other node
	  // to their specific component. //$
	  MagicComponents bccTree(int[] map) {
	    int[] cut = new int[n];
	    Arrays.fill(cut, -1);
	    int size = bccs.size();
	    for(int i : cuts) map[i] = cut[i] = size++;
	    MagicComponents g = new MagicComponents(size);
	    int[] used = new int[n];
	    for(int i = 0; i < bccs.size(); ++i) {
	      ArrayList<Edge> list = bccs.get(i);
	      for(Edge e: list) {
	        for(int node : new int[] {e.u, e.v}) {
	          if(used[node] != i+1) {
	            used[node] = i+1;
	            if(cut[node] != -1)
	              g.addEdge(i, cut[node]);
	            else map[node] = i;
	          }
	        }
	      }
	    }
	    return g;
	  }
	}
	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {st = new StringTokenizer(br.readLine());}
				catch(Exception e) { throw null;}
			}
			return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next());}
		double nextDouble() { return Double.parseDouble(next());}
		long nextLong() { return Long.parseLong(next());}
		int[] NIA(int n) {
			int r[] = new int[n];
			for(int i = 0; i < n; i++) r[i] = nextInt();
			return r;
		}
		long[] NLA(int n) {
			long r[] = new long[n];
			for(int i = 0; i < n; i++) r[i] = nextLong();
			return r;
		}
		char[][] grid(int r, int c){
			char res[][] = new char[r][c];
			for(int i = 0; i < r; i++) {
				char l[] = next().toCharArray();
				for(int j = 0; j < c; j++) {
					res[i][j] = l[j];
				}
			}
			return res;
		}
	}
	
}
