CF1158E Strange device

这是一个交互题。 Vasya 喜欢解答测验。他发现了一个奇怪的装置，想要弄清楚它的工作原理。 这个装置被一棵树（一个无环连通无向图）加密，这棵树有 $n$ 个顶点，编号为 $1$ 到 $n$。为了破解这个测验，你需要猜出这棵树的结构。 幸运的是，这个装置可以进行一种操作，你需要利用这种操作来猜出加密的树。你可以向装置输入一个长度为 $n$ 的非负整数数组 $d_1, d_2, \ldots, d_n$。装置上有 $n$ 盏灯，第 $i$ 盏灯与树上的第 $i$ 个顶点相连。对于每个 $i$，如果存在某个编号为 $j \neq i$ 的顶点，使得 $dist(i, j) \leq d_j$，那么第 $i$ 盏灯会被点亮。这里 $dist(i, j)$ 表示树上顶点 $i$ 和 $j$ 之间的距离，即它们之间简单路径上的边数。 Vasya 想通过不超过 $80$ 次操作猜出这棵树。请你帮助他！

你的程序首先应读取一个整数 $n$，表示加密树的顶点数（$2 \leq n \leq 1000$）。 之后，你可以进行多次操作，每次操作的格式如下：输出一个符号 "?"（不含引号），后跟 $n$ 个整数 $d_1, d_2, \ldots, d_n$，用空格分隔。注意，对于所有 $i$，只能使用满足 $0 \leq d_i < n$ 的数。然后，你应读取一个长度为 $n$ 的字符串 $s$，由字符 "0" 和 "1" 组成。对于每个 $i$，如果与第 $i$ 个顶点相连的灯未被点亮，则 $s_i$ 为 "0"，否则为 "1"。 在进行若干次操作后，你需要输出你猜测的树。为此，输出一个符号 "!"（不含引号），接下来 $n-1$ 行，每行输出两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条树边连接的两个顶点编号。要求 $1 \leq a_i, b_i \leq n$ 且 $a_i \neq b_i$。这些边应构成一棵与你猜测的加密树完全相同的树。输出后程序应终止。 保证每个测试中的树在测试开始前已固定，不会因你的操作而改变。 你的程序最多可以进行 $80$ 次操作。如果超过 $80$ 次操作，可能会收到任意判定，因为此时会继续从已关闭的输入中读取数据。如果操作或输出格式不正确，也可能收到任意判定。请小心。 每次输出问题或答案后不要忘记刷新输出缓冲区。 刷新输出的方法如下： - C++：fflush(stdout) - Java：System.out.flush() - Python：stdout.flush() - Pascal：flush(output) - 其它语言请查阅相关文档。 Hack 数据格式： 第一行包含一个整数 $n$，表示树的顶点数（$2 \leq n \leq 1000$）。接下来 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条树边连接的两个顶点（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$）。所有边应构成一棵树。注意，不能有多余的空格或换行。

见输入格式说明。

下图为第一个测试样例中加密装置的树结构：  下表为该树中各顶点对之间的距离：  - 若你进行操作 $d = [0, 0, 0, 0, 0]$，则没有灯会亮，因为对于所有 $i \neq j$，都有 $dist(i, j) > 0$。 - 若你进行操作 $d = [1, 1, 2, 0, 2]$，则除了与第 $3$ 个顶点相连的灯外，其余灯都会亮。例如，与第 $1$ 个顶点相连的灯会亮，因为 $dist(1, 5) = 1 \leq 2 = d_5$。 - 若你进行操作 $d = [0, 0, 0, 1, 0]$，则除了与第 $4$、$5$ 个顶点相连的灯外，其余灯都会亮。 - 若你进行操作 $d = [0, 1, 0, 0, 1]$，则只有与第 $1$、$4$ 个顶点相连的灯会亮。 由 ChatGPT 4.1 翻译