Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, it should output one. (It should not output all the cycles in the graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges. Your proof of correctness must consider two cases:

(a) The graph does not contain a cycle: in this case, you should prove that your algorithm correctly reports this fact.

(b) The graph contains one or more cycles: in this case, you must prove that the algorithm correctly computes one of the cycles in the graph. If the graph contains many cycles, it is enough to report one of the cycles.