Let G$=($V$,$E$)$ be a directed graph where some of the nodes are red, some of the nodes are blue, and the rest are uncolored. A walk in G is balanced if in each prefix of the walk, the $($absolute$)$ difference between the number of red nodes and the number of blue nodes is at most $1.$ Suppose s and t are two distinct uncolored nodes. Design a linear$-$time algorithm to check if there is a balanced s$-$t walk in G$.[$Hint: Define a state machine with states V x $\{0,1,-1\}$ where the second entry represents the red$-$minus$-$blue balance.$]$