简要题意
交互器隐藏一个由 $0,1,\ldots,n-1$ 组成的排列 $p$，相邻元素之间连边，形成一条路径。你需要通过询问还原这个排列。
令 $k=\lceil\log_2 n\rceil$。每次询问选择 $0\le m<2^k$ 和 $v\in{-1,0,\dots,n-1}$：
- 将所有满足 $\operatorname{popcount}(x\mathbin{\&}m)$ 为奇数的顶点 $x$ 放入集合 $S$。
- 若 $v\ne-1$，就翻转 $v$ 是否属于 $S$。
- 交互器返回：路径上恰有一个端点属于 $S$ 的边数，对 $3$ 取模的结果。
你最多可以询问 $nk$ 次，需要输出完整排列。题目保证 $n\ge2$ 时 $p_1
$n\le 10^3,\sum n \le 10^4$。
题解
为了便于操作和分析，我们估计我们选择询问的不同 $m$ 个数不会很多；结合题目给的 $nk$ 要求，那么我们猜测我们应该会选取 $k$ 个线性无关的 $m$ 来询问。
把编号看成二进制向量空间 $\mathbb F_2^k$ 中的向量里：（即向量的每一位都是 $0/1$，且每一位的运算都是在 $\bmod 2$ 意义下运算的）（可以参考 浅谈线性基在 OI 中的应用 - BYR_KKK - 博客园）
- 加法对应异或运算；数乘系数因为在 $\bmod 2$ 下只有 $0/1$；线性组合就是选出若干个向量异或起来；内积就是对应坐标相乘后求和，再对 $2$ 取模。
可以看到运算 $\operatorname{popcount}(x\mathbin{\&}m)\bmod 2$ 实际上就是二进制向量空间的内积。下面尝试从线性代数的角度，分析询问选取的 $m$ 不满秩时会出现什么问题
为了说明一组固定的不满秩掩码不能保证处理所有情况，我们考虑 $n=2^k\ge 4$ 下的情况（对于 $n$ 非二的次幂的情况不一定成立）。如果我们选取了一些数 $M=\{m_1,m_2...m_p\}$ 且其秩为 $r
- 定义顶点的签名：$\sigma(x)=\bigl(\langle x,m_1\rangle,\ldots,\langle x,m_p\rangle\bigr).$ 这是一个秩为 $r$ 的线性映射，因此共有 $2^r$ 种签名，每种签名对应 $2^{k-r}$ 个顶点。同签名顶点在所有 $B(m_i)$ 中的归属都相同。
- 我们可以选出四个不同的顶点 $a,b,c,d$，满足 $\sigma(a)=\sigma(b)$、$\sigma(c)=\sigma(d)$：当 $r\ge1$ 时，从两个签名类中各取两个；当 $r=0$ 时，从唯一的签名类中取四个。不妨设 $a < b$，令 $R$ 为其余顶点的任意排列，构造 $P=(a,c,R,d,b),Q=(a,d,\operatorname{rev}(R),c,b)$。
对于任何元素 $m_i$：
- 由于 $a,b$ 同签名、$c,d$ 同签名，$P$ 和 $Q$ 的 $c(B(m_i))$ 相同。
- 对于 $a,b,c,d$ 这四个顶点，虽然他们在 $P,Q$ 内的邻居不同；但他们的邻居在 $B(m_i)$ 的存在性却相同，同时，对于其他顶点，他们在 $P,Q$ 内的邻居相同。
- 因此，我们无论翻转哪个顶点，对 $P,Q$ 两条路径的询问的变化量都相同。即对于任意一个询问，在 $P,Q$ 中得到的答案都相同，因此我们无法区分这两条路径。
因此，为了方便，一个简单的取法就是： $m_j=2^j$，其中 $0\le j \lt k$。
为了方便，对于第 $j \in [ 0 , k ) $ 位来说，我们记
- $b_j$：询问 $m=2^{j},v=-1$ 的回答。
- $q_j(x)$：询问 $m=2^{j},v=x$ 的回答
暂时假设已经获得全部 $b_j$ 和 $q_j(v)$。直接取得这些信息需要 $(n+1)k$ 次询问，后面再调整询问顺序，省去不必要的部分。
part2
注意到关于 $b_j$ 和 $q_j(v)$ 的两次询问中，询问集合 $S$ 只翻转了 $v$ 这个点。那么不妨考虑 $b_j$ 和 $q_j(v)$ 的变化量。 设 $u$ 是 $v$ 的邻居，那么对边 $\{v,u\}$：
- 两端这一位相同：原来不是割边，翻转后成为割边，贡献增加 $1$；
- 两端这一位不同：原来是割边，翻转后不再是割边，贡献减少 $1$。
不妨设：$f_j(x)= \begin{cases} 1,&x\text{ 的第 }j\text{ 位为 }0,\\ -1,&x\text{ 的第 }j\text{ 位为 }1. \end{cases}$。一条关联边的贡献变化恰好是 $f_j(v)f_j(u)$，所以 $$ q_j(v)-b_j \equiv f_j(v)\sum_{u\in 是 v 的邻居}f_j(u) \pmod3. $$
我们真正想要的只有 $\sum_{u\in 是 v 的邻居}f_j(u)$，因此我们不妨设 $s_j(v)=f_j(v)\bigl(q_j(v)-b_j\bigr)\bmod3 =\left(\sum_{u 是 v 的邻居}f_j(u)\right)\bmod3.$。
注意到这是一条路径，所以 $v$ 度数最多为 $2$，如果我能确定 $v$ 是一个端点的话，就能利用 $s_j(v)$ 来推出他的唯一邻居：$u_j= \begin{cases} 0,&s_j(v)=1,\\ 1,&s_j(v)=2. \end{cases}$
而对于内部顶点 $v$，设它有两个邻居 $a,b$。某一位的信息如下：
| $a$ 的这一位 | $b$ 的这一位 | $s_j(v)$ |
|---|---|---|
| 0 | 0 | $2$ |
| 0 | 1 | $0$ |
| 1 | 0 | $0$ |
| 1 | 1 | $1$ |
另外，在内部点 $v$ 已知前驱 $pre$ 时，可以减去它的贡献：$f_j(next)\equiv s_j(v)-f_j(pre)\pmod3$，从而逐位推出后继 $next$。所以，只要确定起点，就能沿路径恢复整个排列。
同时我们注意到我们并没有使用上述的推导中最后一个确定的点的询问信息，因此我们可以考虑通过节省了 $k$ 次操作来达到了 $nk$ 的操作限制。
那么接下来的问题变成了我们怎么找到一个端点。
part 3
一个比较简洁的 $O(nk)$ 的实现方法：
如果 $v$ 是内部点，因为两个邻居 $a,b$ 不同，所以至少有一位满足 $a_j\ne b_j$，参照表格可以得到 $s_j(v)=0$。因此，当 $n\ge2$ 时，$v\text{ 是端点}\iff \forall j,\ s_j(v)\ne0.$
这样我们就得到了端点的判别方法，那么我们可以从 $0$ 到 $n-1$ 逐渐询问找到第一个端点。由于按编号递增检查，$a$ 一定是编号较小的端点，另一个端点 $b>a$ 此时尚未被查询。从 $a$ 开始沿路径递推：当前点的信息如果已有缓存，就直接使用，否则补充询问；利用已知前驱推出下一点。这样，每个顶点最多被查询一次，而 $b$ 始终未被查询，总次数恰好为 $nk$。
很多不大需要思考的 $O(n^2k)$ 或者 $O(n^2)$ 的实现方法，这里挑一个最笨的讲解：
我们故意漏询问一个点 $r=n-1$，真实路径可以看成 $a\longrightarrow\cdots\longrightarrow r \longleftarrow\cdots\longleftarrow b.$ 我们枚举每个 $v\ne r$，假设它是一个端点，然后模拟从它走到 $r$。也是按照沿路径递推的方式逐渐推出后继的每一个点，不过需要：
- 每一步都检查询问信息是否吻合、编号是否合法、是否重复经过顶点。不合法就放弃这个起点。
- 一旦走到 $r$ 就停止，并保存这条链。
最后把成功的链拼起来：如果 $r$ 本身是端点，就会得到一条覆盖所有顶点的链；如果 $r$ 是内部点，就会得到两条分别从两个端点走向 $r$ 的链，将其中一条反转后拼接即可。
综上，时间复杂度最低为 $O(nk)$。