Minimum Edge Graph Copy

Bessie has a connected undirected graph \(G\) with \(N\) nodes numbered \(1\ldots N\) and \(M\) edges. The graph may contain self-loops but no multi-edges. Define the boolean function \(f_G(a,b)\) for every \(1 \le a \le N\) and \(b \ge 0\) such that \(f_G(a,b)\) is true if and only if there exists a path from node \(1\) to node \(a\) that uses exactly \(b\) edges (an edge traversed multiple times is counted as many times as it appears in the path).

Elsie wants to replicate Bessie’s graph by constructing another undirected graph \(G'\) that satisfies \(f_{G'}(a,b)=f_G(a,b)\) for all \(a\) and \(b\). To minimize her effort, she wishes \(G'\) to have the minimum possible number of edges. Your task is to compute the minimum number of edges in such a graph \(G'\).

Observations:

• Let \(d(a)\) be the shortest distance from node \(1\) to node \(a\) in \(G\).
• It is known that in any graph, even without extra added edges, one can always obtain a path from \(1\) to \(a\) of length \(d(a)\); and by backtracking (using the same edge twice) in a tree any additional even number of edges can be added. Thus, when the graph is bipartite (i.e. contains no odd cycle), \(f_G(a,b)=true\) if and only if \(b\ge d(a)\) and \(b-d(a)\) is even.
• If \(G\) is non-bipartite (i.e. it contains an odd cycle – note that a self-loop is an odd cycle of length 1), then \(f_G(a,b)=true\) for all \(b\ge d(a)\).

To preserve the function \(f_G\), the constructed graph \(G'\) must have the same distances \(d(a)\) from node \(1\) as \(G\). A natural candidate is a spanning tree of \(G\), which has \(N-1\) edges, and it allows creation of longer paths by backtracking; however, a spanning tree is bipartite. Therefore:

• If \(G\) is bipartite, then the spanning tree (with \(N-1\) edges) already gives exactly the same set of available path lengths.
• If \(G\) is non-bipartite, then we must introduce an odd cycle in \(G'\) to allow paths of every length \(b\ge d(a)\). The simplest way is to add one extra edge (for example, a self loop or an edge connecting two nodes at the same level in the spanning tree) to the spanning tree. Hence, the minimum number of edges in \(G'\) is \(N\) in this case.

Input Constraints:

<li\(2 \le N \le 10^5\), \(N-1 \le M \le \frac{N^2+N}{2}\)</li>
• There are \(T\) test cases with \(1 \le T \le 5 \cdot 10^4\), and the total \(N\) over all test cases does not exceed \(10^5\) and total \(M\) does not exceed \(2 \cdot 10^5\).

Task: For each test case, output the minimum number of edges in \(G'\). In summary, if \(G\) is bipartite, answer \(N-1\); if \(G\) is non-bipartite, answer \(N\).

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case starts with a line containing two integers \(N\) and \(M\) separated by a space. Then \(M\) lines follow, each containing two integers \(u\) and \(v\) denoting an undirected edge between nodes \(u\) and \(v\). The graph may contain self-loops but no multiple edges.

outputFormat

For each test case, output a single integer representing the minimum number of edges in the constructed graph \(G'\) that satisfies \(f_{G'}(a,b)=f_G(a,b)\) for all \(a\) and \(b\).

sample

3
3 2
1 2
2 3
3 3
1 2
2 3
1 3
2 2
1 2
2 2

2
3
2