Problem Description

After finishing the paper Sandpile Prediction on Structured Undirected Graphs, Xiaoqingyu wants everyone to solve more graph theory problems. “We cannot live without graph theory problems, and everyone should work on sandpile prediction problems!”

A bipartite graph is a graph that satisfies the following condition: its vertices can be divided into two disjoint sets $U$ and $V$, such that every edge in the graph connects a vertex in $U$ and a vertex in $V$. If the numbers of vertices in $U$ and $V$ are equal, then the graph is called a balanced bipartite graph.

A matching in an undirected graph is a set of edges in which no two edges share a common endpoint. A maximum matching is a matching that contains the largest number of edges. The matching number of a graph is the number of edges in a maximum matching of the graph.

Now, Xiaoqingyu gives you a balanced bipartite graph. You need to add exactly one edge, connecting one vertex in $U$ and one vertex in $V$, so that the matching number of the graph increases. Find the number of ways.

Input Format

There are multiple test cases. The first line contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n,m \le 10^5$), representing the number of vertices in $U$ and $V$, and the number of edges.

In the next $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), indicating that the $i$-th edge connects the $u_i$-th vertex in $U$ and the $v_i$-th vertex in $V$. The graph may contain multiple edges.

It is guaranteed that the sum of $(n + m)$ over all test cases does not exceed $4 \times 10^5$.

Output Format

For each test case, output one line containing one integer, representing the answer.

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

6
0
4

Hint

For the first sample test case, the matching number of the original graph is $2$. By adding the edge $(1, 1)$, $(1, 4)$, $(2, 1)$, $(2, 4)$, $(3, 1)$, or $(3, 4)$, we can increase the matching number to $3$. So the answer is $6$.

For the second sample test case, the matching number of the original graph is $3$. Clearly, we cannot increase the matching number, because all vertices are already in the matching, so the answer is $0$.

For the third sample test case, the matching number of the original graph is $1$. By adding the edge $(2, 1)$, $(2, 3)$, $(3, 1)$, or $(3, 3)$, we can increase the matching number to $2$. So the answer is $4$.

Translated by ChatGPT 5