题目描述
Problem Background
「{*^$&#$~!@ovo} (Do they also have a road network? Interesting.)」
「{&%#@~akoio!@} (Let's finish the work at hand first, and deal with distractions later.)」
「{!%_&#%@yw?} (Did you not study Chinese well?)」
Under the azure sky, people are unaware of the impending danger.
Problem Description
An adversarial civilization has been angered. They plan to destroy Earth's road network in an interesting way. Earth's road network can be approximated as a forest with $n$ nodes and $m$ undirected edges. They intend to use the following two operations:
- Destroy all roads connected to city $u$.
- Build a new road between cities $u$ and $v$.
to transform Earth's road network into the least efficient form: a single chain. Unfortunately, their intelligence is not very high. Therefore, they have captured you and demanded that you provide a plan with the minimum number of operations. In desperation, you decide to write a program to help them calculate the result.
Input Format
Input is read from the standard input.
The first line contains two positive integers $n$ and $m$.
The next $m$ lines each contain two positive integers $u$ and $v$, indicating an undirected road between cities $u$ and $v$.
Output Format
Output is written to the standard output.
Output a single integer on one line, representing the minimum number of operations required by the aliens.
Sample Input and Output
Sample Input #1
3 1
1 2
Sample Output #1
1
Sample Input #2
See the attached file traffic2.in
Sample Output #2
See the attached file traffic2.ans
Sample Input #3
See the attached file traffic3.in
Sample Output #3
See the attached file traffic3.ans
Notes
[Sample Explanation]
- Sample 1 Explanation:
Initial graph:
Perform operation two on cities $2$ and $3$.
The graph is now a single chain.
[Data Range]
For $100\%$ of the data, $0 \le m < n \le 2 \times 10^6$ and the input is guaranteed to be valid.
| Test Point Number | $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 \times 10^6$ | None |
- Special Property A: Each connected component is a binary tree.
- Special Property B: The degree of each vertex does not exceed $2$.
[Hint]
This problem has a large I/O volume, and it is recommended to use fast I/O methods.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分