这是一个交互问题。
最近发现了下界,史蒂夫建立了一个由 $$$n$$$ 下界传送门组成的网络,每个传送门都位于他世界的不同位置。
每个门户都在一个方向上连接到一定数量(可能为零)的其他门户。为了避免迷路,史蒂夫精心构建了门户网络,这样就不会有通过门户的跳跃顺序将您从一个位置带回原来的位置;形式上,网络形成有向无环图。
史蒂夫拒绝告诉您哪些门户连接到哪个,但他允许您提出疑问。在每个查询中,您为 Steve 提供一组位置 $$$S = \{s_1, s_2, \ldots, s_k\}$$$ 和起始位置 $$$x \in S$$$。 Steve 将计算出从 $$$x$$$ 开始且仅经过 $$$S$$$ 中的位置的最长路径,并告诉您其中的位置数量。 (如果无法从 $$$x$$$ 到达 $$$S$$$ 中的任何其他位置,Steve 将回复 $$$1$$$。)
当您寻求获得成就“热门旅游目的地”时,您希望找到访问尽可能多的地点的路径。史蒂夫感觉特别慷慨,会给你 $$$2 \cdot n$$$ 查询来找到它。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500$$$) - 位置数。
保证所有测试用例的$$$n^3$$$总和不超过$$$500^3$$$。
互动
每个测试用例的交互都从读取整数 $$$n$$$ 开始。然后您最多可以进行 $$$2 \cdot n$$$ 查询。
要进行查询,请按以下格式输出一行:
- $$$\texttt{?}\,\,x\,\,k\,\,s_1\,s_2\,\ldots\,s_k$$$
评审团将返回质疑的答案。
当找到最大长度的路径时,按以下格式输出一行:
- $$$\texttt{!}\,\,k\,\,v_1\,v_2\,\ldots\,v_k$$$
这表示从门户 $$$v_1$$$ 开始,然后跳到 $$$v_2$$$,然后跳到 $$$v_3$$$ 等等,以 $$$v_k$$$ 结束。
注意输出答案 不算数 朝着 $$$2 \cdot n$$$ 查询的限制。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
交互器是 不自适应。交互过程中门户之间的连接不会改变。
黑客
要执行黑客攻击,请使用以下格式:
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — 位置数。
然后,输出 $$$n$$$ 行。第 $$$i$$$ 行的格式应为 $$$k_i\,v_1\,v_2\,\ldots\,v_{k_i}$$$ ($$$0 \le k_i \le n - 1$$$, $$$1 \le v_j \le n$$$, $$$v_j \ne i$$$),表示位置 $$$i$$$ 处的门户已连接朝一个方向(通向)位置 $$$v_1, v_2, \ldots, v_{k_i}$$$。给定网络必须形成有向无环图。
所有测试用例的 $$$n^3$$$ 总和不得超过 $$$500^3$$$。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 5 3 3 2 1 2 1 1
输出复制
? 1 4 1 2 3 4 ? 3 3 4 3 2 ? 5 2 1 5 ? 2 2 2 4 ! 4 5 1 4 2 ? 1 2 1 2 ? 2 2 1 2 ! 1 1
注意
在第一个测试用例中,门户网络如下:
- 从位置 $$$1$$$ 开始,仅经过 $$$\{1, 2, 3, 4\}$$$ 的最长路径是路径 $$$1 \rightarrow 4 \rightarrow 2$$$,它具有 $$$3$$$ 不同的位置。
- 从位置 $$$3$$$ 开始,仅经过 $$$\{2, 3, 4\}$$$ 的最长路径是路径 $$$3 \rightarrow 4 \rightarrow 2$$$,它具有 $$$3$$$ 不同的位置。
- 从位置 $$$5$$$ 开始,仅通过 $$$\{1, 5\}$$$ 的最长路径是路径 $$$5 \rightarrow 1$$$,它具有 $$$2$$$ 不同的位置。
- 从 $$$2$$$ 开始不可能到达 $$$\{2, 4\}$$$ 中的任何其他位置,因此 Steve 对该查询回答 $$$1$$$。
在第二个测试用例中,门户网络如下:
两个门户都没有相互连接,因此最长的路径是单个位置。请注意 ! 1 2 也是一个有效的答案。