Background

“{&%#~!@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.

Problem Description

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?

Input Format

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$.

Output Format

Write output to standard output.

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

3 1
1 2

1

见附件中的 traffic2.in

见附件中的 traffic2.ans

见附件中的 traffic3.in

见附件中的 traffic3.ans

Hint

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.

• 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