带噶好！偶系算法竞赛小编提米>~<

在 提交记录中，最大的点平均只用了不到$960000$次询问。大家可能会很惊讶，这是怎么做到的呢？下面就跟着小编一起来看看吧！

UOJ#153有一种不需要人类智慧的、更本质一点（？）的做法。我们构造一张二分图，把第一轮$1$~$n$构成的所有连通块看作左边的点，第二轮$1$~$n$构成的所有连通块看作右边的点。两点之间连边当且仅当对应的连通块有公共点。（容易发现，两个块最多有一个公共点，否则公共点之间无法区分。）

因此二分图恰有$n$条边，且边与原题的点$1$到$n$一一对应。

通过询问$n+1$到$2n$的连通块，我们同样可以构建出一张二分图。假如我们能将该图和原先二分图的顶点一一对应，则也能将它的边$n+1$到$2n$和原先的边$1$到$n$一一对应。

将点一一对应，我们只需要图不自同构。我们可以随机生成图，计算哈希，假如哈希冲突再次随机即可。最后的图中，两部分的点数均略大于100。

此时如果随机询问点对应的连通块，期望次数会略大于$10^6$（但已经比大部分提交优了>~<)。为此，我们将已有的连通块按大小排序，和最后对应排名的连通块大小的差值认为是这个连通块的剩余点数。按照剩余点数从大到小询问，就可以做到$960000$左右啦。（每次排序时间开销较大，可以隔几轮重排一次。）

以上就是在1e6次询问内解决UOJ#153的全部内容了。大家有什么想法呢？欢迎在评论区和小编讨论哦！