After writing the paper Sandpile Prediction on Structured Undirected Graphs, Little Cyan Fish wants everyone to solve more graph theory tasks. "We cannot survive without graph theory problems, and everyone should come to do the sandpile prediction!"
A bipartite graph is a graph whose vertices can be divided into two disjoint sets $$$U$$$ and $$$V$$$, such that every edge in the graph connects a vertex in $$$U$$$ to one in $$$V$$$. If the number of vertices in $$$U$$$ and $$$V$$$ are the same, then this graph is called a balanced bipartite graph.
A matching in an undirected graph is a set of edges, in which any two edges have no common vertices. A maximum matching of the graph is a matching containing the largest possible number of edges. The matching number of a graph is the number of edges in its maximum matching.
Now, Little Cyan Fish gives you a balanced bipartite graph. You are asked to count the number of ways to add exactly one edge between a vertex in $$$U$$$ and a vertex in $$$V$$$, such that the matching number of the graph is increased.
There are multiple test cases. The first line of the input 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$$$) indicating number of vertices in $$$U$$$ and $$$V$$$, and the number of edges.
For the following $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) indicating 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's guaranteed that the sum of $$$(n + m)$$$ of all test cases will not exceed $$$4 \times 10^5$$$.
For each test case output one line containing one integer indicating the answer.
34 31 23 24 33 31 32 23 13 21 21 2
6 0 4
For the first sample test case, the matching number of the original graph is $$$2$$$. By adding 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$$$. Obviously we cannot increase the matching number since all vertices are 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 edge $$$(2, 1)$$$, $$$(2, 3)$$$, $$$(3, 1)$$$ or $$$(3, 3)$$$, we can increase the matching number to $$$2$$$. So the answer is $$$4$$$.
