P8595 “KDOI-02” A Road in a Web

“{$&%#$~!@ovo} (They also have a road network? Interesting.)” “{&%#@~akoio!@} (Finish the work you should do first. We will talk about those distracting toys later.)” “{!%_&#%@yw?} (Is your Chinese language not good?)” Under the blue sky, people still do not know that danger is coming.

The hostile civilization has been angered. They want to destroy Earth’s road network in a strange way. Earth’s road network can be approximated as a **forest** with $n$ nodes and $m$ undirected edges. They want to use the following $2$ operations: - Destroy all roads connected outward from a city $u$. - Build a new road between cities $u, v$. They want to change Earth’s road network into the least efficient form: a single chain (path). Now you want to know: to achieve the goal, what is the minimum number of operations they need?

Read input from standard input. The first line contains $2$ positive integers $n, m$. The next $m$ lines each contain $2$ positive integers $u, v$, indicating there is an undirected road between cities $u, v$.

Write output to standard output. Output one line containing one integer, which is the minimum number of operations the aliens need.

**Sample Explanation** + **Sample 1 Explanation:** Initial graph:  Apply operation 2 to cities $2, 3$.  Now it has become a chain. *** **Constraints** For $100\%$ of the testdata, $0 \le m < n \le 2 \times 10^6$, and the input is guaranteed to be valid. |Test Point ID|$n \le$|Special Property| |:-:|:-:|:-:| |$1\sim2$|$10$|A| |$3\sim6$|$500$|None| |$7\sim8$|$10^4$|A| |$9$|$10^4$|B| |$10\sim12$|$10^4$|None| |$13\sim15$|$10^6$|None| |$16\sim20$|$2\times10^6$|None| + Special Property A: Each connected component is guaranteed to be a binary tree. + Special Property B: The degree of each vertex is guaranteed to be at most $2$. **Hint** This problem has a large I/O size, so a faster I/O method is recommended. Translated by ChatGPT 5