AORイカちゃん と そすうさ がグラフを使った場所当てゲームを行う.
最初に,AORイカちゃん が整数 $N$ を指定し,そすうさ は頂点数 $N$ の無向グラフを生成する. $N$ 個の頂点には, $1$ ~ $N$ までの番号が割り振られている.この無向グラフを使って,$K$ 回ゲームを行う.
各ゲームのはじめに AORイカちゃん は頂点を $1$ つ選び,そすうさ がその頂点を当てる.
そすうさ は AORイカちゃん に最大 $10$ 回まで質問することができる. そすうさ が頂点番号を $1$ つ AORイカちゃん に伝えると,番号に従い AORイカちゃん は以下のうちどれかを答える.
AORイカちゃん の返事 | 意味 |
---|---|
Yes | その頂点が当たり |
Near | Yesではなく,その頂点に隣接する頂点が当たり |
No | それ以外 |
$K$ 回のゲーム全てで $10$ 回以内に頂点を当てることができれば,そすうさ の勝ちである. どうしても勝ちたい そすうさ は,あなたに絶対に勝てるプログラムの作成をお願いしてきた.
まず,以下の形式で頂点数 $N$ とゲーム回数 $K$ が与えられる.
$N\ K$
次に,生成した無向グラフを以下の形式で出力する.
$M$
$a_{1} b_{1}$
$\vdots$
$a_{M} b_{M}$
ここで、 $M$ は生成した無向グラフの辺の本数であり, $a_i$, $b_i$ はグラフの $i$ 本目の辺が頂点 $a_i$ と頂点 $b_i$ を繋いでいることを示す.
なお, 生成する無向グラフは $ 0 \leq M \leq \frac{N(N-1)}{2}$ かつ $1 \leq a_i, b_i \leq N$ を満たさなければならない.
続いて,あなたのプログラムは何回か応答プログラムに質問をする.質問のフォーマットは以下のとおりである.
Num
$Num$ は $1$ 以上 $N$ 以下の頂点番号である. この質問で,'Yes','Near','No'のうち,どれかが標準入力に $1$ 行で渡される.
'Yes'が渡されれば勝利となり,$1$ 回のゲームが終了する. $1$ 回のゲームが終了したら,すぐに次のゲームが始まることに注意せよ. 各ゲーム最大 $10$ 回以内の質問で勝利しなければいけない.
このゲームを $K$ 回行い,すべてのゲームで勝利すれば正答となる.
ゲームが終了した後,あなたのプログラムは直ちに終了しなければならない.終了しなかった場合のジャッジ結果は不定である. また,これら以外のフォーマットで出力した場合のジャッジ結果も不定である.
なお,グラフの情報や質問を応答プログラムに送ったあとフラッシュしないとTLEとなることがある.
フラッシュはCでは
fflush(stdout);
C++では
std::cout << endl;
で行うことができる. fflush() は stdio.h をインクルードすると使用できる.
プログラムへの入力 | プログラムの出力 |
---|---|
3 2 | |
2 1 2 2 3 |
|
1 | |
No | |
3 | |
Yes | |
2 | |
Near | |
3 | |
No | |
1 | |
Yes |