你知道 Just Ordinary Inventions 公司嗎？這家公司的業務是進行「只是平凡的發明（just ordinary inventions）」。

JOI 君正在玩 Just Ordinary Inventions 公司開發的最新遊戲。

這是一款探索地下城的遊戲，地下城由若干房間與若干道路組成。每條道路連接地下城內兩個不同的房間，可以雙向通行。任意兩個不同房間之間至多只有一條道路，也不存在兩端為同一房間的道路。此外，已知地下城內任意兩個房間都可以透過若干條道路互相到達。各房間非常相似，對於連出道路數量相同的房間，僅觀察房間的樣子完全無法區分。

遊戲為了協助攻略，在每個房間中準備了標記與基座。以標記為基準，可以將房間連出的道路依序編為第 $1$ 條、第 $2$ 條、$\ldots$。遊戲過程中地下城的結構不會改變。因此，從同一個房間沿相同編號的道路移動，總是會抵達同一個房間。基座上裝飾著一顆玩家可以改變顏色的寶石。寶石的顏色為顏色 $1$、顏色 $2$、$\ldots$、顏色 $X$ 其中之一，遊戲開始時每個房間的寶石都是顏色 $1$。除非玩家進行操作，否則寶石的顏色不會改變。

JOI 君發現，如果知道地下城的結構，也就是房間之間如何以道路相連，就能輕鬆攻略這款遊戲。然而，JOI 君嘗試各種方法後，仍無法確定地下城的結構。因此，你決定代替 JOI 君編寫確定地下城結構的程式。

任務

請編寫一個探索地下城並確定其結構的程式。不過，JOI 君不希望地下城的結構被完全揭露，因此程式不能直接回答地下城的結構，而必須對每個 $1$ 以上、$R$ 以下的整數 $i$，回答「最少恰好需要經過 $i$ 條道路才能互相到達的房間對有多少組」（交換兩個房間的順序視為同一組）。

為了探索地下城，會提供可執行下列行動的函式庫。

• 得知目前所在房間連出多少條道路。
• 得知目前所在房間基座上寶石的顏色。
• 將目前所在房間基座上寶石的顏色改成指定顏色（也可以指定與目前相同的顏色）。接著，選擇一條從該房間連出的道路，沿該道路移動到另一個房間。
• 得知最後使用的道路是目前所在房間連出道路中的第幾條。

實作細節

你必須編寫一個程式，實作向 JOI 君回答的方法。程式必須引入 dungeon2.h。

程式必須實作以下函式。

void Inspect(int R)

此函式只會在一開始呼叫一次。

• 參數 $R$ 表示，對每個 $1$ 以上、$R$ 以下的整數 $i$，你必須回答「最少恰好需要經過 $i$ 條道路才能互相到達的房間對有多少組」（交換兩個房間的順序視為同一組）。

此外，必須呼叫下列函式來回答問題。

void Answer(int D, int A)

• 參數 $D,A$ 表示此次呼叫回答「最少恰好需要經過 $D$ 條道路才能互相到達的房間對有 $A$ 組」。

不過，對 Answer 的呼叫必須滿足下列條件。

• $D$ 必須為 $1$ 以上、$R$ 以下的整數。否則會被判定為答案錯誤 [1]。
• 不得以相同的參數 $D$ 呼叫 Answer 兩次以上。否則會被判定為答案錯誤 [2]。
• 必須恰好呼叫 Answer 共 $R$ 次。否則會被判定為答案錯誤 [3]。
• $A$ 必須等於最少恰好需要經過 $D$ 條道路才能互相到達的房間對數。否則會被判定為答案錯誤 [4]。

若對 Answer 的呼叫被判定為答案錯誤，則不保證程式之後的部分仍會執行。

除此之外，程式可以呼叫下列函式。

void Move(int I, int C)

• 參數 $I$ 是玩家選擇用來移動的道路編號。此次呼叫之後，玩家會立刻沿目前所在房間連出的第 $I$ 條道路移動到另一個房間。
• 參數 $C$ 表示，在移動房間之前，先將目前所在房間基座上寶石的顏色設為顏色 $C$。

不過，對 Move 的呼叫必須滿足下列條件。

• 令玩家目前所在房間連出的道路數為 $K$，參數 $I$ 必須是 $1$ 以上、$K$ 以下的整數。否則會被判定為答案錯誤 [5]。
• 令寶石的顏色種類數為 $X$，參數 $C$ 必須是 $1$ 以上、$X$ 以下的整數。$X$ 的值由各子任務決定。否則會被判定為答案錯誤 [6]。
• 不得呼叫 Move 超過 $1\,500\,000$ 次。否則會被判定為答案錯誤 [7]。

int NumberOfRoads()

• 此函式回傳玩家目前所在房間連出的道路數。

int LastRoad()

• 此函式回傳玩家最後使用的道路是目前所在房間連出道路中的第幾條。不過，若在尚未呼叫過 Move 時呼叫此函式，則回傳 $-1$。

int Color()

• 此函式回傳玩家目前所在房間基座上寶石的顏色。

函式 Inspect 被呼叫後，會進行答案判定。

你可以自由實作供內部使用的其他函式，或宣告全域變數。不過，提交的程式不得以任何方式與標準輸入、標準輸出或其他檔案交換資訊。

編譯與執行方式

可從競賽網站下載的壓縮檔中，包含用來測試你所寫程式的範例評測程式。壓縮檔也包含必須提交的檔案的範例。

範例評測程式由一個檔案組成，即 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 的執行檔。

請注意，實際評測程式與範例評測程式不同。範例評測程式以單一行程啟動，從標準輸入讀取輸入，並將結果寫入標準輸出。

範例評測程式的輸入格式

範例評測程式會從標準輸入讀取下列資料。

• 第一行包含以空格分隔的整數 $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$ 條道路才能互相到達的房間對有 $A_j$ 組。也就是說，對每個 $j$（$1 \le j \le R$），以 $j$ 作為 Answer 的參數 $D$，並以 $A_j$ 作為參數 $A$ 呼叫時，範例評測程式會判定為正確；其他情況則判定為答案錯誤。

範例評測程式會將玩家的初始位置設為房間 $1$，並呼叫你所寫的函式。

範例評測程式的輸出格式

程式正常結束時，範例評測程式會向標準輸出以一行輸出下列資訊（實際上不會輸出引號）。

• 若答案正確，會以 Accepted : #move = 8 這樣的形式輸出函式 Move 的呼叫次數。
• 若答案錯誤，會以 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$），存在 $k$（$1 \le k \le D_{T_{ij}}$）使得 $T_{T_{ij}k}=i$。
• 任意兩個房間都能透過若干條道路互相到達。

子任務

以下令輸入資料中的地下城房間數為 $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 \le 14$，得 $56$ 分。
  • 若 $14 < L \le 32$，得 $\lfloor 70-L \rfloor$ 分。
  • 若 $32 < L \le 64$，得 $\left\lfloor 54-\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

函式呼叫範例

請注意，此範例中的函式呼叫不一定都有意義。