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$-$Dists, 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)$