P14784 [NERC 2025] Cacti Classification

Ivan 和 Petr 喜欢玩 **仙人掌图** —— 这是一种特殊的图，其中每条边最多属于一个简单环，且图是连通的。允许一对顶点之间存在多条边，也允许自环。 他们发明了以下游戏： - Petr 秘密地构建一个有 $n$ 个顶点和 $m$ 条边的仙人掌图。这些边被标记为 $1$ 到 $m$。 - Petr 只告诉 Ivan 数字 $m$。 - 然后 Ivan 被允许提出以下形式的问题： - 他选择一个边标签的子集 $S$（关于子集的限制见下文），并问：“如果我们只保留标签在 $S$ 中的边（以及所有 $n$ 个顶点），得到的图是否连通？” - Petr 必须回答 “yes” 或 “no”。 在最多提出 $8m$ 个问题后，Ivan 必须确定每条边： 1. 这条边是否位于仙人掌图的某个环上； 2. 如果是，该简单环的长度是多少。 在这个问题中，每个自环被视为长度为 $1$ 的简单环，而同一对顶点之间的两条边构成一个长度为 $2$ 的简单环。 然而，Ivan 还很年轻，只认识不超过 $14$ 的数字。因此： - 如果一条边位于长度不超过 $14$ 的简单环上，他必须输出该确切长度； - 如果一条边位于长度大于 $14$ 的简单环上，他必须说这条边位于一个 **大环** 上。 此外，为了避免每次列出很多条边，Ivan 总是询问从之前某个查询使用的边集，或从所有边的集合中，恰好移除一条边所得到的边集。 你能设计一个策略让 Ivan 完成这个任务吗？

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。接下来是测试用例的描述。 每个测试用例的第一行包含 $m$ ($1 \le m \le 10^4$) —— 仙人掌图中边的数量。 保证所有测试用例的 $m$ 之和不超过 $10^4$。 ### 交互协议 要提出一个查询，请按以下格式输出一行（不含引号）： - `? p e` ($0 \le p \le q$；$1 \le e \le m$)，其中 $p$ 是之前某个查询的编号，或为零（查询按提出顺序从 $1$ 开始编号），$q$ 是当前查询之前已提出的查询数量，$e$ 是一条边的标签。 该查询表示一个图，由查询编号 $p$ 中使用的边（如果 $p = 0$ 则表示所有边）去除边 $e$ 后组成。交互器检查该图在考虑 **所有原始顶点** 时是否连通，并返回一个整数： - $1$ 如果查询所表示的图是连通的； - $0$ 如果查询所表示的图不是连通的； - $-1$ 如果你超出了 $8m$ 个允许的查询，或者边 $e$ 已经从查询 $p$ 使用的边集中被移除了。在这种情况下，你应该终止程序以收到 Wrong Answer 的判定。 当你找到答案时，按以下格式输出一行： - `! e_1 e_2 … e_m`（对所有 $i$，$-1 \le e_i \le 14$）， 其中： - 如果 $e_i$ 为正数，则编号为 $i$ 的边属于一个长度恰好为 $e_i$ 的简单环； - 如果 $e_i = 0$，则编号为 $i$ 的边属于一个 **大环**（长度大于 $14$ 的简单环）； - 如果 $e_i = -1$，则编号为 $i$ 的边不属于任何环。 交互器返回一个整数： - $1$ 如果你的答案正确。继续下一个测试用例，或者如果是最后一个用例则终止程序。 - $-1$ 如果你的答案不正确。在这种情况下，你应该终止程序以收到 Wrong Answer 的判定。 交互器是 **非自适应的**，这意味着图在你提出任何查询之前就已经固定了。

无

在示例交互中，输入和输出包含空行以使交互器的响应与查询对齐。这些空行在实际的输入和输出中不会出现。 在这个例子中，图有 $5$ 个顶点和 $7$ 条边；边 $1$ 到 $7$，按顺序依次是 $(1,2)$、$(2,3)$、$(3,3)$、$(3,4)$、$(4,5)$、$(2,4)$、$(4,5)$。 :::align{center}  :::