出力数が \(2 \times 10^5\) 以下であることを利用した解法を紹介します。

1 u v のクエリが渡されたとき既に \(u,v\) が同じ連結成分に属している場合、その辺を追加する必要はありません。なぜならばその辺を追加しても新たに行き来可能になる頂点対が現れないためです。

そして、そのように追加する辺を制限するとグラフが常に森として保たれることになるため、各連結成分は木になり、サイズ \(n\) の連結成分に含まれる頂点を幅優先（または深さ優先）探索によって \(O(n)\) で列挙することができます。これは出力数と同等のオーダーであるため、間に合います。

実装上は、管理するグラフとは別に UnionFind(Disjoint Set Union) を用意し、連結成分を管理していくとよいです。そのようにすると \(u,v\) が同じ連結成分に属しているかどうかを高速に判定できます。

実装例 (PyPy3, 734ms)