Updated post.

First, find the number of connected components, c. Now, there are 5 cases.

1. c > 3: There is no solution.
2. c = 1: The graph is already connected, so the result is 0.
3. c = 3, cycles in different components: Let's say the components are A, B, and C and the cycles are in A and B. To make graph connected, there are three ways, , or . By , I mean to erase an edge from X which is part of a cycle and connect either of its endpoints to Y. To find an optimal way, you can iterate on edges which are part of the cycle in X, store nodes of Y in sorted order and find the nearest node.
4. c = 3, cycles in the same component: Let's say the components are A, B, and C and the cycles are in A. Say S and T are the sets of edges of two (simple) cycles and P = S - T, Q = T - S, . The possible way is to choose two edges, each from distinct sets (among P, Q, and R), erase them and connect either of their vertices to B and C. So, there are 6 ways basically.
5. c = 2: The components are A and B and the cycle is in A. You can choose an edge from the cycle, erase it and connect either of its vertices to a node in B. There is another possible way, too. Remove an edge from the cycle, join either of its endpoints to a vertex in the trees dangling from the nodes in the cycle, thus, enlarging the cycle. This will give you access to more edges which will be part of the new cycle. For example in the graph here, optimal way is to remove edge (5, 4) and connect (5, 3) instead and then remove (6, 2) and join (6, 1). This will have cost 2.

Accepted solution: 45389010