Ensuring Two Disjoint Routes in a Grazing Field Network

Bessie and her herd currently traverse a network of F grazing fields (numbered from 1 to F) that are connected by R official paths. Each path connects exactly two different fields. Although there is at least one route between any two fields, sometimes the herd is forced to take the same path repeatedly. To solve this, the cows want to add the minimum number of new paths so that between any pair of fields there are at least two separate routes that do not share any common paths (edge‐disjoint routes).

You are given the current configuration of paths (with F and R satisfying 1 ≤ F ≤ 5000 and F-1 ≤ R ≤ 10000). The new path can connect any two fields (even if they are already directly connected by some path). Determine the minimum number of new paths required to ensure that for every pair of fields, there exist at least two distinct routes that do not share any common paths.

Hint: This problem reduces to eliminating all the bridges in the graph and turning the network into a 2-edge-connected graph. One efficient approach is to identify the bridges using a DFS algorithm and then consider the bridge tree of the graph. If the bridge tree has L leaves, the answer is \(\lceil L/2 \rceil\).

inputFormat

The first line of input contains two integers, F and R, representing the number of fields and the number of paths, respectively. The following R lines each contain two integers, u and v, indicating an official path between fields u and v.

Constraints:

• 1 ≤ F ≤ 5000
• F - 1 ≤ R ≤ 10000

outputFormat

Output a single integer, representing the minimum number of new paths that must be built so that for every pair of fields there exist at least two edge-disjoint routes.

sample

4 3
1 2
2 3
3 4

1