CF1977E Tensor

这是一个交互题。 你将得到一个整数 $n$。 评测机为你隐藏了一个有 $n$ 个顶点（编号为 $1$ 到 $n$）和若干条边的有向图。你还知道： - 图中只包含形如 $i \leftarrow j$ 的边，其中 $1 \le i < j \le n$。 - 对于任意三个顶点 $1 \le i < j < k \le n$，至少满足以下条件之一$^\dagger$： - 顶点 $i$ 可以从顶点 $j$ 到达，或 - 顶点 $i$ 可以从顶点 $k$ 到达，或 - 顶点 $j$ 可以从顶点 $k$ 到达。 你需要将每个顶点染成黑色或白色，使得对于任意两个同色的顶点 $i$ 和 $j$（$1 \le i < j \le n$），顶点 $i$ 可以从顶点 $j$ 到达。 为此，你可以进行如下类型的询问： - ? i j —— 顶点 $i$ 是否可以从顶点 $j$ 到达（$1 \le i < j \le n$）？ 请在最多 $2 \cdot n$ 次询问内，找到一种合法的顶点染色方案。可以证明，总是存在这样的染色方案。 注意，评测机不是自适应的：图在所有询问前就已确定。 $^\dagger$ 如果存在一条从顶点 $b$ 到顶点 $a$ 的路径，则称顶点 $a$ 可以从顶点 $b$ 到达。详见[路径](https://en.wikipedia.org/wiki/Path_(graph_theory))。

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 1000$）——表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的唯一一行包含一个整数 $n$（$3 \le n \le 100$）——隐藏图的顶点数。 保证所有测试用例中 $n$ 的总和不超过 $1000$。

每个测试用例的交互从读取整数 $n$ 开始。 每次询问时，输出 "? i j"（不带引号，$1 \le i < j \le n$）。如果顶点 $i$ 可以从顶点 $j$ 到达，你将收到 YES 作为回答，否则收到 NO。 如果你收到 $-1$ 作为回答或作为 $n$ 的值，说明你的程序进行了非法询问、超出了询问次数限制，或在上一个测试用例中给出了错误答案。你的程序必须立即终止，否则会收到 Wrong Answer 判定。否则，你的程序会继续读取已关闭流的数据，可能得到任意判定。 当你准备好给出最终答案时，输出 "! c_1\ c_2\ \ldots\ c_n"（不带引号）——表示每个顶点的颜色，其中 $c_i = 0$ 表示黑色，$c_i = 1$ 表示白色。所有测试用例结束后，程序应立即终止。 每次输出询问后，别忘了输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 时请使用如下格式： 第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 100$，$0 \le m \le \frac{n\cdot(n - 1)}{2}$）——图的顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le b < a \le n$），表示存在一条从 $a$ 到 $b$ 的有向边。图必须满足上述条件。 所有测试用例中 $n$ 的总和不超过 $1000$。

第一个测试用例中的隐藏图：  第二个测试用例中的隐藏图：  交互过程如下： | Solution | Jury | Explanation | |----------|------|-------------| | 2 | | 有 $2$ 个测试用例。 | | 4 | | 第一个测试用例，图有 $4$ 个顶点。 | | ? 1 2 | YES | 询问顶点 $1$ 是否可以从顶点 $2$ 到达，评测机回答 YES。 | | ? 2 3 | YES | 询问顶点 $2$ 是否可以从顶点 $3$ 到达，评测机回答 YES。 | | ? 1 3 | YES | 询问顶点 $1$ 是否可以从顶点 $3$ 到达，评测机回答 YES。 | | ? 1 4 | NO | 询问顶点 $1$ 是否可以从顶点 $4$ 到达，评测机回答 NO。 | | ? 2 4 | NO | 询问顶点 $2$ 是否可以从顶点 $4$ 到达，评测机回答 NO。 | | ? 3 4 | NO | 询问顶点 $3$ 是否可以从顶点 $4$ 到达，评测机回答 NO。 | | ! 0 0 0 1| | 程序得出一种合法染色并输出。答案正确，进入下一个测试用例。 | | 5 | | 第二个测试用例，图有 $5$ 个顶点。 | | ! 1 1 0 1 0 | | 程序得出一种合法染色并输出。答案正确且没有更多测试用例，程序和评测机均退出。 | 注意，示例输入输出中的换行仅为便于阅读，实际交互中不会出现。 由 ChatGPT 4.1 翻译