a) Suppose that there are 4 students, {A,B,C,D}, and 2 graduation projects, {q,r}. Each student x specifies a set P(x) of projects to work on. For each project y, its supervisor specifies a set S(y) of students to work with: A:{q,r}B:{r}C:{q,r}D:{r}q:{A,C}r:{B,C,D} Explain (step by step, showing each iteration) how the Edmonds-Karp algorithm can be used to assign projects to the maximum number of students, such that the following conditions hold: - no student is matched to two different projects, - no project is assigned to two different students, - no student x is matched to a project that is not in P(x), and - no project y is assigned to a student that is not in S(y). ) What is the worst-case asymptotic time complexity of using the Edmonds-Karp algorithm to assign m students to m projects, subject to the conditions in (a) above? Please explain. c) Prove that the following problem is NP-hard: Given a graph G and a positive integer k, is there a spanning tree of G that contains at most k leaves