例えば、以下のクエリなら UnionFind を用いることで解くことが出来ます。

• タイプ \(a\): 頂点 \(u,v\) を結ぶ無向辺を追加する。
• タイプ \(b\): 頂点 \(u\) から頂点 \(v\) に辺を辿って到達できるか判定する。

なので、 UnionFind を改造してこの問題を解くことを考えましょう。

連結成分ごとに以下の情報を保持すればよいです。

• その連結成分に含まれる黒色の頂点の個数

この情報を保持すれば、タイプ \(3\) のクエリへの返答はその連結成分に黒色の頂点が \(1\) 個以上存在するかどうかを判定することで対応可能です。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/dsu>

using namespace std;
using namespace atcoder;

int main(){
  int n,q;
  cin >> n >> q;
  dsu d(n+1);
  vector<int> c(n+1,0);
  vector<int> s(n+1,0);

  while(q--){
    int typ;
    cin >> typ;
    if(typ==1){
      int u,v;
      cin >> u >> v;
      u=d.leader(u);
      v=d.leader(v);
      if(u!=v){
        d.merge(u,v);
        int w=d.leader(u);
        s[w]=s[u]+s[v];
        s[u^v^w]=0;
      }
    }
    else if(typ==2){
      int u;
      cin >> u;
      s[d.leader(u)]-=c[u];
      c[u]^=1;
      s[d.leader(u)]+=c[u];
    }
    else{
      int u;
      cin >> u;
      if(s[d.leader(u)]){cout << "Yes\n";}
      else{cout << "No\n";}
    }
  }
  return 0;
}