Let G = (V, E) be an undirected graph. Design algorithms for the following (in each case discuss the complexity of your algorithm):

(a) Assume G contains only one cycle. Direct the edges s.t. for each u, indegree(u) 1.

(b) Determine whether it is possible to direct the edges of G s.t. for each u, indegree(u) 1. If it is possible, your algorithm should provide a way to do so.

(c) Let S be a subset of edges s.t. every cycle of G has at least one edge in S. Find a minimum size subset S.