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$ 到达。详见路径。

每个测试包含多个测试用例。输入的第一行包含一个整数 $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 翻译