あなたは Just Ordinary Inventions 社を知っているだろうか? この会社の業務は「ただ平凡な発明（単なる平凡な発明）」をすることである．

JOI 君は，Just Ordinary Inventions 社で開発された最新のゲームで遊んでいる．

このゲームは，いくつかの部屋といくつかの道からなるダンジョンを探索するゲームである．道はダンジョン内の異なる 2 つの部屋を結んでおり，双方向に移動可能である．どの異なる 2 つの部屋についても，それらを結ぶ道は高々1 本しかなく，両端が同じ部屋であるような道は存在しない．また，ダンジョンのどの 2 つの部屋の間も，何本かの道を使うことで互いに移動できることがわかっている．各部屋同士は非常によく似ており，同じ本数の道が出ている部屋同士は，部屋の様子を見るだけではまったく区別ができない．

このゲームでは，攻略を助けるために各部屋に目印と台座が用意されている．部屋から出ている道は，目印を基準として 1 本目，2 本目，$\ldots$ と数えることができる．ゲーム中にダンジョンの構造が変化することはない．したがって，同じ部屋から同じ番号の道を使って移動すると，いつも同じ部屋にたどり着く．台座にはプレイヤーが色を変更することができる宝石が 1 個飾られている．宝石の色は色 $1$，色 $2$，$\ldots$，色 $X$ のいずれかであり，ゲーム開始時の各部屋の宝石の色は色 $1$ である．宝石の色はプレイヤーが操作しない限り変更されることはない．

JOI 君は，もしこのダンジョンの構造，すなわちダンジョンの部屋同士がどのように道で結ばれているかがわかれば，このゲームは簡単に攻略できてしまうことに気づいた．しかし，JOI 君がいろいろ試してもダンジョンの構造を決定することはできなかった．そこで，あなたは JOI 君に代わってダンジョンの構造を決定するプログラムを書くことにした．

課題

ダンジョンを探索して，ダンジョンの構造を決定するプログラムを作成せよ．しかし，JOI 君はダンジョンの構造を完全に明かされることを望まなかったため，プログラムはダンジョンの構造を直接答えるのではなく，$1$ 以上 $R$ 以下の各整数 $i$ に対して「最小でちょうど $i$ 本の道を使うことで移動できる 2 つの部屋の組は何個あるか」の値（部屋の順序を入れ替えたものは同じ組とみなす）を解答しなければならない．

ダンジョンを探索するために，あなたには次の行動を行うためのライブラリが提供される．

• 現在いる部屋から，何本の道が出ているかを知る．
• 現在いる部屋の台座に飾られている宝石の色を知る．
• 現在いる部屋の台座に飾られている宝石の色を，指定した色にする（現在の色と同じ色を指定することもできる）．その後，部屋から出ている道を 1 本選び，その道を使って他の部屋へ移動する．
• 最後に使った道が，現在いる部屋から出ている道のうち何本目かを知る．

実装の詳細

あなたは，JOI 君に解答する方法を実装した 1 個のプログラムを書かねばならない．プログラムは dungeon2.h をインクルードすること．

プログラムは，以下のルーチンを実装しなければならない．

• void Inspect(int R)

このルーチンは，最初に 1 回だけ呼び出される．

• 引数 R は，$1$ 以上 $R$ 以下の各整数 $i$ に対して「最小でちょうど $i$ 本の道を使うことで移動できる 2 つの部屋の組は何個あるか」の値（部屋の順序を入れ替えたものは同じ組とみなす）を解答しなければならないことを表す．

また，次のルーチンを呼び出し，質問に答えなければならない．

• void Answer(int D, int A)

• 引数 D，A は，この呼び出しにおいて，「最小でちょうど $D$ 本の道を使うことで移動できる 2 つの部屋の組は $A$ 個ある」ことを解答することを表す．

ただし，Answer の呼び出しは以下の条件を満たすこと．

• D は $1$ 以上 $R$ 以下の整数でなければならない．これを満たさない場合，不正解 [1] となる．
• Answer を同じ引数 D で 2 回以上呼び出してはならない．これを満たさない場合，不正解 [2] となる．
• Answer はちょうど $R$ 回呼び出さなければならない．これを満たさない場合，不正解 [3] となる．
• A は最小でちょうど $D$ 本の道を使うことで移動できる 2 つの部屋の組の個数でなければならない．これを満たさない場合，不正解 [4] となる．

Answer の呼び出しが不正解と判定された場合，それ以降のプログラムは実行されるとは限らない．

これに加え，プログラム中では，以下のルーチンを呼び出すことができる．

• void Move(int I, int C)

• 引数 I は，プレイヤーが移動するために選ぶ道の番号である．この呼び出しの直後，プレイヤーは現在いる部屋から出ている $I$ 本目の道を使って他の部屋まで移動する．

• 引数 C は，部屋の移動を行う前に，現在いる部屋の台座に飾られている宝石の色を色 $C$ にすることを表す．

ただし，Move の呼び出しは以下の条件を満たすこと．

• 引数 I は，プレイヤーが現在いる部屋から出ている道の本数を $K$ として，$1$ 以上 $K$ 以下の整数でなければならない．これを満たさない場合，不正解 [5] となる．
• 引数 C は，宝石の色の種類が $X$ 種類として，$1$ 以上 $X$ 以下の整数でなければならない．$X$ の値は小課題ごとに定まっている．これを満たさない場合，不正解 [6] となる．
• Move を $1\,500\,000$ 回より多く呼び出してはならない．呼び出した場合，不正解 [7] となる．

• int NumberOfRoads()

• この関数は，プレイヤーが現在いる部屋から出ている道の本数を返す．

• int LastRoad()

• この関数は，プレイヤーが最後に使った道が，現在いる部屋から出ている道のうち何本目の道であるかを返す．ただし，Move を一度も呼び出す前にこの関数が呼び出された場合は，$-1$ を返す．

• int Color()

• この関数は，プレイヤーが現在いる部屋の台座に飾られている宝石の色を返す．

ルーチン Inspect が呼び出された後，答えの判定が行われる．

内部での使用のために他のルーチンを実装したり，グローバル変数を宣言するのは自由である．ただし，あなたの提出は標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．

コンパイル・実行の方法

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

採点プログラムのサンプルは 1 つのファイルからなる．そのファイルは grader.c または grader.cpp である．作成したプログラムをテストするには，次のようにコマンドを実行する．

• C の場合

gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• C++ の場合

g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

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

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

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

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

• 1 行目には，整数 $N,X,R$ が空白を区切りとして書かれている．これは，ダンジョンに部屋 $1$，部屋 $2$，$\ldots$，部屋 $N$ の $N$ 個の部屋があり，宝石の色が $X$ 種類あり，プログラムが解答すべき値が $R$ 個であることを表す．
• 続く $2N$ 行のうちの $2i-1$ 行目（$1\le i\le N$）には，整数 $D_i$ が書かれており，部屋 $i$ から $D_i$ 本の道が出ていることを表す．$2i$ 行目（$1\le i\le N$）には，$D_i$ 個の整数 $T_{i1},T_{i2},\ldots,T_{iD_i}$ が空白を区切りとして書かれている．これは，部屋 $i$ から出ている $j$（$1\le j\le D_i$）本目の道を使って移動すると部屋 $T_{ij}$ にたどり着くことを表す．
• 続く $R$ 行のうちの $j$ 行目（$1\le j\le R$）には，整数 $A_j$ が書かれている．これは，最小でちょうど $j$ 本の道を使うことで移動できる 2 つの部屋の組が $A_j$ 個あることを表す．つまり，各 $j$（$1\le j\le R$）に対して，Answer の引数 D として $j$，引数 A として $A_j$ を与えて呼び出した場合に採点プログラムのサンプルが正解と判定し，それ以外の場合に不正解と判定することを表す．

採点プログラムのサンプルは，プレイヤーの初期位置を部屋 $1$ として，あなたの作成したルーチンを呼び出す．

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

プログラムの実行が正常に終了した場合，採点プログラムのサンプルは標準出力へ以下の情報を 1 行で出力する（引用符は実際には出力されない）．

• 正解の場合，関数 Move を呼び出した回数が Accepted : #move = 8 のように出力される．
• 不正解の場合，不正解の種類が Wrong Answer [1] のように出力される．

制約

すべての入力データは以下の条件を満たす．$N,D_i,T_{ij}$ の意味については「採点プログラムのサンプルの入力」の項目を参照せよ．

• $2\le N\le 200$．
• $3\le X\le 100$．
• $1\le R\le 200$．
• $1\le D_i\le N-1$（$1\le i\le N$）．
• $1\le T_{ij}\le N$ かつ $T_{ij}\ne i$（$1\le i\le N$，$1\le j\le D_i$）．
• $T_{i1},T_{i2},\ldots,T_{iD_i}$（$1\le i\le N$）は互いに異なる．
• 各 $i,j$（$1\le i\le N$，$1\le j\le D_i$）に対し，$T_{T_{ij}k}=i$ を満たす $k$（$1\le k\le D_{T_{ij}}$）が存在する．
• どの 2 つの部屋の間も，何本かの道を使うことで互いに移動できる．

小課題

以下では，入力データにおけるダンジョンの部屋の数を $N$，道の本数を $M$ とする．

小課題 1 [17 点]

以下の条件を満たす．

• $N\le 50$．
• $M\le 100$．
• $X=100$．

小課題 2 [27 点]

以下の条件を満たす．

• $N\le 50$．
• $M\le 100$．
• $X=3$．

小課題 3 [56 点]

• $X=3$ を満たす．

この小課題では，以下に従い得点が決定される．

• この小課題の全てのテストケースにおける，次の値の最大値を $L$ とおく．

  • Move の呼び出し回数を $C$ としたときの，$\dfrac{C}{M}$．

• このとき，この小課題の得点は，

  • $L\le14$ のとき，56 点．
  • $14<L\le32$ のとき，$\lfloor70-L\rfloor$ 点．
  • $32<L\le64$ のとき，$\left\lfloor54-\dfrac{L}{2}\right\rfloor$ 点．
  • $64<L$ のとき，0 点．

ここで，$\lfloor x\rfloor$ は $x$ を超えない最大の整数を表す．

採点システム上では，プログラムが正しく終了し，正解と判定された場合には詳細の欄に Accepted と表示される．ただし，小課題 3 の採点で，上の $C,M$ が $64<\dfrac{C}{M}$ となるテストケースについては，結果の欄には不正解と表示されるので注意せよ．

やりとりの例

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

入力 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

ルーチンの呼び出しの例

この例での関数の呼び出しは，必ずしも意味のある呼び出しとは限らないことに注意せよ．