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：stdiostdout().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 翻译