解説

カード $i$ ごとに4種類の状態 $j$ があるので、それぞれのカードと状態を合わせて $4i+j$ として別のノードして見ます。

実装としてはUnionFindTreeを用いて、前半では対応するノード同士をマージします。 今回の場合は $4A_{i}+j$ と $4B_{i}+((j-1) \oplus (C_i-1) + 1)$ とマージできます。
後半のクエリでは $4X_i+Y_i$ と $4Z_i+w$ が連結であるような $w$ が存在する場合は $w$ を、存在しない場合は -1 を出力します。

これによって $O(M\alpha(N) + Q\alpha(N))$ で計算することができます。

想定ソースコード