Consider the following problem: INPUT: - directed, unweighted graph G (V, E). Note that the graph is unweighted. Moreover, every vertex in the graph is either red or black. You can access the color of a vertex v in O(1) time by looking at v.color. So for each vertex v, v.color is either "red" or "black" Two vertices s, t. = OUTPUT: output TRUE if there exists a path s to t that contains at most V red vertices. Output FALSE otherwise. Note that you don't need to output a path; you just need to determine if one exists. The Problem: Write pseudocode for an algorithm which solves the above problem in time O(|E| log(V)). For this problem you must use graph transformation. That is, your algorithm should create a new graph G', and then run an existing graph algorithm from our library on G'; that is, the algorithm you run on G' should be one of the graph algorithms in our library, without any modifications to that algorithm. OPTIONAL ASSUMPTION: If it makes things easier for you, you can assume that both s and t are colored black. If your algorithm requires this optional assumption, please write at the beginning of your solution "I am using the optional assumption that s and t are colored black". You will not lose any points for making this assumption. HINT: note that none of the algorithms in our library work on graphs where the vertices have colors. This means that in G' the vertices will not be colored. G' will also be different from G in several other ways as well. HINT: first think about how you would solve this problem if all vertices were red; in this case, you just want to figure out if there is an st path with at most n vertices. This is significantly easier, and you can do it without any graph transformation just by calling one of the algorithms from our library directly on G. Now think about the harder case where only some vertices are red and think about how graph transformation can help here. HINT: In the solution I have in mind, the graph G' you construct will have edge-weights. You will also have to add some additional vertices and edges. HINT: this problem might look similar to problem 4 because in both you have colored vertices, but it's really not. In that problem we have a DAG; here we do not. In that problem the input graph G is weighted; here the input graph G is unweighted. Most importantly, in this problem you need to use graph transformation, whereas in that one you should not. So don't expect the solutions of these two problems to have much in common. WHAT TO WRITE: Make sure to very clearly describe the graph G' State what algorithm you are using to compute distances in G' State how to use the distances you computed in G' (previous step) to figure out the solution to the original problem in G.