問題文

あなたは Just Odd Inventions 社を知っているだろうか？　この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．

JOI 社のとある実験室には，複雑な電気回路がある． 回路は N 個の節点と M 本の細長い電気抵抗からなり，節点には 0 から N - 1 までの，電気抵抗には 0 から M - 1 までの番号が付けられている． 各節点は「高電圧」または「低電圧」のいずれかの状態に設定することができる． 電気抵抗 i (0 \leqq i \leqq M - 1) は節点 A_i から異なる節点 B_i に向けて繋がれており，節点 A_i が「高電圧」，節点 B_i が「低電圧」の状態にあるときにのみ電流が流れる． それ以外の場合には電流は流れない． また，任意の 2 つの節点を繋ぐ電気抵抗は，その向きに関わらず高々 1 本しか存在しない．

JOI 社の研究員であるあなたは，この回路を用いて実験を行うことになった． この回路の電気抵抗はあまりにも細長いため，電気抵抗がどの節点を結んでいるのかを目視で確認することはできない． しかし，各節点の電圧を設定している間，電流が流れている電気抵抗の本数に応じて回路の温度が上昇するという手がかりがある． そこであなたは，電圧を設定した後，回路に触れることで温度を読み取ることにした． あなたは回路の温度を正確に読み取ることはできないが，電圧の設定を 2 回行い，どちらの設定においてより温度が高くなったかを比較することはできる． つまり，電圧の設定を 2 回指定することで，以下のいずれかの情報が得られる．

• 1 回目の電圧の設定の方が，電流が流れる電気抵抗の本数が多い．
• 2 回の電圧の設定において，電流が流れる電気抵抗の本数は同じである．
• 2 回目の電圧の設定の方が，電流が流れる電気抵抗の本数が多い．

あなたの目的は，この温度の比較を繰り返すことで，どの節点からどの節点へ向かう電気抵抗が存在するかをすべて特定することである． あらかじめ，節点の数 N，電気抵抗の本数 M は与えられている． また，電気抵抗は異なる節点を繋いでいること，および任意の 2 つの節点を繋ぐ電気抵抗はその向きに関わらず高々 1 本であることも分かっている． これらの条件のもと，温度の比較によって得られた情報から，回路に存在する電気抵抗が繋ぐ節点のペア (a, b) の集合をすべて特定せよ． ただし，回路の構造によっては，いかなる比較を何回行ったとしても，電気抵抗の繋がりを一意に特定できない場合がある． その場合には，特定不能であることを報告する必要がある．

電気抵抗の劣化を防ぐため，実際に温度を比較するのは 30\,000 回までしか行うことが許されない．

なお，JOI 社がこの奇妙な回路を用いてどのような発明をしているかは，社内でも最高機密であり社長以外の誰も知らない．

回路の節点と電気抵抗の本数が与えられたとき，30\,000 回以下の温度の比較で，回路の電気抵抗を特定するかもしくは特定不能であることを報告するプログラムを作成せよ．

実装の詳細

あなたの回答プログラムは，voltage.h を #include プリプロセッサ指令で読み込み，以下の関数を実装しなければならない．

• bool solve(int N, int M)
  • この関数は 1 回の実行で 1 回だけ呼び出される．
  • 引数 N は 回路の節点の数 N である．
  • 引数 M は 回路の電気抵抗の本数 M である．
  • この関数は，いかなる温度の比較を何回行ったとしても電気抵抗の繋がりを一意に特定できない場合には false を，それ以外の場合には true を返さなければならない．
  • 電気抵抗の繋がりを特定不能であるのに true を返した場合，不正解[1] と判定される．
  • 温度の比較によって回路が特定できるのに false を返した場合，不正解[2] と判定される．

あなたのプログラムは以下の関数を呼び出すことができる．

• int query(std::vector<int> x, std::vector<int> y)
  • あなたはこの関数を用いて電圧の設定を 2 回行い，温度を比較できる．
  • 引数 x は 1 回目の電圧の設定を，引数 y は 2 回目の電圧の設定を指定する．
  • 引数 x と y は 0 と 1 からなる長さ N の配列でなければならない．
  • x[k] (0 \leqq k \leqq N - 1) が 1 ならば 1 回目の電圧の設定において，節点 k は「高電圧」に， x[k] が 0 ならば節点 k は「低電圧」に設定することを表す．
  • y[k] (0 \leqq k \leqq N - 1) が 1 ならば 2 回目の電圧の設定において，節点 k は「高電圧」に， y[k] が 0 ならば節点 k は「低電圧」に設定することを表す．
  • この関数の戻り値は 1 回目の電圧の設定と 2 回目の電圧の設定において，温度を比較した結果であり，-1,0,1のいずれかの値である．
    • 戻り値が-1のとき，1 回目の方が，2 回目の電圧の設定より，電流が流れる電気抵抗の本数が多いことを表す．
    • 戻り値が0のとき，1 回目と2 回目の電圧の設定において電流が流れる電気抵抗の本数が等しいことを表す．
    • 戻り値が1のとき，2 回目の方が，1 回目の電圧の設定より，電流が流れる電気抵抗の本数が多いことを表す．
  • 引数 x の長さが N でない場合，不正解[3] と判定される．
  • 引数 x に 0 でも 1 でもない値が含まれる場合，不正解[4] と判定される．
  • 引数 y の長さが N でない場合，不正解[5] と判定される．
  • 引数 y に 0 でも 1 でもない値が含まれる場合，不正解[6] と判定される．
  • この関数を 30\,000 回より多く呼び出してはならない．30\,000 回より多く呼び出した場合，不正解[7] と判定される．
• void answer(int a, int b)
  • この関数を用いて，特定した電気抵抗を解答する．
  • 引数 a, b は節点 a から節点 b に向けて繋がれている電気抵抗があることを表す．
  • 0 \leqq a \leqq N - 1 かつ 0 \leqq b \leqq N - 1 でなければならない．これが満たされない場合 不正解[8] と判定される．
  • 同じ (a, b) の組を引数として 2 回以上呼び出してはならない．これが満たされない場合 不正解[9] と判定される．
  • この関数を M 回より多く呼び出してはならない．M 回より多く呼び出した場合，不正解[10] と判定される．
  • 関数 solve が true を返したとき，それまでに関数 answer はちょうど M 回呼び出されている必要がある． これが満たされない場合，不正解[11] と判定される．
  • 関数 solve が true を返したとき，それまでに関数 answer の引数として渡されたすべての組 (a, b) について，節点 a から節点 b へ向けて繋がれている電気抵抗が実際に存在していなければならない． これが満たされない場合，不正解[12] と判定される．

重要な注意

• 内部での使用のために他の関数を実装したり，グローバル変数を宣言するのは自由である．
• あなたの提出したプログラムは，標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない． ただし，標準エラー出力にデバッグ情報等を出力することは許される．

コンパイル・実行の方法

作成したプログラムをテストするための，採点プログラムのサンプルが， コンテストサイトからダウンロードできるアーカイブの中に含まれている． このアーカイブには，提出しなければならないファイルのサンプルも含まれている．

採点プログラムのサンプルは 1 つのファイルからなる. そのファイルは grader.cpp である． 作成したプログラムをテストするには， これらのファイル grader.cpp, voltage.cpp, voltage.h を同じディレクトリに置き，次のようにコマンドを実行する．

g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp

なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．その場合，次のようにコマンドを実行する．

./compile.sh

コンパイルが成功すれば，grader という実行ファイルが生成される．

実際の採点プログラムは，採点プログラムのサンプルとは異なることに注意すること． 採点プログラムのサンプルは単一のプロセスとして起動する． このプログラムは，標準入力から入力を読み込み，標準出力に結果を出力する．

採点プログラムのサンプルの入力

採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む．

N M
A_0 B_0
\vdots
A_{M-1} B_{M-1}

採点プログラムのサンプルの出力

採点プログラムのサンプルは標準出力へ以下の情報を出力する (引用符は実際には出力されない)．

• 不正解 [3] ～ [12] のいずれかの場合，不正解の種類が "Wrong Answer [5]" のように出力される．
• そうでない場合，関数 query の呼び出し回数と，関数 solve の戻り値が "Accepted: 30 true" のように出力される． 採点プログラムのサンプルは，実際の採点プログラムと違って不正解 [1], [2] であるか，つまり関数 solve の戻り値が正しいかを判定しないことに注意せよ．

採点プログラムのサンプルは，不正解 [3] ～ [12] のいずれかの不正解の条件が満たされた時点で実行を終了する． 実行するプログラムが不正解 [3] ～ [12] のうち，複数の条件を満たした場合，表示される不正解の種類はそれらのうち 1 つのみである．

採点に関する注意

実際の採点プログラムは適応的 (adaptive) ではなく，やりとりの初めから固定された答えを持つ．

制約

• 2 \leqq N \leqq 500．
• 1 \leqq M \leqq 1\,000．
• 0 \leqq A_i \leqq N - 1 (0 \leqq i \leqq M - 1)．
• 0 \leqq B_i \leqq N - 1 (0 \leqq i \leqq M - 1)．
• A_i \neq B_i (0 \leqq i \leqq M - 1)．
• (A_i, B_i) \neq (A_j, B_j) かつ (A_i, B_i) \neq (B_j, A_j) (0 \leqq i < j \leqq M - 1)．
• N, M, A_i, B_i は整数である (0 \leqq i \leqq M - 1)．

小課題

1. (4 点) N = 2．
2. (16 点) N \leqq 100，M = N - 1，B_i = A_{i+1} (0 \leqq i \leqq N - 3)，N 個の値 A_0, A_1, \ldots ,A_{N-2}, B_{N-2} はすべて異なる．
3. (21 点) M = N - 1，B_i = A_{i+1} (0 \leqq i \leqq N - 3)，N 個の値 A_0, A_1, \ldots ,A_{N-2}, B_{N-2} はすべて異なる．
4. (24 点) N \leqq 100，A_i \neq A_j (0 \leqq i < j \leqq M - 1)．
5. (14 点) A_i \neq A_j (0 \leqq i < j \leqq M - 1)．
6. (11 点) N \leqq 100．
7. (10 点) 追加の制約はない．

やりとりの例

採点プログラムのサンプルが読み込む入力の例と，それに対応する関数の呼び出しの例を以下に示す．

入力例 1

5 6
0 2
2 1
0 3
3 2
3 4
4 1

1 回目の \texttt{query} の呼び出しにおける 2 回の電圧の設定と，電流が流れる電気抵抗は以下の通りである．

• 1 回目は節点 0, 1 を「低電圧」に，節点 2, 3, 4 を「高電圧」に設定する．このとき，電気抵抗 1, 5 に電流が流れる．
• 2 回目は節点 3, 4 を「低電圧」に，節点 0, 1, 2 を「高電圧」に設定する．このとき，電気抵抗 2 に電流が流れる．

1 回目の電圧の設定の方が電流が流れる電気抵抗の本数が多いため，戻り値は -1 である．

この入力例は小課題 6, 7 の制約を満たす．

コンテストサイトからダウンロードできるファイルのうち，sample-01-in.txt は入力例 1 に対応する． また，sample-02-in.txt は小課題 2, 3, 4, 5, 6, 7 の制約を満たし，sample-03-in.txt は小課題 4, 5, 6, 7 の制約を満たす．