注意到对于已知的一张图 $G=(V,E)$ 可以通过整体二分插入一个独立集 $S$，即问出 $u\in S,v\in V$ 的所有边 $(u,v)$。

对于全集 $U=\{1,2,\cdots,n\}$ 随机排列然后将它询问得到一个独立集 $S$，先问出 $U-S$ 构成的子图再插入 $S$ 即可。

这个过程期望迭代 $k$ 轮，询问次数是 $O(m\log n+nk)$，因为需要得知每个点对 $S$ 的初始连边数。

稀疏图中 $k$ 是 $O(1)$ 的，可以通过。本地 $n=4000,m=10000$ 的随机数据有 $k=6\sim 7$，总代价 $136700$ 左右。