1. Let G = (V, E) be an undirected (not necessarily connected) graph with each edge colored either blue or red. We are interested in whether the vertices in V can be assigned to two categories: C1 and C2. We take a blue edge (u, v) to mean that u and v should be in the same category, while we take a red edge (u, v) to mean that u and v should be in different categories. G is assignable if there is an assignment of vertices to C1 and C2 such that the meaning of the edges is correct; G is unassignable otherwise.

D. Using BFS or DFS, design an algorithm Assignable to solve Assignability. Write Assignable in pseudocode. Explain the major changes required to either BFS or DFS to achieve your Assignable algorithm.

E. Analyze the worst-case time complexity of Assignable.