グラフ \(G\) の連結成分ごとに異なる ID （整数など）を割り当て、ID が \(c\) である連結成分を単に連結成分 \(c\) と呼びます。 また、各頂点 \(w\) について \(w\) が属する連結成分の ID を \(\mathrm{id}(w)\) で表すことにします。 例えば、頂点 \(u, v\) が同じ連結成分に属することは \(\mathrm{id}(u) = \mathrm{id}(v)\) と同値です。

\(G\) に \(2\) 頂点 \(p, q\) を結ぶ辺を追加すると、（ \(\mathrm{id}(p) \neq \mathrm{id}(q)\) であれば）連結成分 \(\mathrm{id}(p)\)と 連結成分 \(\mathrm{id}(q)\) が一つの連結成分に併合されます。

よって、その結果 \(2\) 頂点 \(x_i, y_i\) を結ぶパスが作られないようにするには、非順序対 \(\lbrace \mathrm{id}(p), \mathrm{id}(q) \rbrace\) と非順序対 \(\lbrace \mathrm{id}(x_i), \mathrm{id}(y_i) \rbrace\) が異なることが必要かつ十分です。

したがって、\(2\) 頂点 \(p, q\) を結ぶ辺を追加した後も、良いグラフであり続ける（つまり、全ての \(i = 1, 2, \ldots, K\) で \(2\) 頂点 \(x_i, y_i\) を結ぶパスが存在しない）ようにするには、 非順序対 \(\lbrace \mathrm{id}(p), \mathrm{id}(q) \rbrace\) が、つないではならない連結成分のペアを示す \(K\) 個（重複を許す）の非順序対

\[\lbrace \mathrm{id}(x_1), \mathrm{id}(y_1)\rbrace, \lbrace \mathrm{id}(x_2), \mathrm{id}(y_2)\rbrace, \ldots, \lbrace \mathrm{id}(x_K), \mathrm{id}(y_K)\rbrace　\tag{1} \]

のいずれとも異なることが必要かつ十分です。

そのため、本問題を解くには、(1) に示す \(K\) 個の非順序対の集合 \(S\) をあらかじめ平衡二分木で保持しておき、 各質問 \((p_i, q_i)\) では \(\lbrace \mathrm{id}(p_i), \mathrm{id}(q_i) \rbrace\) が \(S\) に含まれるかどうかを、この平衡二分木へのアクセスによって判定すれば良いです。

連結成分の ID の定め方・求め方について、\(G\) をUnionFindで管理することで、\(G\) の各頂点 \(v\) に対して \(v\) が属する連結成分の代表元が UnionFind の機能から得られるので、これを \(v\) の属する連結成分の ID \(\mathrm{id}(v)\) として用いることができます。