Problem Description

You are a city planner tasked with optimizing the road network of Bridge City. The city has n intersections (nodes) connected by m roads (edges). However, the current road network has too many redundant connections creating traffic loops and inefficiencies.

Your goal is to remove the minimum number of roads to eliminate all cycles in the network while keeping all intersections reachable. An acyclic road network (tree or forest) is more efficient for traffic flow and maintenance.

Given the current road network, determine the minimum number of roads that must be removed to make the entire network acyclic.

Input Format

First line: n m (cities, roads). Next m lines: u v (road between cities u and v).

Output Format

Minimum number of roads to remove to make the graph acyclic.

Constraints

• 1 ≤ n ≤ 1000

• 0 ≤ m ≤ 5000

• Cities numbered 1 to n

• Roads are undirected

• Find minimum spanning forest

Sample Input/Output

4 5
1 2
2 3
3 4
4 1
2 4

2

Explanation

In this problem, we need to find the minimum number of edges to remove to make the graph acyclic.

Key insights:
1. An acyclic graph with n nodes can have at most n-1 edges (this forms a tree)
2. If the graph has multiple connected components, each component can be a tree
3. For a graph with c connected components, the maximum number of edges in an acyclic version is n-c
4. Therefore, minimum edges to remove = total_edges - (n - connected_components)

In the sample:
- 4 nodes, 5 edges, 1 connected component
- Maximum acyclic edges = 4 - 1 = 3
- Edges to remove = 5 - 3 = 2