問題文

この問題はインタラクティブな問題です。

パ研町には N 戸の家があり、 1, 2, \ldots, N の番号が付いています。また家と家を双方向に結ぶ 0 本以上の道路があり、道路は 300 本以下であることが分かっていますが、何本あるかや、それぞれの道路がどの家とどの家を結んでいるかは分かりません。ただし、両端が同じ家を結んでいる道路はなく、複数の道路が同じ家の組を結んでいることもありません。

パ研町の町長となったあなたは、これから毎日 1 回ずつ集会を開きます。 N 戸の家それぞれについて、その家の住人を招待するかしないか決めることができます。

しかし、パ研町は非常に険悪な町です。特に隣人、つまり 1 つの道路で結ばれた 2 つの家に住む住人は、集会で顔を合わせるだけで集会の全員を巻き込んだ乱闘が起きてしまいます。

さて、あなたはパ研町の道路の本数や、それぞれの道路がどの家とどの家を結んでいるかを調べたいと思いました。そこで、各日に集会に招待する人を工夫し、乱闘が起きるかどうかを調べることで、パ研町の構造を調べることにしました。

これは明らかに職権濫用なので、 3200 日間までしか集会を開けません。集会に招待する人を決める戦略を定めるプログラムを作成してください。

なお、あなた自身は誰とも隣人でないものとします。また、誰も呼ばずに一人で集会を行うこともできます。

制約

• N は整数
• 1 \leq N \leq 200
• 道路は 300 本以下である。
• 両方の端が同じ 1 つの家となっている道路はない
• 複数の道路が同じ家の組を結んでいることはない

小課題

1. (50 点) N \leq 80
2. (100 点) どの道路についても、その道路が結ぶ 2 つの家の番号の偶奇が異なる
3. (150 点) どの家 a, b, c についても、 a と b を結ぶ道路が存在し、 a と c を結ぶ道路が存在しない場合、 b と c を結ぶ道路が存在する
4. (400 点) 追加の制約はない

入出力

最初に、 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 が逆になっていても構わない。

注意

• 出力の度に標準出力を flush せよ。そうしない場合、ジャッジ結果は不定である。
• 全ての道路を出力した後プログラムを終了させなかった場合、ジャッジ結果は不定である。
• 不正な質問や不正な出力を行った場合、ジャッジ結果は不定である。

入出力例

この入出力例では、 N=4 で道路が 4 本あり、それぞれの道路が家 1, 2 、家 2, 3 、家 3, 4 、家 4, 1 を結ぶ場合のジャッジとのやり取りの一例を示している。

ただしこれはあくまで入出力例であり、意味のあるやり取りをしているとは限らないことに注意せよ。

なお、この入力例は全ての小課題の制約を満たす。