\(m = 1, \dots, N - 1\) の順に以下のことを考えます。

頂点番号 \(1\) 以上 \(m\) 以下の頂点同士を結ぶ辺がすべてわかっている状態で、頂点番号 \(1\) 以上 \(m\) 以下の頂点と頂点 \(m + 1\) を結ぶ辺をすべて求める。

まず、頂点番号 \(1\) 以上 \(m\) 以下の頂点集合を \(2\) つの集合 \(S_{1}, S_{2}\) に分けます。このとき、\(S_{1}\) に含まれる頂点同士の間に辺が存在しないようにします。\(S_{2}\) についても同様です。

頂点集合 \(S_{i}\) に含まれる頂点であって、頂点 \(m + 1\) と辺で繋がっている頂点が存在することは、\(\mathrm{ask}(S_{i}\cup \{m + 1\})\) が \(2\) 以上であることと同値です。

よって、二分探索することで\(S_{i}\) の中にある頂点 \(m + 1\) と辺で繋がっている頂点を \(1\) つ見つけることができます。

この解法は高々 \(N(\log_{2}(N) + 3) = 2816\) 回のクエリで答えが求められます。

辺が存在しない集合を探索する回数が \(2N\) 回。 辺が存在する集合を探索する回数が \(N - 1\) 回。そのときにする質問回数が \((\log_{2}(N) + 1)\) 回です。

実装例