Bipartite Graph

Soda has a bipartite graph with $n$ vertices and $m$ undirected edges. Now he wants to make the graph become a complete bipartite graph with most edges by adding some extra edges. Soda needs you to tell him the maximum number of edges he can add.

Note: There must be at most one edge between any pair of vertices both in the new graph and old graph.

There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 100)$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$, $(2 \le n \le 10000, 0 \le m \le 100000)$.

Each of the next $m$ lines contains two integer $u, v$ $(1 \le u, v \le n, v \ne u)$ which means there's an undirected edge between vertex $u$ and vertex $v$.

There's at most one edge between any pair of vertices. Most test cases are small.

For each test case, output the maximum number of edges Soda can add.

2
4 2
1 2
2 3
4 4
1 2
1 4
2 3
3 4

2
0

BestCoder 1st Anniversary ($)