俄羅斯好多地方冬天都會落雪。俄羅斯有 $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 收到市民問題之後，透過同中繼伺服器溝通嚟作答。

不過，佢哋嘅溝通有以下限制：

• 中繼伺服器容量係 $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\texttt{A[i]}<\texttt{B[i]}\le N-1$。

• void Anya(int C[])

喺 InitAnya 被呼叫之後，呢個函數會被呼叫 $Q$ 次。佢對應每日開始、道路降雪資訊更新之後，Anya 決定儲存喺中繼伺服器嘅位元序列嘅行為。

• 參數 C[] 係長度 $N-1$ 嘅數列，表示道路降雪資訊。元素 C[i]（$0\le i\le N-2$）係 $0$ 或 $1$，表示道路 $i$ 嘅降雪情況：C[i] = 1 表示有落雪，C[i] = 0 表示冇落雪。

喺 Anya 入面可以呼叫以下函數。

• void Save(int place, int bit)

呢個函數表示 Anya 將一個位元儲存到中繼伺服器嘅操作。

• 參數 place 表示寫入位置，必須係 $0$ 至 $L-1$ 之間嘅整數。超出範圍會判為 Wrong Answer [1]。每次呼叫 Anya 期間，唔可以用同一個 place 呼叫兩次或以上；重複呼叫會判為 Wrong Answer [2]。
• 參數 bit 表示寫入嘅位元，必須係整數 $0$ 或 $1$。用其他值呼叫會判為 Wrong Answer [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\texttt{A[i]}<\texttt{B[i]}\le N-1$。

• int Boris(int city)

喺 InitBoris 被呼叫之後，呢個函數會被呼叫若干次，對應 Boris 回答市民問題嘅行為。

• 參數 city 表示市民嘅問題，係 $1$ 至 $N-1$ 之間嘅整數。問題係由城市 $0$ 去到城市 city，最少要經過幾多條落緊雪嘅道路。
• Boris 必須回傳一個 $0$ 至 $N-1$ 之間嘅整數，作為問題答案。超出範圍會判為 Wrong Answer [4]；答案唔正確會判為 Wrong Answer [7]。

喺 Boris 入面可以呼叫以下函數。

• int Ask(int place)

呢個函數表示 Boris 從中繼伺服器讀取一個位元嘅操作。

• 參數 place 表示讀取位置，必須係 $0$ 至 $L-1$ 之間嘅整數。超出範圍會判為 Wrong Answer [5]。

Ask 嘅回傳值係中繼伺服器第 place 個位元嘅內容，即整數 $0$ 或 $1$。每次呼叫 Boris 期間最多只可以呼叫 Ask 20 次；超過 20 次會判為 Wrong Answer [6]。

如果 Ask 嘅呼叫被判為錯誤，程式會即時終止。

評測流程

評測按以下步驟進行。如果判為錯誤，程式會即時終止。

1. 依次各呼叫 InitAnya 同 InitBoris 一次，提供道路資訊。

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

   • 呼叫 Anya 一次，對應每日開始、道路降雪資訊更新之後，Anya 決定儲存嘅位元序列。
   • 呼叫 Boris $D_i$ 次，$D_i$ 係第 $i$ 日市民問題數量。第 $j$ 次呼叫（$1\le j\le D_i$）嘅參數係 $R_{ij}$（$1\le R_{ij}\le N-1$）。如果回傳值唔等於由城市 $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 嘅執行檔。

請注意，真正評測程式同樣例評測程式唔同。樣例評測程式用單一程序執行，由標準輸入讀資料，向標準輸出寫結果。

樣例評測程式概覽

樣例評測程式會按照「評測流程」呼叫函數。

請注意，以下行為同真正評測程式唔同：

• 樣例評測程式唔會判定 Wrong Answer [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$ 日嘅降雪資訊：由左數第 $j+1$ 個字元（$0\le j\le N-2$）係 1 就表示道路 $j$ 有落雪，係 0 就表示冇落雪。之後 $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$）就係 函數 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(...) 嘅參數分別如下。