CFCF2181C.Cacti Classification

Ivan 和 Petr 喜欢玩仙人掌（一种特殊的图，每条边至多属于一个简单环，并且图是连通的）。允许多重边和自环。

他们发明了如下游戏：

• Petr 秘密构造一个有 $n$ 个顶点和 $m$ 条边的仙人掌。边按照 $1$ 到 $m$ 编号。
• Petr 只告诉 Ivan 边的数量 $m$。
• 然后，Ivan 可以反复提如下类型的问题：
  • 他选择一个边的编号子集 $S$（关于子集的限制见下文），并提问：“如果我们只保留编号在 $S$ 中的边（以及所有 $n$ 个顶点），结果图是连通的吗？”
  • Petr 必须回答“是”或“否”。

Ivan 最多只能提 $8m$ 个问题，便必须判定每一条边：

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$ 是之前某次询问的编号或 $0$（询问按发起顺序从 $1$ 开始编号），
  • $q$ 是当前询问之前已发起的询问次数，
  • $e$ 是某条边的编号。

该询问表示：在第 $p$ 次询问所使用的边集基础上（若 $p=0$ 则使用全体边集），移除边 $e$ 后得到的图。交互器会在保留所有点的前提下，检查该图是否连通，并返回一个整数：

• 若询问所表示的图是连通的，则返回 $1$；
• 若询问所表示的图是不连通的，则返回 $0$；
• 若你已超出最多 $8m$ 次询问的限制，或边 $e$ 已在第 $p$ 次询问使用的边集中被移除，则返回 $-1$。此时你应终止程序，得到「Wrong Answer」的评测结果。

---

2. 输出答案

当你找到答案后，请按以下格式输出一行：

• "! $e_1$ $e_2$ $\dots$ $e_m$"（$-1 \le e_i \le 14$），

其中：

• 若 $e_i > 0$，第 $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)$。

由 ChatGPT 5 翻译