Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. (It should not output all 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 solution must include:

(a) (3 marks) a precise specification of the problem (b) (6 marks) specification of the algorithm (using pseudocode) (c) (6 marks) a proof that your algorithm is correct (if your algorithm is a modification of a known algorithm, your proof of correctness may assume that the known algorithm is correct and focus on arguing that the adaptations solve the new problem), (d) ( marks) a proof that your algorithm runs in time O(mn)