这是问题的简单版本。版本之间的区别在于,在此版本中,您最多可以提出 $$$32 \cdot (n + m)$$$ 问题,以及 $$$n \leq 15$$$ 问题。只有解决了该问题的所有版本,您才能破解。
这是一个交互问题。
评审团想到了一个没有循环和多条边的有向无环图,它有 $$$n$$$ 个顶点和 $$$m$$$ 个边。
您的任务是确定该图中有哪些边。为此,您可以提出以下形式的问题:第 $$$k$$$ 条路径在图中所有路径的字典顺序 $$$^{\text{*}}$$$ 排序列表中是什么样子。
图中的路径是一系列顶点 $$$u_{1}, u_{2}, \dots, u_{l}$$$,这样对于任何 $$$i \lt l$$$,图中都存在一条边 ($$$u_{i}, u_{i + 1}$$$)。
你的任务是通过提出不超过 $$$32 \cdot (n + m)$$$ 的问题来完成此任务。
$$$^{\text{*}}$$$当且仅当满足以下条件之一时,序列 $$$a$$$ 按字典顺序小于序列 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;或
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。测试用例的描述如下。
每个测试用例都包含一行,其中包含一个整数 $$$n$$$ ($$$1 \le n \le 15$$$) — 图中的顶点数。
评审团保证给定的图不包含循环或多重边。
请注意,$$$m$$$ 对您来说是未知的。
互动
每个测试用例的交互都从读取整数 $$$n$$$ 开始。
那么您最多可以提出 $$$32 \cdot (n + m)$$$ 问题。
要提出问题,请输出格式为“的字符串”? k"(不带引号)($$$1 \le k \le 2^{30}$$$)。在每个问题之后,读取一个整数 $$$q$$$ — 第 $$$k$$$ 条路径中的顶点数。如果 $$$q = 0$$$,则这样的路径不存在;否则,读取 $$$q$$$ 整数 — 组成该路径的顶点数路径。
可以证明,在给定的约束下,图中不同路径的数量不超过$$$2^{30}$$$。
要报告您的答案,请首先输出格式为“的字符串”!米",然后以格式 " 输出描述边缘的 $$$m$$$ 行u v”,表示从 $$$u$$$ 到 $$$v$$$ 有一条边。可以按任意顺序输出边。输出答案不算查询。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客:
对于 hack,请使用以下格式:
第一行应包含一个整数 $$$t$$$ ($$$1\leq t\leq 10$$$) — 测试用例的数量。
每种情况的第一行应包含两个整数 $$$n, m$$$ ($$$1 \leq n \leq 15$$$, $$$0 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$) - 图中顶点和边的数量。
接下来的 $$$m$$$ 行应包含边缘的描述。每条边由两个整数 $$$v$$$、$$$u$$$ ($$$1 \leq v, u \leq n$$$, $$$v \neq u$$$) 定义,表示从顶点 $$$v$$$ 到顶点 $$$u$$$ 的一条边。
图形不能包含循环或多重边。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
3 5 1 1 2 1 2 3 1 2 4 3 1 2 5 2 1 3 3 1 3 4 3 1 3 5 1 2 1 3 1 4 1 5 1 0 2 1 1 1 2 2 2 1
输出复制
? 1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 11 ? 14 ? 15 ! 6 1 3 1 2 2 4 3 4 2 5 3 5 ? 2 ! 0 ? 1 ? 2 ? 3 ! 1 2 1
注意
第一个测试用例的图表。
在此图中,有 $$$15$$$ 路径,按字典顺序排列如下:
- $$$1$$$
- $$$1 \到 2$$$
- $$$1 \到 2 \到 4$$$
- $$$1 \到 2 \到 5$$$
- $$$1 \到 3$$$
- $$$1 \到 3 \到 4$$$
- $$$1 \到 3 \到 5$$$
- $$$2$$$
- $$$2 \到 4$$$
- $$$2 \ 到 5$$$
- $$$3$$$
- $$$3 \到 4$$$
- $$$3 \到 5$$$
- $$$4$$$
- $$$5$$$