Similarly colored paths in a DAG Is there an algorithm that can efficiently solve the following question?

Given a directed acyclic graph G with n vertices each assigned a random color from a set of size &lt;= n - 1 colors, a source vertex s, and two distinct vertices a and b both having the same color and reachable from s. 

Determine if there exists at least one path from s to a and one path from s to b that have the same sequence of vertex colors.
Hint:


   Use the techniques in How hard is finding the shortest path in a graph matching a given regular language?.