这是一个交互问题。
小多米在狂欢节上遇到了一个尴尬的问题:他必须猜测 $$$n$$$ 节点的未加权树的边缘!树的节点编号从$$$1$$$ 到$$$n$$$。
游戏大师只允许他问一类问题:
- Little Dormi 选择一个节点 $$$r$$$ ($$$1 \le r \le n$$$),游戏主机将回复一个数组 $$$d_1, d_2, \ldots, d_n$$$,其中 $$$d_i$$$ 是从节点 $$$r$$$ 到 $$$i$$$ 的最短路径的长度,对于所有节点$$$1 \le i \le n$$$。
另外,为了让游戏对小多米发起不公平的挑战,游戏管理员最多允许 $$$\lceil\frac{n}{2}\rceil$$$ 问题,其中 $$$\lceil x \rceil$$$ 表示大于或等于 $$$x$$$ 的最小整数。
面对无法猜出树的令人反胃的可能性,小多米需要你的帮助来制定获胜策略!
请注意,游戏主持人在游戏开始前创建树,并且在游戏过程中不会更改它。
输入
输入的第一行包含整数 $$$n$$$ ($$$2 \le n \le 2\,000$$$),即树中的节点数。
然后您将开始交互。
互动
接受输入后,您最多可以进行 $$$\lceil\frac{n}{2}\rceil$$$ 查询。每个查询均以“? r”格式进行,其中 $$$r$$$ 是整数 $$$1 \le r \le n$$$ 表示您要为该查询选择的节点。
然后,您将收到 $$$n$$$ 空格分隔的整数 $$$d_1, d_2, \ldots, d_n$$$,其中 $$$d_i$$$ 是从节点 $$$r$$$ 到 $$$i$$$ 的最短路径的长度,后跟换行符。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
如果您在任何时候进行无效查询或尝试进行超过 $$$\lceil \frac{n}{2} \rceil$$$ 查询,则交互将立即终止,并且您将收到错误答案判决。
黑客
要破解解决方案,请使用以下格式。
第一行包含整数 $$$n$$$ ($$$2 \le n \le 2\,000$$$)。
接下来的 $$$n−1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$) 表示 $$$u$$$ 和 $$$v$$$ ($$$u \neq v$$$) 之间的边。这些 $$$n-1$$$ 边必须形成一棵树。
输出
当你的程序找到树时,首先输出一行由单个“!”组成的行。后面是 $$$n-1$$$ 行,每行都有两个空格分隔的整数 $$$a$$$ 和 $$$b$$$,表示连接节点 $$$a$$$ 和 $$$b$$$ 的边 ($$$1 \le a, b \le n$$$)。完成后,刷新输出流后立即正常终止程序。
您可以按任意顺序输出边,并且边 $$$(a,b)$$$ 被视为与边 $$$(b,a)$$$ 相同。回答不被视为询问。
示例
输入 #1
4 0 1 2 2 1 0 1 1
输出 #1
? 1 ? 2 ! 4 2 1 2 2 3
输入 #2
5 2 2 1 1 0
输出 #2
? 5 ! 4 5 3 5 2 4 1 3
注意
这是第一个示例中的树。
请注意,边缘可以按任何顺序输出。
此外,以下是查询示例 $$$1$$$ 中每个节点的答案:
- $$$1$$$: $$$[0,1,2,2]$$$
- $$$2$$$: $$$[1,0,1,1]$$$
- $$$3$$$: $$$[2,1,0,2]$$$
- $$$4$$$: $$$[2,1,2,0]$$$
下面是第二个交互示例中的树。
最后,以下是查询示例 $$$2$$$ 中每个节点的答案:
- $$$1$$$: $$$[0,4,1,3,2]$$$
- $$$2$$$: $$$[4,0,3,1,2]$$$
- $$$3$$$: $$$[1,3,0,2,1]$$$
- $$$4$$$: $$$[3,1,2,0,1]$$$
- $$$5$$$: $$$[2,2,1,1,0]$$$