← 返回题目列表

Codeforces · 2181/C

C. 仙人掌分类

中文机器翻译题面 查看原题

Ivan 和 Petr 喜欢一起玩 仙人掌 — 每条边至多属于一个简单循环的特殊图,并且该图是连通的。顶点对和循环之间允许存在多条边。

他们发明了以下游戏:

  • Petr 秘密构建了一棵具有 $$$n$$$ 顶点和 $$$m$$$ 边的仙人掌。边缘标记为从 $$$1$$$ 到 $$$m$$$。
  • Petr 只告诉 Ivan 数字 $$$m$$$。
  • 然后 Ivan 可以提出以下形式的问题:
    • 他选择边标签的子集 $$$S$$$(请参阅下面有关子集的限制),并问道:“如果我们只保留标签位于 $$$S$$$ 中的边(以及所有 $$$n$$$ 顶点),则生成的图是否连通?”
    • Petr 必须回答“是”或“否”。

在提出最多 $$$8m$$$ 问题后,Ivan 必须针对每条边确定:

  1. 这条边是否位于仙人掌中的某个循环上;
  2. 如果是,那么这个简单循环的长度是多少。

在这个问题中,每个循环被认为是长度为 $$$1$$$ 的简单循环,并且同一对顶点之间的两条边形成长度为 $$$2$$$ 的简单循环。

然而,Ivan 还很年轻,只知道 $$$14$$$ 以内的数字。所以:

  • 如果一条边位于长度最多 $$$14$$$ 的简单循环上,他必须输出该精确长度;
  • 如果一条边位于长度大于$$$14$$$的简单循环上,他必须说这条边位于 大循环.

此外,为了避免每次必须列出大量边,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$$$ 中使用的边集合中删除。在这种情况下,您应该终止程序才能收到错误答案的判决。

找到答案后,按以下格式输出一行:

  • "! $$$e_1$$$ $$$e_2$$$ $$$\点$$$ $$$e_m$$$" ($$$-1 \le e_i \le 14$$$ 对于所有 $$$i$$$),
其中:
  • 如果 $$$e_i$$$ 为正,则边号 $$$i$$$ 属于长度恰好为 $$$e_i$$$ 的简单循环,
  • 如果$$$e_i = 0$$$,则边号$$$i$$$属于大循环(长度大于$$$14$$$的简单循环),
  • 如果$$$e_i = -1$$$,则边号$$$i$$$不属于任何循环。

交互器返回一个整数:

  • $$$1$$$ 如果您的答案正确。继续下一个测试用例,如果这是最后一个用例,则终止程序。
  • $$$-1$$$ 如果您的答案不正确。在这种情况下,您应该终止程序才能收到错误答案的判决。

交互器是 不 自适应,这意味着在您提出任何查询之前图表是固定的。

示例

输入
复制

1
7

0

1

1

1

输出
复制


? 0 1

? 0 3

? 2 4

! -1 3 1 3 2 3 2

注意

在示例交互中,输入和输出包含空行,以使交互者响应与查询保持一致。这些空行不会出现在实际的输入和输出中。

在此示例中,图有 $$$5$$$ 个顶点和 $$$7$$$ 个边;边 $$$1$$$ 到 $$$7$$$ 按此顺序为 $$$(1, 2)$$$、$$$(2, 3)$$$、$$$(3, 3)$$$、$$$(3, 4)$$$、$$$(4, 5)$$$、$$$(2, 4)$$$、$$$(4, 5)$$$。