まず素朴なbitset解法として以下があります。

• 長さ\(N\)のbitsetを\(N\)本用意する(\(BS\)とする)
  
• クエリ1で\(u\), \(v\) 間に辺が張られるとき、\( BS[u][v] \) と \(BS[v][u]\) を1にする
  
• クエリ2で \(u\), \(v\) が与えられるとき、\(BS[u]\) と \(BS[v]\) のbitwise ANDが1となっている箇所を答える
  
  

これは空間・時間計算量ともに \(O(\frac{N^2}{w})\) ですが、今回の制約ではメモリ使用量が最大ケースでおよそ\(1200\)MBであり、MLEとなってしまいます。

そこで次数が \(B = 100\) に満たない頂点は素直に隣接リストで管理し、次数が\(B\) に到達したらbitsetを作成することを考えます。
するとbitsetの数は \(1000\) 個以下となり、メモリ制約を満たすことができます。
リスト同士の比較はソートしてから二分探索をすることでクエリあたり \(O(B\log{B})\) で比較でき、リストとbitsetとの比較ではリストの各要素ごとにbitsetの値を確認すればよいので \(O(B)\) となります。

以上より空間計算量 \(O(\frac{N^2}{wB}+NB)\) 、時間計算量 \(O(QB\log{B} + \frac{N^2}{w})\) でこの問題に答えることができ、メモリ制限および実行時間制限に間に合います。

実装 (11.7MB, 172ms)