这是一个交互问题。
清理水边区域后,格蕾特发现了一个名为 Genokraken 的怪物,她将其收容起来以进行科学研究。
怪物的神经系统可以被构造为一棵由$$$n$$$节点组成的树$$$^{\dagger}$$$(实际上,一切都应该不再像树$$$\ldots$$$),编号从$$$0$$$到$$$n-1$$$,以节点$$$0$$$为根。
Gretel 的目标是了解怪物神经系统的确切结构 - 更具体地说,她想知道树的值 $$$p_1, p_2, \ldots, p_{n-1}$$$,其中 $$$p_i$$$ ($$$0 \le p_i < i$$$) 是节点 $$$i$$$ ($$$1 \le我\le n - 1$$$)。
她不知道节点到底是如何放置的,但她知道一些方便的事实:
- 如果我们删除根节点$$$0$$$和所有相邻的边,这棵树将变成仅由路径$$$^{\ddagger}$$$组成的森林。最初与节点 $$$0$$$ 相邻的每个节点将是某个路径的终点。
- 节点的索引方式为:如果 $$$1 \le x \le y \le n - 1$$$,则 $$$p_x \le p_y$$$。
- 节点 $$$1$$$ 恰好有两个相邻节点(包括节点 $$$0$$$)。
这张图中的树不满足条件,因为如果我们删除节点$$$0$$$,那么节点$$$2$$$(最初与节点$$$0$$$相邻)将不会是路径$$$4-2-5$$$的终点。这张图中的树不满足条件,因为$$$p_3 \le p_4$$$必须成立。这张图中的树不满足条件,因为节点 $$$1$$$ 只有一个相邻节点。
Gretel 可以对收容间进行查询:
- "? a b" ($$$1 \le a, b < n$$$, $$$a \ne b$$$) — 单元格将检查节点 $$$a$$$ 和 $$$b$$$ 之间的简单路径是否包含节点 $$$0$$$。
然而,为了避免过度刺激生物而产生意外后果,Gretel 希望最多查询 $$$2n - 6$$$ 次。尽管格蕾特很有天赋,但她无法同时完成所有事情,所以你能为她提供帮助吗?
$$$^{\dagger}$$$树是一个连通图,其中每对不同的节点都有一个简单的路径连接它们。
$$$^{\ddagger}$$$路径是一棵树,其顶点可以按 $$$v_1, v_2, \ldots, v_k$$$ 的顺序列出,使得边为 $$$(v_i, v_{i+1})$$$ ($$$1 \le i < k$$$)。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 10^4$$$) — Genokraken 神经系统中的节点数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。
互动
对于每个测试用例,交互都是通过读取整数 $$$n$$$ 开始的。
然后您可以进行以下类型的查询:
- "? a b" (不带引号) ($$$1 \le a, b < n$$$, $$$a \ne b$$$)。
查询后,读取一个整数 $$$r$$$ — 您的查询的答案。您最多可以使用 $$$2n - 6$$$ 此类查询。
- 如果节点 $$$a$$$ 和 $$$b$$$ 之间的简单路径不包含节点 $$$0$$$,则将得到 $$$r = 0$$$。
- 如果节点 $$$a$$$ 和 $$$b$$$ 之间的简单路径包含节点 $$$0$$$,则将得到 $$$r = 1$$$。
- 如果您进行超过 $$$2n-6$$$ 查询或进行无效查询,您将得到 $$$r = -1$$$。您需要在此之后终止才能获得“错误答案”的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
查出结构后,输出一行,格式为“! $$$p_1 \space p_2 \ldots p_{n-1}$$$”(不带引号),其中$$$p_i$$$ ($$$0 \le p_i < i$$$)表示节点$$$i$$$的直接父节点的索引。此查询不计入 $$$2n - 6$$$ 查询限制。
解决一个测试用例后,程序应立即转到下一个测试用例。解决所有测试用例后,程序应立即终止。
打印任何查询后,不要忘记输出行尾并刷新输出缓冲区。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
交互器是非自适应的。交互过程中树不会改变。
黑客
对于 hack,请使用以下格式:
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 10^4$$$) — Genokraken 神经系统中的节点数。
每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$p_1, p_2, \ldots, p_{n-1}$$$ ($$$0 \le p_1 \le p_2 \le \ldots \le p_{n-1} \le n - 2$$$, $$$0 \le p_i < i$$$) — 的直接父级系统中的节点分别为$$$1$$$、$$$2$$$、...、$$$n-1$$$。
在每个测试用例中,值 $$$p_1, p_2, \ldots, p_{n-1}$$$ 必须确保树中满足以下条件:
- 如果我们删除根节点 $$$0$$$ 和所有相邻的边,这棵树将变成仅由路径组成的森林。最初与节点 $$$0$$$ 相邻的每个节点将是某个路径的终点。
- 节点 $$$1$$$ 恰好有两个相邻节点(包括节点 $$$0$$$)。
所有测试用例的 $$$n$$$ 总和不得超过 $$$10^4$$$。
示例
输入 #1
3 4 1 5 1 0 9
输出 #1
? 2 3 ! 0 0 1 ? 2 3 ? 2 4 ! 0 0 1 2 ! 0 0 0 1 3 5 6 7
注意
在第一个测试用例中,Genokraken 的神经系统形成以下树:
- “?2 3”的答案是$$$1$$$。这意味着节点 $$$2$$$ 和 $$$3$$$ 之间的简单路径包含节点 $$$0$$$。
在第二个测试用例中,Genokraken 的神经系统形成以下树:
- “?2 3”的答案是$$$1$$$。这意味着节点 $$$2$$$ 和 $$$3$$$ 之间的简单路径包含节点 $$$0$$$。
- “?2 4”的答案是$$$0$$$。这意味着节点 $$$2$$$ 和 $$$4$$$ 之间的简单路径不包含节点 $$$0$$$。
在第三个测试用例中,Genokraken 的神经系统形成以下树: