Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 1100 点
ストーリー
(ちょっと、想定外です…)せんぱいが魔法陣で移動した直後、わたしは背後から来た異形に囚われてしまった。
(せんぱいに心配をかけるわけにはいかない、けど…)拘束は厳しく、取り付けられた爆弾のようなものも集中を妨げる。
(せめて、せんぱいだけは…)思考が停滞していく。そこに、聞き慣れた声が飛び込んできた。
「いろはちゃん!…助けに、来たよ!」
問題文
爆弾は 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 |