Minimum Roads to Reinforce

You are given a kingdom represented as an undirected graph with N cities and M bidirectional roads. The kingdom is considered connected if there is a path between any two cities. However, if any one road fails (i.e., is removed), the kingdom might become disconnected.

To prevent this, certain roads, called bridges, must be reinforced. A road connecting cities u and v is a bridge if its removal increases the number of connected components in the graph. In other words, an edge (u, v) is a bridge if and only if, in a depth-first search, it satisfies the condition:

Your task is to determine the minimum number of roads that need to be reinforced so that the kingdom remains connected even after any single road failure. This is equivalent to counting the number of bridges in the graph.

inputFormat

The first line of input contains two integers, N and M, representing the number of cities and the number of roads, respectively. Following this, there are M lines, each containing two integers u and v (1-based indexing) indicating that there is a road between city u and city v.

outputFormat

Output a single integer denoting the minimum number of roads that need to be reinforced (i.e. the number of bridges in the graph).

4 4
1 2
2 3
3 4
4 2

1