ストーリー

（ちょっと、想定外です…）せんぱいが魔法陣で移動した直後、わたしは背後から来た異形に囚われてしまった。

（せんぱいに心配をかけるわけにはいかない、けど…）拘束は厳しく、取り付けられた爆弾のようなものも集中を妨げる。

（せめて、せんぱいだけは…）思考が停滞していく。そこに、聞き慣れた声が飛び込んできた。

「いろはちゃん！…助けに、来たよ！」

問題文

爆弾は N 個の端子を持つ。任意の 2 端子間にはコードがちょうど 1 本存在し、特定の方向にのみ電流が流れる(つまり、爆弾は完全グラフの各辺に適当に向きをつけたものである)。この方向は入力で与えられない。 各コードにはスイッチがあり、オン・オフを切り替えられるが、はじめはすべてオフになっている。爆弾は次のように解体しなければならない。

• 無力化する端子の個数 K を指定する。
• その後、K 個の相異なる端子の番号 A_1, A_2, \cdots , A_K を指定し、順番に無力化する。
• ただし、全ての 1 \leq i < K について、A_i, A_{i+1} 間のコードが電流を流す方向は A_i \rightarrow A_{i+1} である。

あなたの仕事は、次の 2 種類のクエリを何回か呼んだ後、解体手順 K, {A_i} を出力することである。

• 「トグル」: 2 つの端子 U_i, V_i を指定し、その間のコードのオン・オフを切り替える。ただし、オンになっているコードが 2N 本を超えた場合、即座に爆弾が爆発する。
• 「検定」: 2 つの端子 U_i, V_i を指定する。端子 U_i から現在オンになっているコードのみを経由して端子 V_i に電流が流れる場合 Y、流れない場合 N と判定される。

ただし、次のいずれかの条件を満たすと、爆弾は爆発してしまい、不正解となる。

• クエリや解答が invalid である。
• 「トグル」クエリを、666666 回を超えて呼び出す。
• 「検定」クエリを、10000 回を超えて呼び出す。
• オンになっているコードが 2N 本を超える。
• 出力より多くの端子を無力化できる解が存在する。

ジャッジ

• 出力のあと、標準出力を flush しなければならない。 そうでないときは TLE の恐れがある。
• 解答を出力したあと、プログラムはすぐに終了しなければならない。そうでない場合の挙動は未定義である。
• 出力が誤っていたときの挙動は未定義である。

サンプル

このサンプルでは N = 3 で、電流の向きは 1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 1 である。また、出力された解答は K = 3, {A_i} = 3 \rightarrow 1 \rightarrow 2 である。

解説

解説