← 返回题目列表

Codeforces · 2001/C

C. 猜猜树

中文机器翻译题面 查看原题

这是一个交互问题。

Misuki 选择了一棵包含 $$$n$$$ 节点的秘密树,索引从 $$$1$$$ 到 $$$n$$$,并要求你使用以下类型的查询来猜测它:

- "? a b" — Misuki 会告诉您哪个节点 $$$x$$$ 最小化 $$$|d(a,x) - d(b,x)|$$$,其中 $$$d(x,y)$$$ 是节点 $$$x$$$ 和 $$$y$$$ 之间的距离。如果存在多个这样的节点,Misuki 会告诉您最小化 $$$d(a,x)$$$ 的节点。

最多使用$$$15n$$$查询找出Misuki秘密树的结构!

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。

每个测试用例都包含一行,其中包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$),即树中的节点数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

互动

交互从读取整数 $$$n$$$ 开始。

然后您最多可以进行 $$$15n$$$ 查询。

要进行查询,请以“? a b”格式输出一行(不带引号)($$$1 \le a,b \le n$$$)。每次查询后,读取一个整数——查询的答案。

要报告答案,请以“! $$$a_1$$$ $$$b_1$$$ $$$a_2$$$ $$$b_2$$$ ... $$$a_{n-1}$$$ $$$b_{n-1}$$$ 格式输出一行(不带引号),这意味着节点 $$$a_i$$$ 和$$$b_i$$$,对于每个 $$$1 \le i \le n-1$$$。您可以按任何顺序打印边缘。

进行 $$$15n$$$ 查询后,对任何其他查询的响应将为 $$$-1$$$。一旦收到此类响应,请终止程序以接收错误答案判决。

打印每一行后,不要忘记输出行尾并刷新输出缓冲区。否则,您将收到超出空闲限制的判决。要冲洗,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

对于 hacks,请使用以下格式:第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。

每个测试的第一行包含一个整数 $$$n$$$ — 隐藏树中的节点数。

然后是 $$$n-1$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$),这意味着隐藏树中 $$$a_i$$$ 和 $$$b_i$$$ 之间有一条边。

所有测试用例的 $$$n$$$ 总和不得超过 $$$1000$$$。

示例

输入 #1

1
4
1
1
3

输出 #1

? 1 2

? 1 3

? 1 4

! 1 2 1 3 3 4

注意

树是无向非循环连通图。具有 $$$n$$$ 节点的树将始终具有 $$$n-1$$$ 边。

在示例中,“? 1 2”的答案是 $$$1$$$。这意味着节点 $$$1$$$ 和 $$$2$$$ 之间存在一条边。

“?1 3”的答案是$$$1$$$。这意味着节点 $$$1$$$ 和 $$$3$$$ 之间存在一条边。

“?1 4”的答案是$$$3$$$。可以证明,只有当节点$$$3$$$同时连接到节点$$$1$$$和$$$4$$$时,才会发生这种情况。

因此,树的边是 $$$(1,2)$$$、$$$(1,3)$$$ 和 $$$(3,4)$$$。