Problem 1 Paths of length one (10 points) You are given an undirected graph G(V, E). Your job is to turn this into a directed graph by specifying the direction of each edge. You have to assign directions, such that there is no directed path of length 2 or higher in the graph. That is, every node has either zero indegree or zero outdegree. (a) (2 points) Show two examples; one where there exist such an assignment of directions, and one where it is impossible to assign directions without creating a paths. Make sure you explain why it is possible/impossible. (b) ( 8 points) Find an algorithm that either finds an assignment of edge directions or finds that it is impossible to do