这是一个交互问题。
婴儿 Ehab 喜欢在他的公寓里爬来爬去。它有 $$$n$$$ 房间,编号从 $$$0$$$ 到 $$$n-1$$$。对于每对房间 $$$a$$$ 和 $$$b$$$,都有从房间 $$$a$$$ 到房间 $$$b$$$ 的直接通道,或者从房间 $$$b$$$ 到房间 $$$a$$$ 的直接通道,但绝不会同时存在。
宝宝 Ehab 想和宝宝 Badawy 一起玩。他想知道他是否能找到他。然而,除了房间数量之外,他对自己的公寓一无所知。他可以问保姆两类问题:
- 房间$$$a$$$和房间$$$b$$$之间的通道是从$$$a$$$指向$$$b$$$还是相反?
- $$$x$$$ 房间是否有通向 $$$s_1$$$、$$$s_2$$$、...、$$$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$$$。
互动
要提出第一类问题,请使用以下格式:
- $$$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$$$ ... $$$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$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客:
第一行应包含一个整数 $$$t$$$ — 测试用例的数量。
每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$4 \le n \le 100$$$) — 房间数量。
接下来的 $$$n$$$ 行应包含长度为 $$$n$$$ 的二进制字符串。如果有从房间 $$$i$$$ 到房间 $$$j$$$ 的通道,则第 $$$i$$$ 字符串的第 $$$j$$$ 个字符应为 $$$1$$$,否则为 $$$0$$$。第 $$$i$$$ 字符串的第 $$$i$$$ 字符应为 $$$0$$$。
输出
To print the answer for a test case, print a line containing "3", followed by $$$n$$$ lines, each containing a binary string of length $$$n$$$.如果存在从房间 $$$i$$$ 到房间 $$$j$$$ 的路径,则第 $$$i$$$ 字符串的第 $$$j$$$ 个字符应为 $$$1$$$,如果没有,则为 $$$0$$$。对于每个有效的 $$$i$$$,第 $$$i$$$ 字符串的第 $$$i$$$ 个字符应为 $$$1$$$。
打印答案后,我们将用一个整数进行响应。如果是 $$$1$$$,则您打印了正确的答案,并且应该继续解决测试用例(如果是最后一个,则退出)。如果是 $$$-1$$$,则您打印了错误的答案,应该终止以获得错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
示例
输入 #1
1 4 0 0 1 1 1
输出 #1
2 3 3 0 1 2 1 0 1 1 0 2 2 2 1 1 3 1111 1111 1111 0001
注意
在给定的示例中:
第一个查询询问是否有从房间 $$$3$$$ 到任何其他房间的通道。
第二个查询询问房间 $$$0$$$ 和 $$$1$$$ 之间的通道方向。
经过几次其他查询后,我们得出的结论是,你可以从任何房间到任何其他房间,除非你从 $$$3$$$ 房间开始,并且你无法离开这个房间,所以我们打印了矩阵:
交互者回答了$$$1$$$,告诉我们答案是正确的。