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.


-----Input-----

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$.


-----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

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline

from collections import deque

t=int(input())
for testcaess in range(t):
    n,m,a,b=list(map(int,input().split()))
    E=[[] for i in range(n+1)]

    for i in range(m):
        x,y=list(map(int,input().split()))
        E[x].append(y)
        E[y].append(x)

    USE1=[0]*(n+1)

    Q=deque()
    Q.append(a)

    USE1[a]=1

    while Q:
        x=Q.pop()

        for to in E[x]:
            if to==b:
                continue
            if USE1[to]==0:
                USE1[to]=1
                Q.append(to)

    USE2=[0]*(n+1)

    Q=deque()
    Q.append(b)

    USE2[b]=1

    while Q:
        x=Q.pop()

        for to in E[x]:
            if to==a:
                continue
            if USE2[to]==0:
                USE2[to]=1
                Q.append(to)

    #print(USE1,USE2)

    ANS1=0
    ANS2=0

    for i in range(n+1):
        if i==a or i==b:
            continue
        if USE1[i]==1 and USE2[i]==0:
            ANS1+=1
        elif USE1[i]==0 and USE2[i]==1:
            ANS2+=1

    print(ANS1*ANS2)
        

    

    


import sys
readline = sys.stdin.readline

def dfs(s, t, Edge):
    N = len(Edge)
    used = [0]*N
    used[s] = 1
    used[t] = 1
    stack = [s]
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if not used[vf]:
                used[vf] = 1
                stack.append(vf)
    return used

T = int(readline())
Ans = [None]*T
for qu in range(T): 
    N, M, A, B = map(int, readline().split())
    A -= 1
    B -= 1
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().split())
        a -= 1
        b -= 1
        Edge[a].append(b)
        Edge[b].append(a)
    sa = dfs(A, B, Edge)
    sb = dfs(B, A, Edge)
    ca = 0
    cb = 0
    for fa, fb in zip(sa, sb):
        if fa == fb:
            continue
        if fa:
            ca += 1
        elif fb:
            cb += 1
    Ans[qu] = ca*cb
print('\n'.join(map(str, Ans)))


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]


for _ in range(inp()):
    N,M,a,b = inpl()
    a -= 1; b -= 1
    a,b = min(a,b), max(a,b)
    UF = UnionFind(N)
    alines = []
    blines = []
    for _ in range(M):
        s,t = inpl()
        s-=1 ; t-=1
        s,t = min(s,t), max(s,t)
        if s == a and t == b: continue
        elif s == a: alines.append(t)
        elif t == a: alines.append(s)
        elif s == b: blines.append(t)
        elif t == b: blines.append(s)
        else:
            UF.Unite(s,t)

    aconnects = set()
    acnts = [0]*N
    bcnts = [0]*N

    for a in alines:
        r = UF.Find(a)
        aconnects.add(r)
        acnts[r] = UF.Size(r)

    for b in blines:
        r = UF.Find(b)
        if r in aconnects:
            acnts[r] = 0
        else:
            bcnts[r] = UF.Size(r)

    print(sum(acnts) * sum(bcnts))