CF1919H Tree Diameter

有一棵隐藏的树，包含 $n$ 个顶点。树的 $n-1$ 条边编号为 $1$ 到 $n-1$。你可以进行以下两种类型的询问： 1. 给裁判一个长度为 $n-1$ 的正整数数组 $a$。对于每条边 $i$（$1 \leq i \leq n-1$），将其权值设为 $a_i$。然后，裁判会返回该树的直径长度 $^\dagger$。 2. 给裁判两个下标 $1 \leq a, b \leq n-1$。裁判会返回边 $a$ 和边 $b$ 之间的边数。也就是说，若边 $a$ 连接 $u_a$ 和 $v_a$，边 $b$ 连接 $u_b$ 和 $v_b$，则裁判会返回 $\min(\text{dist}(u_a, u_b), \text{dist}(v_a, u_b), \text{dist}(u_a, v_b), \text{dist}(v_a, v_b))$，其中 $\text{dist}(u, v)$ 表示顶点 $u$ 和 $v$ 之间路径上的边数。 请在最多 $n$ 次类型 1 询问和 $n$ 次类型 2 询问（顺序任意）后，找出一棵与隐藏树同构 $^\ddagger$ 的树。 $^\dagger$ 两个顶点之间的距离是连接它们的唯一简单路径上所有边权之和。直径是所有这些距离中的最大值。 $^\ddagger$ 两棵各有 $n$ 个顶点的树，如果存在一个 $1$ 到 $n$ 的排列 $p$，使得第一棵树中的边 $(u, v)$ 当且仅当第二棵树中存在边 $(p_u, p_v)$，则称它们同构。

输入的第一行包含一个整数 $n$（$3 \leq n \leq 1000$），表示树的顶点数。

交互开始时，先读取 $n$。 你可以按以下方式进行询问： 1. 输出 "$\mathtt{?}\,1\,a_1\,a_2\,\ldots\,a_{n-1}$"（$1 \leq a_i \leq 10^9$）。然后，你应读取一个整数 $k$，表示直径的长度。此类询问最多只能进行 $n$ 次。 2. 输出 "$\mathtt{?}\,2\,a\,b$"（$1 \leq a, b \leq n-1$）。然后，你应读取一个整数 $k$，表示边 $a$ 和边 $b$ 之间的边数。此类询问最多只能进行 $n$ 次。 如果你的询问不合法，程序会立即终止，并返回 Wrong answer。 输出最终答案时，先输出一行 "!"，接下来输出 $n-1$ 行，每行 "$u_i\,v_i$"（$1 \leq u_i, v_i \leq n$），表示对于每个 $i$（$1 \leq i \leq n-1$），存在一条连接 $u_i$ 和 $v_i$ 的边。 每次输出询问后，别忘了输出换行并刷新输出缓冲区，否则会因超时被判为 Idleness limit exceeded。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hacks 第一行包含一个整数 $n$（$3 \leq n \leq 1000$），表示树的顶点数。 接下来 $n-1$ 行，每行两个整数 $u_i, v_i$（$1 \leq u_i, v_i \leq n$），表示树的边。

 上图展示了样例中的隐藏树。顶点上的数字表示顶点编号，边上的数字表示边的编号。  在第一次询问中，所有边权都设为 $1$，因此直径长度为 $3$，如图所示。 在第二次询问中，边 $1$ 和边 $3$ 之间有 $1$ 条边。  在第三次询问中，取边 $1$、$2$ 和 $3$，直径为 $9$。 在第四次询问中，边 $4$ 和边 $2$ 之间没有边。  上图展示了样例中的输出答案。由于它与隐藏树同构，因此被判为正确答案。注意，输出的边顺序可以任意。 由 ChatGPT 4.1 翻译