CF2022D1 Asesino (Easy Version)

这是该问题的简单版本。在本版本中，你最多可以询问 $n+69$ 个问题。只有在你同时解决了两个版本的问题后，才能进行 Hack。 这是一个交互题。 在墨西哥国家 IOI 集训中，有一个传统游戏叫做“Asesino”，它类似于“Among Us”或“Mafia”。 今天，有 $n$ 名玩家（编号从 $1$ 到 $n$）将参与“Asesino”游戏，游戏中有以下三种角色： - 骑士（Knight）：骑士总是说真话。 - 恶棍（Knave）：恶棍总是说谎话。 - 冒名顶替者（Impostor）：冒名顶替者被所有人认为是骑士，但实际上是恶棍。 每个玩家都会被分配一个角色。游戏中恰好有一名冒名顶替者，但骑士和恶棍的人数可以为任意（可能为零）。 作为游戏主持人，你不小心忘记了所有人的角色，但你需要找出谁是冒名顶替者。 为了确定冒名顶替者，你可以提出一些问题。每次提问，你可以选择两名玩家 $i$ 和 $j$（$1 \leq i, j \leq n$，$i \neq j$），询问玩家 $i$ 是否认为玩家 $j$ 是骑士。问题的结果如下表所示： | | 骑士 | 恶棍 | 冒名顶替者 | |------|------|------|------------| | 骑士 | 是 | 否 | 是 | | 恶棍 | 否 | 是 | 否 | | 冒名顶替者 | 否 | 是 | — | 表中第 $a$ 行第 $b$ 列的单元格表示当 $i$ 的角色为 $a$，$j$ 的角色为 $b$ 时的回答。例如，第一行第三列的“是”表示当 $i$ 是骑士，$j$ 是冒名顶替者时的回答。 你需要在最多 $n+69$ 次提问内找出冒名顶替者。 注意：评测器是自适应的：玩家的角色在一开始并未固定，可能会根据你的提问动态变化。但保证始终存在一种角色分配方案，使得所有已提问题的答案都满足本题的约束条件。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 10^5$），表示参与游戏的人数。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

每次提问时，输出一行，格式如下： - "? i j"（$1 \leq i, j \leq n$，$i \neq j$）——询问玩家 $i$ 是否认为玩家 $j$ 是骑士。 评测器会输出 "1" 表示玩家 $i$ 认为玩家 $j$ 是骑士，输出 "0" 表示不是。 当你确定了冒名顶替者是谁后，输出一行，格式如下： - "! i"（$1 \leq i \leq n$）——表示第 $i$ 位玩家是冒名顶替者。 注意，输出答案不计入 $n+69$ 次提问的限制。 如果你的输出无效、提问次数超过 $n+69$ 或错误地确定了冒名顶替者，评测器会返回 "-1"，你的程序必须立即终止。否则，你的解答可能会因为读取已关闭的流而得到任意判定。 每次输出后请不要忘记换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而判错。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Python：sys.stdout.flush() - Rust：std::io::stdout().flush() - 其它语言请查阅相关文档。 Hack 格式 对于 Hack，请使用如下格式。 第一行包含一个整数 $t$，表示测试用例数量。 每个测试用例的第一行包含整数 $n$，后跟字符串 "manual"。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \le a_i \le 1$），表示每个玩家的角色。$1$ 表示骑士，$0$ 表示恶棍，$-1$ 表示冒名顶替者。必须恰好有一个 $a_i=-1$。 例如，Hack 格式的输入如下： ``` 2 7 manual 0 1 0 -1 0 1 0 4 manual 0 1 -1 0 ```

注意，示例测试用例并不代表最优的提问策略，仅用于演示交互格式。具体来说，我们无法通过示例中的提问确定冒名顶替者。 在第一个测试用例中，第 $2$ 和 $6$ 号玩家是骑士，第 $1$、$3$、$5$、$7$ 号玩家是恶棍，第 $4$ 号玩家是冒名顶替者。以下是每次提问的解释： - 第一次提问，$i$ 是恶棍，$j$ 是恶棍。答案为“是”，因为恶棍总是说谎。 - 第二次提问，$i$ 是恶棍，$j$ 是骑士。答案为“否”，因为恶棍总是说谎。 - 第三次提问，$i$ 是骑士，$j$ 是恶棍。答案为“否”，因为骑士总是说真话。 - 第四次提问，$i$ 是骑士，$j$ 是骑士。答案为“是”，因为骑士总是说真话。 - 第五次提问，$i$ 是冒名顶替者，$j$ 是恶棍。答案为“是”，因为冒名顶替者总是说谎。 - 第六次提问，$i$ 是冒名顶替者，$j$ 是骑士。答案为“否”，因为冒名顶替者总是说谎。 - 第七次提问，$i$ 是恶棍，$j$ 是冒名顶替者。答案为“否”，因为恶棍总是说谎，并且恶棍认为冒名顶替者是骑士。 - 第八次提问，$i$ 是骑士，$j$ 是冒名顶替者。答案为“是”，因为骑士总是说真话，并且骑士认为冒名顶替者是骑士。 由 ChatGPT 4.1 翻译