Minimum Edges Removal for Tree Transformation

You are given an undirected graph with ( n ) nodes and ( m ) edges. The graph may contain cycles or may be disconnected. Your task is to remove the minimum number of edges so that each connected component becomes a tree. Recall that a tree (or a forest when considering multiple components) is an acyclic graph. In particular, a connected tree with ( k ) nodes has exactly ( k-1 ) edges. You can prove that the minimum number of edges to remove is given by: [ \text{extra_edges} = m - (n - c), ] where ( c ) is the number of connected components in the graph.

The input will be given via standard input and the output should be written to standard output.

inputFormat

The first line contains two integers ( n ) and ( m ) representing the number of nodes and the number of edges, respectively. Each of the following ( m ) lines contains two integers ( u ) and ( v ), indicating that there is an edge between nodes ( u ) and ( v ). Note that the nodes are numbered from 1 to ( n ).

outputFormat

Print a single integer on a new line: the minimum number of edges that need to be removed to transform the given graph into a forest (each connected component is a tree).## sample

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

1