CF2181C 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 翻译