交互题。后台有一个 (n) 个点 (m) 条边的无向图。每次，你可以询问两点 (x, y) 只经过某个集合 (S) 中的点时能否互相到达。你要用不超过 (45000) 次询问问出这个图。
(n, m le 1500)，且每个点度数不超过 (7)。
分析：
抄的这篇，查重率伯分之伯。
考虑维护 (0) 所在的连通块，每次加一个和它相邻的点。假设已经知道了 (x) 和当前连通块相邻，考虑如何问出所有 (x) 和块内连的边。考虑给连通块钦定一个根 (r)，再搞出一个序，满足每个前缀都连通（dfs 和 bfs 序均可）。再进行二分，每次查 (S) 为序的一个前缀时 (r) 和 (x) 是否连通。这样就能问出和 (x) 相邻的序最小的点。把它挖掉，对每个子连通块递归地做即可。由于做每个子连通块前都要问一遍这个块和 (x) 是否相邻，所以额外要用 (7m) 次操作。
再考虑怎么找 (x)。其实不用显式地找，考虑每次随一个块外的点 (z)，把连通块到 (z) 的一条路径上的点依次加进去。通过类似的问一个前缀的二分，可以问出路径上的某点 (y)。之后先做连通块到 (y) 的路径，再继续做 (z) 即可。为了避免 (z) 找到 (y)，(y) 又找回 (z) 的情况，做 (y) 时要先把 (z) 删掉。详见代码。