Let G be a directed, unweighted graph with vertex set V and edge set E$.$ Suppose that each edge e has additional attribute e$.$color, which is either red or green. A particular vertex is labelled N for the north pole, and a particular vertex is labelled S for the south pole. The goal is to determine if there is a route from the south pole to the north pole, which consists of edges of all one color, OR$,$ starts on edges of one color, and then switches to edges of another color.

For example, an all$-$red path is acceptable, or a path that starts with red edges, and then switches $($once$)$ to green edges, or a path that starts with green edges and then switches along the way $($once$)$ to red edges, or an all$-$green path.

Your job is to design an algorithm that solves this problem. You do not need to provide pseudo$-$code, but you must carefully described the steps and the inputs to any algorithms from class that you use. Justify the runtime of O$($E $+$ V $).$