CF2133C The Nether

这是一个交互题。 Steve 最近发现了下界，他在自己的世界里建造了 $n$ 个下界传送门，每个传送门的位置都不同。 每个传送门都以有向的方式连接到若干（可能为零）其他传送门。为了避免迷路，Steve 精心设计了传送门网络，使得不存在通过一系列传送门跳跃后又回到原位置的情况；形式上，这个网络构成了一个有向无环图（DAG）。 Steve 不会告诉你哪些传送门彼此相连，但他允许你进行询问。每次询问时，你需要给 Steve 一个位置集合 $S = \{s_1, s_2, \ldots, s_k\}$ 以及一个起始位置 $x \in S$。Steve 会帮你计算从 $x$ 出发，仅经过 $S$ 中的位置的最长路径，并告诉你这条路径包含多少个位置。（如果从 $x$ 出发无法到达 $S$ 中的其他位置，Steve 会回答 $1$。） 你想获得成就“热门景点”，因此你希望找到一条经过尽可能多位置的路径。Steve 今天格外慷慨，他允许你进行 $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\ \dots\ s_k$ 测评机将返回查询的答案。 找到最大长度的路径后，按以下格式输出一行： - $\texttt{!}\ k\ v_1\ v_2\ \dots\ v_k$ 这表示从入口 $v_1$ 开始，然后跳转到 $v_2$ ，再跳转到 $v_3$ ，以此类推，最后在 $v_k$ 结束。 请注意，输出答案**不计入** $2\cdot n$ 查询次数限制。 打印完每个查询后，不要忘记输出行尾并刷新 $^{\text{∗}}$ 输出。否则，您将收到 `Idleness limit exceeded` 的提示。 如果在任何交互步骤中读取的不是有效数据，而是 $-1$ ，则必须立即退出程序。这意味着由于查询无效或其他错误，您的程序将收到 `Wrong Answer` 。未退出可能会导致任意判定，因为您的程序将继续从封闭的数据流中读取数据。 交互器是**非自适应的**。在交互过程中，传送门之间的连接不会改变。 **Hacks*** 要 hack，请使用以下格式： 每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1\le t\le 1000$）。下面是测试用例的说明。 每个测试用例的第一行包含一个整数 $n$（$2\le n\le 500$），表示位置数。 然后，输出 $n$ 行。第 $i$ 行的形式应为 $k_i\ v_1\ v_2\ \dots\ 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, \dots, v_{k_i}$ 。给定的网络必须是有向无环图。 所有测试用例中 $n^3$ 的总和不得超过 $500^3$ 。 若要刷新缓冲区，请使用： - `fflush(stdout)` 或 C++ 中的 `cout.flush()`； - 在 Python 中使用 `sys.stdout.flush()`； - 参见其他语言的文档。

在第一个测试用例中，传送门网络如下图所示：  - 从位置 $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$。 利用这些询问信息，可以确定一条最长路径为 $5 \rightarrow 1 \rightarrow 4 \rightarrow 2$。 在第二个测试用例中，传送门网络如下图所示：  两个传送门之间没有连接，因此最长路径只包含一个位置。注意 $1\ 2$ 也是一个合法答案。 由 ChatGPT 4.1 翻译