Two Fairs
Contest: Technocup 2020 - Elimination Round 4
Difficulty rating: 1900
Tags: combinatorics, dfs and similar, dsu, graphs

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 format:
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 format:
Print $$$t$$$ integers — the answers to the given test cases in the order they are written in the input.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example output:
4
0
1

Editorial:
This problem has a simple linear solution (just two depth-first searches) without involving cut points, biconnected components, and other advanced techniques.
Let's reformulate this problem in the language of graph theory: you are given an undirected graph and two vertices $$$a$$$ and $$$b$$$, you need to find the number of pairs of vertices ($$$x, y$$$) such that any path from $$$x$$$ to $$$y$$$ contains both vertices $$$a$$$ and $$$b$$$.
In other words, we are interested in pairs of vertices ($$$x, y$$$) such that deleting the vertex $$$a$$$ (while going from $$$b$$$) breaks the connection from $$$x$$$ to $$$y$$$ and deleting the vertex $$$b$$$ (while going from $$$a$$$) breaks the connection from $$$x$$$ to $$$y$$$.
Let's remove the vertex $$$a$$$ and select the connected components in the resulting graph. Similarly, we remove the vertex $$$ b $$$ and select the connected components in the resulting graph. Then the pair ($$$x, y$$$) interests us if $$$x$$$ and $$$y$$$ belong to different components both when removing $$$a$$$ and when removing $$$b$$$.
Thus, let's find a pair of $$$(\alpha_u, \beta_u)$$$ for each vertex $$$u$$$. It will be numbers of the connected components when $$$a$$$ and $$$b$$$ are removed, respectively. The pair ($$$x, y$$$) interests us if $$$(\alpha_x, \beta_x) \ne (\alpha_y, \beta_y)$$$.
The total number of vertex pairs is $$$n \cdot (n - 1) / 2$$$. Let's subtract the number of uninteresting pairs from it.
Firstly, these are pairs such that $$$(\alpha_x, \beta_x)$$$ and $$$(\alpha_y, \beta_y)$$$ partially equals (in exactly one component). For example, let the equality be on the first component in the common value of $$$\alpha$$$. Let the total number of pairs $$$(\alpha_u, \beta_u)$$$ such that $$$\alpha_u = \alpha$$$ be equal to $$$c$$$, then subtract $$$c \cdot (c-1) / 2$$$ from the current answer. We will do this with all $$$\alpha$$$ and $$$\beta$$$.
Note that some uninteresting pairs were counted twice. These are pairs of vertices such that $$$(\alpha_x, \beta_x)$$$ and $$$(\alpha_y, \beta_y)$$$ equals in both components. We can count the number of corresponding vertices $$$c$$$ and add $$$c \cdot (c-1) / 2$$$ to the current answer for each pair.
In the following code, let $$$p$$$ be an array of pairs of component numbers for all vertices except $$$a$$$ and $$$b$$$. Each pair is the number of the connected component of this vertex if $$$a$$$ is removed, and the number of the connected component of this vertex if $$$b$$$ is removed. Then the main part of the solution can be like this:
To build the array $$$p$$$ we could use the code below: