俄羅斯的許多地方在冬季會下雪。俄羅斯有 $N$ 座城市，編號為 $0$ 到 $N-1$。俄羅斯有 $N-1$ 條道路，編號為 $0$ 到 $N-2$。道路 $i$（$0\le i\le N-2$）雙向連接兩座不同的城市 $A_i,B_i$（$0\le A_i<B_i\le N-1$）。俄羅斯任意兩座不同的城市之間，都可以經由若干條道路互相往來。

每條道路的降雪狀況隨日期而變。在任何一天，每條道路不是正在下雪，就是沒有下雪。一天之內降雪狀況不會改變。

Anya 和 Boris 在俄羅斯的交通局工作。Anya 隸屬於管理道路資訊的部門，Boris 隸屬於回答市民問題的部門。市民的問題是：從俄羅斯首都城市 $0$ 移動到某座其他城市，至少必須經過幾條正在下雪的道路？Boris 通常會在收到問題後與 Anya 溝通，再回答市民。

這次，俄羅斯將舉辦為期 $Q$ 天的程式設計世界大賽。預計大賽期間通訊線路會壅塞，使 Anya 和 Boris 難以直接溝通。因此，他們決定採用下列方式溝通。

• Anya 在每天開始時收到當天的降雪資訊，並將資料傳送至中繼伺服器。
• Boris 收到市民的問題後，透過與中繼伺服器互動來回答問題。

不過，Anya 和 Boris 的溝通有以下限制。

• 中繼伺服器的容量是 $L=1\,000$ 位元。Anya 最多只能在中繼伺服器儲存 $L$ 位元的資訊。
• 中繼伺服器儲存的資料在每天開始時都會全部初始化為 $0$。
• Boris 每次與中繼伺服器互動，可以讀取指定的 $1$ 個位元。
• 為了回答每個問題，Boris 最多只能與中繼伺服器互動 20 次。

你與交通局長相識，因此受託設計 Anya 和 Boris 的策略。

任務

請撰寫實作 Anya 和 Boris 策略的程式，使他們能正確回答市民的問題。

實作細節

你必須提交兩個以相同程式語言撰寫的檔案。

第一個檔案名為 Anya.c 或 Anya.cpp。此檔案實作 Anya 的策略，必須實作以下兩個函式。程式必須引入 Anyalib.h。

void InitAnya(int N, int A[], int B[])

每個測試案例中，此函式只會被呼叫一次。

• 參數 $N$ 表示城市數量。
• 參數 A[] 和 B[] 各為長度 $N-1$ 的數列，表示道路的連接資訊。元素 A[i] 和 B[i]（$0\le i\le N-2$）為整數，表示道路 $i$ 雙向連接城市 A[i] 和 B[i]，且滿足 $0\le A[i]<B[i]\le N-1$。

void Anya(int C[])

此函式會在 InitAnya 被呼叫後被呼叫 $Q$ 次。它對應於每天開始、道路降雪資訊更新後，Anya 決定儲存在中繼伺服器中的位元序列。

• 參數 C[] 是長度 $N-1$ 的數列，表示道路的降雪資訊。元素 C[i]（$0\le i\le N-2$）是表示道路 $i$ 降雪資訊的整數 $0$ 或 $1$。若 $C[i]=1$，表示道路 $i$ 正在下雪；若 $C[i]=0$，表示道路 $i$ 沒有下雪。

在函式 Anya 中可以呼叫下列函式。

void Save(int place, int bit)

此函式表示 Anya 將位元儲存至中繼伺服器的操作。

• 參數 $place$ 表示寫入位元的位置，必須是 $0$ 到 $L-1$ 之間的整數。若以此範圍之外的值呼叫，會被判為答案錯誤 [1]。此外，每次呼叫 Anya 時，不能以相同的參數 $place$ 呼叫此函式兩次或以上。若以相同參數呼叫兩次，會被判為答案錯誤 [2]。
• 參數 $bit$ 是表示要寫入位元的整數，必須是 $0$ 或 $1$。若以其他值呼叫，會被判為答案錯誤 [3]。

呼叫 Save 後，中繼伺服器第 $place$ 個位元的內容會變成 $bit$。

若 Save 的呼叫被判為答案錯誤，程式會在該時刻結束。

每次呼叫 Anya 之前，中繼伺服器的所有位元一定都會初始化為 $0$。 換言之，沒有透過 Save 執行儲存操作的位置，在 Anya 結束時會是 $0$。

第二個檔案名為 Boris.c 或 Boris.cpp。此檔案實作 Boris 的策略，必須實作以下兩個函式。程式必須引入 Borislib.h。

void InitBoris(int N, int A[], int B[])

每個測試案例中，此函式只會被呼叫一次。

• 參數 $N$ 表示城市數量。
• 參數 A[] 和 B[] 各為長度 $N-1$ 的數列，表示道路的連接資訊。元素 A[i] 和 B[i]（$0\le i\le N-2$）為整數，表示道路 $i$ 雙向連接城市 A[i] 和 B[i]，且滿足 $0\le A[i]<B[i]\le N-1$。

int Boris(int city)

此函式會在 InitBoris 被呼叫後被呼叫若干次。它對應於 Boris 對市民問題採取的行動。

• 參數 $city$ 表示市民的問題，是 $1$ 到 $N-1$ 之間的整數。它表示市民詢問：從城市 $0$ 移動到城市 $city$，至少必須經過幾條正在下雪的道路？
• 函式 Boris 必須回傳一個 $0$ 到 $N-1$ 之間的整數，作為市民問題的答案。若回傳此範圍之外的整數，會被判為答案錯誤 [4]。若答案不正確，會被判為答案錯誤 [7]。

在函式 Boris 中可以呼叫下列函式。

int Ask(int place)

此函式表示 Boris 從中繼伺服器讀取位元的操作。

• 參數 $place$ 表示讀取位元的位置，必須是 $0$ 到 $L-1$ 之間的整數。若以此範圍之外的值呼叫，會被判為答案錯誤 [5]。

Ask 的回傳值是表示中繼伺服器第 $place$ 個位元內容的整數，為 $0$ 或 $1$。此外，每次呼叫 Boris 時，最多只能呼叫 Ask 20 次。若呼叫超過 20 次，會被判為答案錯誤 [6]。

若 Ask 的呼叫被判為答案錯誤，程式會在該時刻結束。

評分流程

評分依下列步驟進行。若被判為答案錯誤，程式會在該時刻結束。

1. 為了提供道路資訊，依序呼叫 InitAnya 和 InitBoris 各一次。

2. 對 $i=1,\ldots,Q$，依序執行以下操作。

   • (a) 呼叫 Anya 恰好一次。這對應於每天開始、道路降雪資訊更新後，Anya 決定儲存在中繼伺服器中的位元序列。
   • (b) 呼叫 Boris 共 $D_i$ 次。$D_i$ 是第 $i$ 天市民提問的次數。其中第 $j$ 次（$1\le j\le D_i$）呼叫的參數是 $R_{ij}$（$1\le R_{ij}\le N-1$）。若第 $j$ 次呼叫時 Boris 的回傳值，不等於從城市 $0$ 到城市 $R_{ij}$ 必須經過的下雪道路數量的最小值，則會被判為答案錯誤。

3. 若從未被判為答案錯誤，則判為正確。

重要注意事項

• 執行時間與記憶體用量的測量對象，是「評分流程」中的步驟 (1)、(2)。若答案正確，在步驟 (2) 中，Anya 總共會被呼叫 $Q$ 次，Boris 總共會被呼叫 $D_1+\cdots+D_Q$ 次。
• Anya 和 Boris 無法知道 $D_1,\ldots,D_Q$ 的值。
• 函式 Boris 不會獲得任何資訊來表示函式 Anya 在何時更新了中繼伺服器中儲存的資料。
• 你可以自由實作其他供內部使用的函式或宣告全域變數。不過，提交的兩份程式會與評分程式一起連結成一個執行檔，因此每個檔案內所有全域變數與內部函式（InitAnya、Anya、InitBoris、Boris 除外）都必須宣告為 static，以避免與其他檔案互相干擾。評分時，此程式會以 Anya 端與 Boris 端兩個行程執行，因此兩端無法共用程式中的全域變數。
• 你的提交不得以任何方式與標準輸入、標準輸出或其他檔案互動。

編譯與執行方式

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

範例評分程式由一個檔案組成，檔案名為 grader.c 或 grader.cpp。若你所寫的程式為 Anya.c 與 Boris.c，或 Anya.cpp 與 Boris.cpp，請以下列方式執行指令來測試程式。

• 使用 C 時：

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• 使用 C++ 時：

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

若編譯成功，會產生名為 grader 的執行檔。

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

範例評分程式概要

範例評分程式依照「評分流程」呼叫函式。

請注意，以下部分與實際評分程式的行為不同。

• 範例評分程式不會進行答案錯誤 [7] 的判定，而是輸出每個問題對應的 Boris 回傳值。

範例評分程式的輸入格式

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

• 第一行包含整數 $N$，表示城市數量為 $N$。
• 接下來 $N-1$ 行中的第 $i+1$ 行（$0\le i\le N-2$）包含以空白分隔的整數 $A_i,B_i$，表示道路 $i$ 雙向連接城市 $A_i$ 和城市 $B_i$。
• 下一行包含整數 $Q$，表示大賽舉辦 $Q$ 天。
• 接下來 $Q$ 行中的第 $i$ 行（$1\le i\le Q$）包含長度 $N-1$ 的字串 $S_i$ 和 $D_i+1$ 個整數，以空白分隔。$S_i$ 表示第 $i$ 天的降雪資訊；若 $S_i$ 從左起第 $j+1$ 個字元（$0\le j\le N-2$）是 1，表示道路 $j$ 正在下雪；若是 0，表示道路 $j$ 沒有下雪。接下來 $D_i+1$ 個整數中的第一個是 $D_i$，其後的 $D_i$ 個整數為 $R_{i1},\ldots,R_{iD_i}$。這表示第 $i$ 天的第 $j$ 個問題（$1\le j\le D_i$）詢問從城市 $0$ 到城市 $R_{ij}$ 必須經過的下雪道路數量的最小值。

範例評分程式的輸出格式

範例評分程式向標準輸出輸出下列資訊（實際不會輸出引號）。

• 若程式執行期間被判為答案錯誤，會輸出如 Wrong Answer [1] 的錯誤種類，並結束執行。
• 若第 $i$ 次（$1\le i\le Q$）呼叫 Anya 之後的 $D_i$ 次 Boris 呼叫都未被判為答案錯誤，便在此時於一行中輸出 $D_i$ 個以空白分隔的整數。其中第 $j$ 個（$1\le j\le D_i$）整數是 $\operatorname{Boris}(R_{ij})$ 的回傳值。

若執行的程式同時符合多種答案錯誤的條件，只會顯示其中一種錯誤。

資料範圍

所有輸入資料都滿足以下條件。

• $2\le N\le 500$。
• $1\le Q\le 500$。
• $0\le A_i<B_i\le N-1$（$0\le i\le N-2$）。
• $1\le D_j$（$1\le j\le Q$）。
• $D_1+\cdots+D_Q\le 500$。
• 任意兩座不同的城市之間，都可以經由若干條道路互相往來。

子任務

子任務 1［15 分］

• 滿足 $N\le 20$。

子任務 2［5 分］

• 滿足 $N\le 100$。

子任務 3［35 分］

滿足以下條件。

• $A_i=i$（$0\le i\le N-2$）。
• $B_i=i+1$（$0\le i\le N-2$）。

子任務 4［45 分］

沒有額外限制。

互動範例

以下為範例評分程式讀取的輸入範例，以及相對應的函式呼叫範例。

輸入格式 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

函式呼叫範例

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

此時，傳入 InitAnya(...)、InitBoris(...)，以及第一次與第二次 Anya(...) 的參數分別如下。