CF2066A.Object Identification

这是一道交互题。

给定一个由 $1$ 到 $n$ 的整数构成的数组 $x_1, \ldots, x_n$。评测方还拥有一个固定但隐藏的数组 $y_1, \ldots, y_n$，其元素也是 $1$ 到 $n$ 的整数。数组 $y$ 的元素对你未知。此外，已知对于所有 $i$，$x_i \neq y_i$，且所有有序对 $(x_i, y_i)$ 互不相同。

评测方秘密选择了以下两个对象之一，你需要判断具体是哪一个：

• 对象 A：一个包含 $n$ 个顶点（编号为 $1$ 到 $n$）的有向图，包含 $n$ 条形如 $x_i \to y_i$ 的边。
• 对象 B：坐标系上的 $n$ 个点，其中第 $i$ 个点的坐标为 $(x_i, y_i)$。

为了猜测评测方选择的对象，你可以进行查询。每次查询需指定两个数字 $i, j$（$1 \leq i, j \leq n, i \neq j$）。作为回应，你将得到一个数值：

• 若评测方选择对象 A，则返回顶点 $i$ 到顶点 $j$ 的最短路径长度（以边数为单位），若无路径则返回 $0$。
• 若评测方选择对象 B，则返回点 $i$ 与点 $j$ 的曼哈顿距离，即 $|x_i - x_j| + |y_i - y_j|$。

你最多可以进行 $2$ 次查询来确定评测方选择的对象。

每个测试包含多个测试用例。第一行输入测试用例数 $t$（$1 \le t \le 1000$）。随后为各测试用例的描述。

交互开始时，首先读取 $n$（$3 \leq n \leq 2 \cdot 10^5$）——每个测试用例中数组 $x$ 和 $y$ 的长度。

接下来读取 $n$ 个整数：$x_1, x_2, \ldots, x_n$（$1 \leq x_i \leq n$）——数组 $x$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

每个测试用例的数组 $y_1, y_2, \ldots, y_n$ 是固定的。即交互器不具有自适应性。

保证对于所有 $1 \leq i \leq n$，有 $x_i \neq y_i$，且所有有序对 $(x_i, y_i)$ 互不相同。

要进行查询，请输出 "? $i$ $j$"（不含引号，$1 \le i, j \le n, i \neq j$）。随后需读取查询的响应值（非负整数）。

给出答案时，若隐藏对象为 A 则输出 "! A"，若为 B 则输出 "! B"（不含引号）。注意输出答案不计入 $2$ 次查询次数。

每次输出查询后，请勿忘记换行并刷新输出缓冲区$^{\text{∗}}$，否则将导致超时错误。若在任何交互步骤中读取到 $-1$，必须立即终止程序。这意味着你的程序将因无效查询或其他错误而获得错误答案判定。未能及时终止可能导致不确定的评测结果，因为程序会尝试从已关闭的流中读取数据。注意若查询合法，响应值永远不会为 $-1$。

Hacks 说明

第一行必须包含整数 $t$（$1 \le t \le 1000$）——测试用例数。

每个测试用例的第一行必须包含整数 $n$（$3 \le n \le 2 \cdot 10^5$）——隐藏数组的长度。

第二行必须包含 $n$ 个整数——$x_1, x_2, \ldots, x_n$（$1 \le x_i \le n$）。

第三行必须包含 $n$ 个整数——$y_1, y_2, \ldots, y_n$（$1 \le y_i \le n$）。

必须确保对于所有 $1 \le i \le n$，有 $x_i \neq y_i$，且所有有序对 $(x_i, y_i)$ 互不相同。

第四行必须包含一个字符 A 或 B，表示要隐藏的对象类型。

所有测试用例的 $n$ 之和不得超过 $2 \cdot 10^5$。

$^{\text{∗}}$ 刷新缓冲区方法：

• C++：使用 fflush(stdout) 或 cout.flush()；
• Python：使用 sys.stdout.flush()；
• 其他语言请参考相关文档。

第一个测试用例中，$x = [2,2,3]$，$y = [1,3,1]$，隐藏对象为 A。

第二个测试用例中，$x = [5,1,4,2,3]$，$y = [3,3,2,4,1]$，隐藏对象为 B。

翻译由 DeepSeek R1 完成