（この解説は https://blog.brucemerry.org.za/2023/11/ioi-2023-day-1.html と同じものを日本語にしたものです）

$2$ つのパスを管理することを考えます。はじめは $1$ 頂点のパスが $2$ つ、という状況です。ここから、以下のように最大 $2$ 回の質問で頂点を追加します。

• どちらか一方のパスの終点に繋がっているなら、そのパスにつなげる。
• そうでなければ、密度の条件よりパスの終点同士は繋がっているので、パス同士をつなげたのち、追加する頂点は $1$ 頂点のパスとみなす。

これを最後まで繰り返せば、点素な $2$ つのパスを得ることができます。

パス間に辺がなければ、そのグラフは $2$ つの完全グラフなので、大きい方を出力すればよいです。

そうでない場合、端点のつなげ方 $4$ 通りを試し、どれかが可能ならつなげます。不可能であれば、密度の条件よりどちらのパスも始点と終点間に辺が存在し、サイクルになります。

二分探索を用いればサイクル間の辺を $1$ つ見つけることができて、サイクルを切り開いてつなげることができます。以上が $q\leq 550$ の解です。

$q\leq 400$ を達成するために、$2$ つのパスを管理するパートをもう少しいい感じにします。

$2$ 回の質問が要求されるのは、終点同士が繋がっているかわからないときに、1回目の質問で繋がっていないと返ってきたときだけです（繋がっていないとわかっていれば、追加する頂点が一方に繋がっていなければ他方につなげることができます）。頂点を追加する順番と、先に質問するパスをランダムに決めればクエリ数を十分に抑えられます。