1. Let G = (V. E) be directed graph. Each node v E V is given a color from {0, 1, 2, ..., k}; let c(v) denote the color of v. Let X and Y be two non-empty sets of nodes where Xny =0. . Describe an efficient algorithm that given G, the colors c(v), v e V, and X, Y, checks whether there is a path from some node u E X to some node v E Y such that the path contains at most three nodes with colors that are not 0. Ideally your algorithm should run in O(n + m) time where n = [V| and m = |E). Do not try to invent a new algorithm. Come up with a way to create a new graph G' and use a standard algorithm on G'. . Here is a small variation where edges are colored instead of vertices. That is, now each edge e E E has a color c(e) where c(e) E {0, 1, 2,...,k} (the nodes do not have colors). Now the goal is to check whether there is a path from some node in X to some node in Y such that the path contains at most three edges with colors that are not 0. Reduce the problem to the one in the previous part