408335: GYM103098 K Königsberg Bridges

Given a graph, we say it is Königsbergsy if there is a simple path that goes through all of its bridges. Here, a bridge is an edge that disconnects the graph when removed. And recall that a simple path is a path that visits each vertex at most once.

Given a graph $$$G$$$, we want to add some edges to it to make it Königsbergsy. (You may add more than one edge between the same pair of vertices). Determine the maximum number of bridges that the resulting graph can have.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^6$$$; $$$0 \leq m \leq 10^6$$$), the number of vertices and the number of edges of $$$G$$$.

Each of the next $$$m$$$ lines contains two integers $$$u_i, v_i$$$ ($$$0 \leq u_i, v_i \leq n-1$$$), describing an edge between vertices $$$u_i$$$ and $$$v_i$$$.

Output one integer, the maximum number of bridges the resulting graph can have.

4 3
0 1
1 2
2 0

1

4 2
0 1
1 2

3