Definition $1.$ We say a graph G $=($V$,$E$)$ is $2-$colorable if there exists a function Color : V $->\{$Red$,$ Blue$\}$

such that for any edge $($u$,$ v$)$ in E$,$ it holds that Color$($u$)=$ Color$($v$).$ Moreover, such a function is called a valid

$2-$coloring.

Problem $1.$ Given an unweighted, directed graph G $=($V$,$E$)$ and a vertex s in V as input, BFS$-$Dist algorithm

computes the shortest path distance, d$($s$,$ v$),$ between v and s for all vertex v in V $.$

BFS$-$Dist

$$

s$,$G $=($V$,$E$)$

$1.$ d$($s$,$ s$)=0$

$2.$ For v in V $\{$s$\}$: set d$($s$,$ v$)=\backslash$infty $.$

$3.$ Initialize an empty queue, Q$.$

$4.$ Q$.$enque$($s$)$

$5.$ While Q not empty:

$5\mathrm{.}1.$ u $=$ Q$.$deque$()$

$5\mathrm{.}2.$ For $($u$,$w$)$ in E : If d$($s$,$w$)=\backslash$infty $,$ then d$($s$,$w$)=$ d$($s$,$ u$)+1$ and Q$.$enque$($w$)$

$6.$ Return d

Use this algorithm as a subroutine to design an algorithm that given G as above, constructs a $2-$coloring of G$.$

You can assume that the graph is $2-$colorable. $($Point $4)$