AT_pakencamp_2022_day2_g Worst Town

**この問題はインタラクティブな問題です。** パ研町には $ N $ 戸の家があり、 $ 1, 2, \ldots, N $ の番号が付いています。また家と家を双方向に結ぶ $ 0 $ 本以上の道路があり、道路は $ 300 $ 本以下であることが分かっていますが、何本あるかや、それぞれの道路がどの家とどの家を結んでいるかは分かりません。ただし、両端が同じ家を結んでいる道路はなく、複数の道路が同じ家の組を結んでいることもありません。 パ研町の町長となったあなたは、これから毎日 $ 1 $ 回ずつ集会を開きます。 $ N $ 戸の家それぞれについて、その家の住人を招待するかしないか決めることができます。 しかし、パ研町は非常に険悪な町です。特に隣人、つまり $ 1 $ つの道路で結ばれた $ 2 $ つの家に住む住人は、集会で顔を合わせるだけで集会の全員を巻き込んだ乱闘が起きてしまいます。 さて、あなたはパ研町の道路の本数や、それぞれの道路がどの家とどの家を結んでいるかを調べたいと思いました。そこで、各日に集会に招待する人を工夫し、乱闘が起きるかどうかを調べることで、パ研町の構造を調べることにしました。 これは明らかに職権濫用なので、 $ 3200 $ 日間までしか集会を開けません。集会に招待する人を決める戦略を定めるプログラムを作成してください。 なお、あなた自身は誰とも隣人でないものとします。また、誰も呼ばずに一人で集会を行うこともできます。 ### Input & Output Format 最初に、 $ N $ が以下の形式で入力で与えられる。 > $ N $ 次に、あなたは質問を繰り返しすることができる。この質問の回数は $ 3200 $ 回以下である必要がある。 > ? $ S $ ただし、 $ S $ は `0` と `1` からなる長さ $ N $ の文字列であり、 $ 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 $ が逆になっていても構わない。

N/A

N/A

### 小課題 1. ( $ 50 $ 点) $ N \leq 80 $ 2. ( $ 100 $ 点) どの道路についても、その道路が結ぶ $ 2 $ つの家の番号の偶奇が異なる 3. ( $ 150 $ 点) どの家 $ a, b, c $ についても、 $ a $ と $ b $ を結ぶ道路が存在し、 $ a $ と $ c $ を結ぶ道路が存在しない場合、 $ b $ と $ c $ を結ぶ道路が存在する 4. ( $ 400 $ 点) 追加の制約はない ### 注意 - **出力の度に標準出力を flush せよ。**そうしない場合、ジャッジ結果は不定である。 - 全ての道路を出力した後プログラムを終了させなかった場合、ジャッジ結果は不定である。 - 不正な質問や不正な出力を行った場合、ジャッジ結果は不定である。 ### 入出力例 この入出力例では、 $ 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 なお、この入力例は全ての小課題の制約を満たす。 ### Constraints - $ N $ は整数 - $ 1 \leq N \leq 200 $ - 道路は $ 300 $ 本以下である。 - 両方の端が同じ $ 1 $ つの家となっている道路はない - 複数の道路が同じ家の組を結んでいることはない