題意を満たすような移動経路が可能であるとき、その過程で「初めて \(2\) 回訪れる頂点」が必ず存在します。

このときの動作で、移動先の頂点は最初の色と反転しており、移動元の頂点は最初の色のままであることから、最初の状態でこれらの \(2\) 頂点は同じ色であることが必要です。また、それ以前の動作においては、全ての頂点が初めて訪れる頂点であることから、それまでに訪れた頂点は最初の時点での色が交互であるはずです。すなわち、「初めて \(2\) 回訪れる頂点」にたどたどり着くまでに、最初のグラフの状態で見れば

• 異なる色の頂点間の辺のみをいくつかたどって移動する
• 最後に、同じ色の頂点間の辺を \(1\) つたどって移動する

という経路で移動しています。

逆に、上記のような経路があるとき、この経路の最後の点を出発点に定めれば、題意を満たす移動経路になっています。

したがって、最初のグラフ上で、異なる色の頂点間の辺のみを結んでいくつかの連結成分を作ったとき、同じ連結成分内を結ぶような同じ色の頂点間の辺が存在すれば、題意を満たす移動経路が存在します。これは unionfind などを用いて判定することができます。