AT_pakencamp_2022_day2_g Worst Town

**本题为交互题。** 在“パ研町”有 $N$ 户人家，编号分别为 $1, 2, \ldots, N$。各家之间通过道路相互连接，道路总数不小于 $0$ 条且不超过 $300$ 条，但具体的数量及道路分别连接了哪些房屋你一概不知。保证道路不会自环（即没有道路连接同一房屋），也不会有多条道路连接同一对房屋。 作为新任镇长，你打算每天召开一次集会。对于每一户人家，你可以选择是否邀请该户居民参与集会。 但这个镇的邻里关系极为恶劣，特别是“邻居”：即通过一条道路直接相连的两户人家，如果他们一起出现在集会，将引发涉及所有参与者的大混战。 你希望调查出镇上的道路数量以及每条道路连接的房屋。为此，你可以通过集会的组织名单和是否发生混战的信息对镇子的结构进行调查。 需要注意，滥用职权不可无度，你只能召开至多 $3200$ 次集会。请编写程序，设计你的每次集会邀请名单并决定何时结束调查，最终准确输出所有道路的信息。 另外，假设你自己与镇上任何居民都不是邻居。你也可以选择一个人默默开会，即不邀请任何人参加。

首先，以如下格式输入 $N$： > $N$ 随后，你可以重复进行提问，每次的总提问次数不能超过 $3200$ 次。 > ? $S$ 其中 $S$ 是一个长度为 $N$ 的由 `0` 和 `1` 组成的字符串，$S_i = 0$ 表示不邀请第 $i$ 户居民，$S_i = 1$ 表示邀请第 $i$ 户居民。 此后，评测器会对你的提问进行回复，返回值为下述之一： - `Yes`：发生了混战。 - `No`：未发生混战。 - `-1`：提问或输出不合法，包括提问超过 $3200$ 次。 确定所有道路信息后，按如下格式输出所有道路： > ! $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$ 其中 $M$ 表示道路总数，第 $i$ 条道路连接房屋 $a_i$ 和 $b_i$。 道路输出的顺序任意，$a_i$ 和 $b_i$ 顺序也任意。

# 提示 ## 小题 1.（$50$ 分）$N \leq 80$ 2.（$100$ 分）任意道路所连接的两户房屋的编号奇偶性不同 3.（$150$ 分）对任意三户 $a, b, c$，若存在道路连接 $a$ 与 $b$，且存在道路连接 $a$ 与 $c$，则一定存在道路连接 $b$ 与 $c$ 4.（$400$ 分）无额外限制 ## 注意事项 - **每次输出后，务必立即刷新标准输出缓冲区。** 否则可能导致评测结果异常。 - 输出所有道路后，若程序未能正确终止，则评测结果不确定。 - 若进行非法提问或非法输出，也会导致评测结果不确定。 ### 输入输出样例 在下例输入输出场景中，$N=4$，有 $4$ 条道路分别连接房屋 $1$ 与 $2$，$2$ 与 $3$，$3$ 与 $4$，$4$ 与 $1$。交互过程如下： 测评器输出（你的程序输入） 你的程序输出 4 ? 1011 Yes ? 0101 No ? 1001 Yes ! 4 1 2 2 3 3 4 4 1 注意，这只是一组输入输出样例，未必是合理的查询流程，但各小题限制均满足。 # 输入格式 # 输出格式

## 小题 1.（$50$ 分）$N \leq 80$ 2.（$100$ 分）任意道路所连接的两户房屋的编号奇偶性不同 3.（$150$ 分）对任意三户 $a, b, c$，若存在道路连接 $a$ 与 $b$，且存在道路连接 $a$ 与 $c$，则一定存在道路连接 $b$ 与 $c$ 4.（$400$ 分）无额外限制 ## 注意事项 - **每次输出后，务必立即刷新标准输出缓冲区。** 否则可能导致评测结果异常。 - 输出所有道路后，若程序未能正确终止，则评测结果不确定。 - 若进行非法提问或非法输出，也会导致评测结果不确定。 ### 输入输出样例 在下例输入输出场景中，$N=4$，有 $4$ 条道路分别连接房屋 $1$ 与 $2$，$2$ 与 $3$，$3$ 与 $4$，$4$ 与 $1$。交互过程如下： 测评器输出（你的程序输入） 你的程序输出 4 ? 1011 Yes ? 0101 No ? 1001 Yes ! 4 1 2 2 3 3 4 4 1 注意，这只是一组输入输出样例，未必是合理的查询流程，但各小题限制均满足。 # 输入格式 # 输出格式 # 提示 - $N$ 为整数。 - $1 \leq N \leq 200$。 - 道路总数不超过 $300$。 - 不存在自环的道路。 - 不存在多重边。 由 ChatGPT 5 翻译