各連結成分に対して適当に根を定めることで根付き森とし，各頂点 \(v\) に対してその親 \(par[v]\) を管理することにします（頂点 \(v\) が根のときは \(par[v]=-1\) とします）．マージテクを用いれば各クエリ \(1\) に対して愚直に \(par\) を更新していくことができます．（頂点 \(u,v\) を含む根付き森を \(F_u,F_v\) とし\(F_u\) のサイズが \(F_v\) のサイズより小さいものとします．マージした後の根付き森の根を \(F_v\) の根と同じにすることによって，\(F_u\) に含まれる頂点のみ親を更新すればよくなります．） クエリ \(2\) に対しては

• \(par[v]=par[u]\neq-1\) （答えは \(par[v]\)）
• \(par[par[v]]=u\)（答えは \(par[v]\)）
• \(par[par[u]]=v\)（答えは \(par[u]\)）

のいずれかを満たすかどうかを判定すればよいです．計算量は \(O(N\log N+Q)\) です．

実装例(c++, 55ms) https://atcoder.jp/contests/abc350/submissions/52534640

Bonus： \(N\) 頂点 \(0\) 辺の無向グラフがある．以下の \(2\) 種類のクエリをオンラインで処理せよ．

• クエリ \(1\)：頂点 \(u,v\) の間に辺を追加する．（追加する前は頂点 \(u,v\) は非連結）
• クエリ \(2\)：頂点 \(u,v\) の距離を出力する．（非連結ならその旨を報告）

制約：\(N,Q\leq 10^5\)