Non-academic Problem
Contest: Codeforces Round 954 (Div. 3)
Difficulty rating: 1900
Tags: dfs and similar, graphs, trees

You are given a connected undirected graph, the vertices of which are numbered with integers from $$$1$$$ to $$$n$$$. Your task is to minimize the number of pairs of vertices $$$1 \leq u < v \leq n$$$ between which there exists a path in this graph. To achieve this, you can remove exactly one edge from the graph.

Find the smallest number of pairs of vertices!

Input format:
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq \min(10^5, \frac{n \cdot (n - 1)}{2})$$$) — the number of vertices in the graph and the number of edges.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n, u \neq v$$$), indicating that there is an undirected edge in the graph between vertices $$$u$$$ and $$$v$$$.

It is guaranteed that the given graph is connected and without multiple edges.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all sets of input data does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each set of input data, output the smallest number of pairs of reachable vertices, if exactly one edge can be removed.

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

Note:
In the first set of input data, we will remove the single edge $$$(1, 2)$$$ and the only pair of vertices $$$(1, 2)$$$ will become unreachable from each other.

In the second set of input data, no matter which edge we remove, all vertices will be reachable from each other.

In the fourth set of input data, the graph looks like this initially.

We will remove the edge $$$(3, 4)$$$ and then the only reachable pairs of vertices will be $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$, $$$(5, 6)$$$.

In the sixth set of input data, the graph looks like this initially.

After removing the edge $$$(2, 4)$$$, the graph will look like this. Thus, there will be $$$21$$$ pairs of reachable vertices.

Example input:
6
2 1
1 2
3 3
1 2
2 3
1 3
5 5
1 2
1 3
3 4
4 5
5 3
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
5 5
1 2
1 3
2 3
2 4
3 5
10 12
1 2
1 3
2 3
2 4
4 5
5 6
6 7
7 4
3 8
8 9
9 10
10 8

Example output:
0
3
4
6
6
21

Editorial:
Notice that if an edge is not a bridge, then after its removal the graph remains connected and all vertices are reachable from each other.
Therefore, we would like to remove some bridge edge (if there are no bridges, the answer is $$$\frac{n \cdot (n - 1)}{2}$$$). After its removal, the graph will split into two connected components, let their sizes be $$$x$$$ and $$$y$$$ (note that $$$x + y = n$$$). Then the number of pairs of vertices reachable from each other will be equal to $$$\frac{x \cdot (x - 1)}{2} + \frac{y \cdot (y - 1)}{2}$$$. Let's find all the bridges in the graph, run a $$$dfs$$$ from an arbitrary vertex and calculate for each vertex the size of its subtree in the $$$dfs$$$ traversal tree (denote the size of the subtree of vertex $$$v$$$ as $$$sz_v$$$). Thus, for each bridge, we can find $$$x$$$ and $$$y$$$, knowing the sizes of the subtrees (if the edge $$$(u, v)$$$ is a bridge, then $$$x = \min(sz_x, sz_y), y = n - x$$$). For all bridges, output the smallest answer.