CF1276B Two Fairs

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.