We call a connected graph a unicycle if it has the same number of edges as vertices (i.e. it is a tree plus one edge).

Part A Give an algorithm with running time O(n) that takes a unicycle as input, and outputs a minimum spanning tree.

Part B Call a connected graph a near-tree if it has at most 10 more edges than vertices. Give an algorithm with running time O(n) that takes a near-tree as input, and outputs a minimum spanning tree.