Minimum Operations to Transform a Forest into a Chain

The Earth’s road network can be approximated as a forest with \(n\) nodes and \(m\) undirected edges. Two types of operations are allowed:

• Bomb operation: Bomb a city \(u\) to remove all roads incident to it.
• Add operation: Build a new road between cities \(u\) and \(v\).

The goal is to transform the given forest into a chain (i.e. a simple path spanning all \(n\) nodes). A chain is a connected graph in which exactly two vertices have degree 1 (the endpoints) and all other vertices have degree 2.

Because the enemy’s intelligence is not very high, they require you to find the minimum number of operations needed to achieve this.

Hint: You may connect the forest’s components (if there are \(r\) components, at least \(r-1\) add operations are needed) and then fix the internal structure. In any tree, if the longest simple path (the diameter) has length \(L\) (in terms of nodes), then the remaining \(q - L\) nodes (where \(q\) is the size of that tree) must be reattached by first bombing them (removing their only connection) and then adding an edge back. This incurs a cost of 2 operations per such node. Overall, if the forest has components \(C_1, C_2, \dots, C_r\), with sizes \(q_i\) and diameters (in nodes) \(L_i\), the answer is:

[ \text{answer} = (r-1) + 2\Bigl(n - \sum_{i=1}^{r} L_i\Bigr). ]

You are to compute and output this minimum number.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of nodes and edges, respectively). The next \(m\) lines each contain two integers \(u\) and \(v\) indicating an undirected edge between cities \(u\) and \(v\). It is guaranteed that the given graph is a forest.

outputFormat

Output a single integer representing the minimum number of operations required to transform the forest into a chain.

sample

1 0

0