E: 札 / Fuda

この問題はリアクティブ問題です。 サーバー側に用意されたプログラムと対話的に応答することで正答を導くプログラムを作成する必要があります。

問題文

湖に浮かぶ $N$ 個の小島からなるビワコという村がある。 各小島には $0$ から $N-1$ まで番号が振られている。 村には島と島の間に架かる橋が $M$ 本あり、$0$ から $M-1$ まで番号が振られている。 橋は双方向に移動可能である。 ここで言う橋とは単に島と島の間の通り道ということであり、取り除くと互いに到達不可能な島の組が増える意味ではない。

最近、橋の両端に掲示板を設置し、その橋を渡った先の島から橋を $1$ 本だけ使って移動できる島 (今いる島を含まない) の番号の書かれた札を貼ることで、 スムーズな移動を実現する計画が持ち上がった。 一枚の札には一つの移動先しか書くことが出来ないため、移動できる島の数だけ札が必要になる。

この札の作成を命じられたあなたは、札は全部で何枚必要かを調べることにした。 村には、かつて全ての橋を架けた橋職人がいる。 また、各島にはその島に住んでいる村人がいる。 村は広大で全ての掲示板を見て回るのは骨が折れるため、本部から電話で彼らに質問をすることで必要な札の枚数を求めることにした。

橋職人への質問では、まず、何番の橋の情報が知りたいかを橋職人に伝える。 すると、どの島とどの島の間に該当する橋を架けたかを確実に教えてくれる (edgクエリ)。 住人への質問では、まず聞きたい島の番号$i$を伝える。 すると、島 $i$ にかかる橋の数とその橋がどこにかかっているかを教えてくれる (lst クエリ)。 しかし、貧弱な通信網を使用しているため、各橋に対して、80% の確率で情報が抜け落ちてしまう。

札の発注まで時間がないので全体で多くても $3N$ 回しか質問ができない。 以上の条件のもとで、必要な札の数を求めるプログラムを書きなさい。

入出力仕様

以降では、あなたが提出したプログラムを「解答」、ジャッジ側が用意したプログラムを「ジャッジ」と呼ぶ。 入出力の詳細な仕様を以下に示すが、先にサンプルを見ると速い。

島と橋の数

ジャッジは、まず島の数 $N$ と橋の数の合計 $M$ を $1$ 行に出力する。

N M

続いて、解答は edg, lst クエリを最大 $3N$ 回、 ans をちょうど 1 回ジャッジに対して送ることができる。

edg クエリ

解答の edg クエリに対し、ジャッジは橋$i$の両端の島の番号を答える。解答は次の形式で出力せよ。

edg i

これに対して、ジャッジは次の形式で応答する。

a b

$a$, $b$ は橋 $i$ が結ぶ島の番号である。

lst クエリ

解答の lst クエリに対し、ジャッジは小島 $i$ にかかる橋の本数と、それぞれの橋の行き先の島の番号を答える。解答は次の形式で出力せよ。

lst i

これに対して、ジャッジは次の形式で応答する。

k v1 v2 v3 … vk

$k$ は島 $i$ にかかる橋の数である。 続く $v_1 \cdots v_k$ は頂点$i$から橋を一度だけ使って移動可能な頂点の番号のリストである。 各橋の行き先 $v_j$ に対し、$v_j \ge 0$ の場合はその情報がしっかり伝わったことを表す。$v_j = -1$ の場合は情報が抜け落ちていることを表す。 $-1$ かどうかは乱数で決められ、80% の確率で $-1$ となる。したがって、同じ $i$ に対して複数回このクエリを実行すると、結果は変わりうる。また、順番も不定である。

ans クエリ

解答の ans クエリによって、答えを出力できる。このクエリは 1 度しか行うことが出来ず、結果が正しくない場合は直ちに誤答となる。 このクエリの実行後に、解答は直ちに正常終了せよ。 $X$ を答えとして出力したい場合の形式は以下の通りである。

ans X

制約と注意

• $1 \le N \le 100$
• $0 \le M \le N(N-1)/2$
• 橋は異なる 2 つの島の間に架かっている。
• 異なる橋が、同じ 2 つの島を結ぶことはない。
• ans 以外のクエリは高々 $3N$ 回しか投げられない。
• ジャッジプログラムの出力は全て $1$ 行かつスペース区切りの整数からなる。
• 仕様に従わない出力の結果は不定である。
• 解答はジャッジの応答をすぐに標準入力で受け取らなければならない。
• 解答はクエリを出力した直後にバッファを空にせよ。最小の解答プログラム例を下に示す。C、C++以外の言語は各自で調べてほしい。

C

#include <stdio.h>
int main(){
    int n,m;
    scanf("%d %d", & n, &m);
    printf("ans 100\n"); // 答えをジャッジに提出
    fflush(stdout); // フラッシュ
    return 0;
}

C++

#include <iostream>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    cout << "ans 100" << endl; // 改行直後にフラッシュ
    // cout << "ans 100\n" << flush; // 上と同じ
}

サンプル

解答プログラムとジャッジプログラムの入出力例を以下に示す。 問題文の図中の村に対する答えを求めている。