Minimum Redundant Roads Removal

You are given a road network with N intersections and M roads. Each road connects two intersections, and it is possible that some roads are self-loops or duplicate connections that create cycles.

Your task is to remove the minimum number of roads such that for every connected component in the resulting network, there is exactly one simple path between any two intersections. In other words, the remaining roads in each connected component form a tree. A key observation is that if the network were fully connected, the number of roads in a tree is N − 1. More generally, if the network has C connected components, then the sum of roads in the spanning trees is N − C and the number of redundant roads to be removed is

[ R = M - (N - C) ]

Note that self-loops are always redundant.

inputFormat

The input is given from standard input (stdin) and consists of:

1. The first line contains two integers N and M where N is the number of intersections and M is the number of roads.
2. The following M lines each contain two integers u and v (1-indexed) representing a road between intersections u and v.

outputFormat

Output one integer to standard output (stdout), the minimum number of roads to remove such that in each connected component the remaining roads form a tree (i.e. there is exactly one simple path between any two intersections within that component).

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

1