Let G=(V, E) be a directed graph where every node has exactly one incoming edge, and there is a node s that has a directed path to every other node.

a) Draw an example graph with at least 6 nodes that satisfies the condition stated about G. Identify s in your example.

b) Prove that G is not a DAG (Directed Acyclic Graph) For this and subsequent parts, refer to a generic graph G that satisfies the conditons stated above, not the example you drew in part (a)

c) What is the maximum number of edges you need to delete from G so that the resulting graph is a DAG? Your answer should be a specific number, and this number will not depend on the specific graph G, only the assumptions stated about G in the first part. Prove that your answer is correct.

d) Let k be the number of edges that need to be removed (your answer from the previous part). Now give an O(m + n) time algorithm, where n=number of nodes and m=number of edges. to identify the specific set of k edges to delete. Assume only that the graph is given as input, and not the identity of the node s. Explain why your algorithm is correct.