P7417 [USACO21FEB] Minimizing Edges P

Bessie has a connected undirected graph $G$. $G$ has $N$ nodes numbered $1\ldots N$ and $M$ edges ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). $G$ may contain self-loops (an edge that connects a node to itself), but it does not contain multiple edges (multiple edges connecting the same pair of nodes). Let $f_G(a,b)$ be a boolean function. For each $1\le a\le N$ and $0\le b$, the function is true if there exists a path from node $1$ to node $a$ that uses exactly $b$ edges, and false otherwise. If an edge is traversed multiple times, then it is counted that many times. Elsie wants to copy Bessie. Specifically, she wants to construct an undirected graph $G'$ such that for all $a$ and $b$, we have $f_{G'}(a,b)=f_G(a,b)$. Elsie wants to do as little work as possible, so she wants to construct the smallest possible graph. Therefore, your task is to compute the minimum possible number of edges in $G'$. Each input contains $T$ ($1\le T\le 5\cdot 10^4$) independent test cases. It is guaranteed that the sum of $N$ over all test cases does not exceed $10^5$, and the sum of $M$ over all test cases does not exceed $2\cdot 10^5$.

The first line of the input contains $T$, the number of test cases. The first line of each test case contains two integers $N$ and $M$. Each of the next $M$ lines of a test case contains two integers $x$ and $y$ ($1\le x\le y\le N$), indicating that there is an edge connecting $x$ and $y$ in $G$. For readability, adjacent test cases are separated by a blank line.

For each test case, output one line, the minimum possible number of edges in $G'$.

#### Sample 1 Explanation In the first test case, Elsie can construct $G'$ by removing $(2,5)$ from $G$. Alternatively, she can also construct a graph containing the following edges, because she is not restricted to only removing edges from $G$: ``` 1 2 1 4 4 3 4 5 ``` Elsie clearly cannot do better than $N-1$, because $G'$ must also be connected. #### Sample 2 Explanation In the above test cases, Elsie cannot do better than Bessie. #### Subtask Properties - For another $5\%$ of the data, $N\le 5$. - For another $10\%$ of the data, $M=N$. - For another $20\%$ of the data, if it is not true that $f_G(x,b)=f_G(y,b)$ for all $b$, then there exists a $b$ such that $f_G(x,b)$ is true and $f_G(y,b)$ is false. - For another $30\%$ of the data, $N\le 10^2$. - For another $25\%$ of the data, there are no additional constraints. Problem by: Benjamin Qi. Translated by ChatGPT 5