CF1514E Baby Ehab's Hyper Apartment

这是一个交互题。 小宝宝 Ehab 喜欢在他的公寓里爬来爬去。公寓里有 $n$ 个房间，编号从 $0$ 到 $n-1$。对于每一对房间 $a$ 和 $b$，要么存在一条从房间 $a$ 到房间 $b$ 的单向通道，要么存在一条从房间 $b$ 到房间 $a$ 的单向通道，但绝不会同时存在两条。 小宝宝 Ehab 想去找小宝宝 Badawy 玩。他想知道自己是否能到达 Badawy 所在的房间。然而，他只知道房间的数量，对公寓的其他情况一无所知。他可以向保姆提出两种类型的问题： - 房间 $a$ 和房间 $b$ 之间的通道是从 $a$ 到 $b$，还是反过来？ - 房间 $x$ 是否有通道通向房间 $s_1, s_2, \ldots, s_k$ 中的任意一个？ 他最多可以提出 $9n$ 次第一类问题，最多可以提出 $2n$ 次第二类问题。 在询问了一些问题后，他想知道对于每一对房间 $a$ 和 $b$，是否存在一条从 $a$ 到 $b$ 的路径。所谓从 $a$ 到 $b$ 的路径，是指一系列通道，起点为房间 $a$，终点为房间 $b$。

第一行包含一个整数 $t$（$1 \le t \le 30$），表示需要解决的测试用例数量。 每个测试用例以一个整数 $n$ 开头（$4 \le n \le 100$），表示房间的数量。 所有测试用例中 $n$ 的总和不超过 $500$。

对于每个测试用例，输出一行 "3"，接下来输出 $n$ 行，每行包含一个长度为 $n$ 的二进制字符串。第 $i$ 行的第 $j$ 个字符应为 $1$，如果存在从房间 $i$ 到房间 $j$ 的路径，否则为 $0$。对于每个合法的 $i$，第 $i$ 行的第 $i$ 个字符应为 $1$。 在输出答案后，我们会回复一个整数。如果是 $1$，说明你的答案正确，可以继续解决下一个测试用例（如果还有的话）；如果是 $-1$，说明你的答案错误，应立即退出，否则会得到 Wrong answer 判定。否则，你的程序会继续读取已关闭的流，可能会得到任意判定。 交互说明 要提出第一类问题，使用以下格式： - $1\ a\ b$（$0 \le a,b \le n-1$，$a \neq b$）。 - 如果通道是从 $a$ 到 $b$，我们会回复 $1$，如果是从 $b$ 到 $a$，我们会回复 $0$。 - 每个测试用例最多可以提出 $9n$ 次此类问题。 要提出第二类问题，使用以下格式： - $2\ x\ k\ s_1\ s_2\ \ldots\ s_k$（$0 \le x,s_i \le n-1$，$0 \le k < n$，$x \neq s_i$，$s$ 中元素两两不同）。 - 如果存在从 $x$ 到 $s$ 中任意一个房间的通道，我们会回复 $1$，否则回复 $0$。 - 每个测试用例最多可以提出 $2n$ 次此类问题。 如果我们回复 $-1$ 而不是有效答案，说明你超出了查询次数或查询不合法。收到 $-1$ 后应立即退出，否则会得到 Wrong answer 判定。否则，你的程序会继续读取已关闭的流，可能会得到任意判定。 每次输出查询后，不要忘记输出换行并刷新输出缓冲区。否则会得到 Idleness limit exceeded。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档。 Hack 数据格式： 第一行包含一个整数 $t$，表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$4 \le n \le 100$），表示房间数量。 接下来 $n$ 行，每行一个长度为 $n$ 的二进制字符串。如果房间 $i$ 到房间 $j$ 有通道，则第 $i$ 行第 $j$ 个字符为 $1$，否则为 $0$。第 $i$ 行第 $i$ 个字符为 $0$。

在给定的示例中：  第一次查询询问房间 $3$ 是否有通道通向其他任意房间。 第二次查询询问房间 $0$ 和房间 $1$ 之间的通道方向。 经过几次查询后，我们得出结论：除了从房间 $3$ 出发无法到达其他房间外，其他任意房间都可以到达任意房间。因此我们输出如下矩阵： ``` 1111 1111 1111 0001 ``` 交互器回复 $1$，表示答案正确。 由 ChatGPT 4.1 翻译