P16312 [ICPC 2023 Jinan R] I Just Want... One More...

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.

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$.

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

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