When there is a desired moving route, the first vertex to be visited twice on the way always exists.

In the move visiting it for the second time, its color has been reversed from its initial color, and the vertex you move from remains its initial color. Therefore, these two vertices must have the same color in the initial state. Also, in all moves before that, all vertices are visited for the first time, so the colors of those vertices should alternate in the initial state. In other words, looking at the initial state of the graph, until you reach the first vertex to be visited twice, you move along a path that:

• follows some edges between vertices of different colors,
• and finally, follows one edge between vertices of the same color.

Conversely, if there is a path as described above, setting the last point of that path as the starting point makes it a desired moving route.

Therefore, on the initial graph, when you create some connected components by spanning only edges between vertices of different colors, if there is an edge between vertices of the same color that connects vertices in the same connected component, there is a desired moving route. You can check this using union-find or similar methods.

(Modified the first draft written by GPT-4.)