ストーリー

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

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

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

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

問題文

爆弾は $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$ 本を超える。
• 出力より多くの端子を無力化できる解が存在する。

---

制約

• $2 \\leq N \\leq 800$

入出力

最初に、標準入力から $N$ が以下のように与えられる:

$N$

次に、「トグル」および「検定」クエリを $0$ 回以上行う。各クエリは、標準出力に以下の形式で出力しなければならない。

「トグル」クエリ:

$1$ $U_i$ $V_i$

ただし、$1 \\leq U_i, V_i \\leq N, U_i \\neq V_i$ でなければならない。この直後には、標準入力には何も与えられない。

「検定」クエリ:

$2$ $U_i$ $V_i$

ただし、$1 \\leq U_i, V_i \\leq N, U_i \\neq V_i$ でなければならない。この直後に、質問の答えが標準入力から以下の形式で与えられる:

ans

ここで、$ans$ は Y または N である。

最後に、解答を出力する。これらは以下の形式で出力しなければならない:

0 $K$ 0 $A_1$ $A_2$ $\\vdots$ $A_K$

その後、直ちにプログラムを終了すること。

---

ジャッジ

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

サンプル

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

入力

出力

$3$

$1$ $2$ $3$

$1$ $1$ $3$

$2$ $3$ $1$

$Y$

$2$ $2$ $1$

$Y$

$2$ $3$ $2$

$N$

$1$ $1$ $2$

$2$ $3$ $2$

$Y$

$0$ $3$ $0$

$3$

$1$

$2$

---

解説

解説