JOI Co., Ltd. 嘅工廠有 $N$ 張枱，編號由 $0$ 到 $N-1$。工廠有 $N-1$ 條輸送帶，編號由 $0$ 到 $N-2$。輸送帶 $i$ ($0\le i\le N-2$) 連接枱 $A_i$ 同枱 $B_i$，將產品由其中一張枱運去另一張枱。不過，我哋睇唔到輸送方向。如果忽略輸送帶嘅方向，任何兩張枱都可以透過若干條輸送帶互相連通。
IOI-kun 係工廠主管。佢唔記得咗每條輸送帶嘅輸送方向，所以會重複執行以下一連串操作。
- 揀若干條輸送帶，將佢哋嘅輸送方向反轉。
- 揀若干張枱，喺每張揀中嘅枱上放一件產品。
對每張放咗產品嘅枱，以下其中一種情況會同時發生。
- 如果冇輸送帶由呢張枱向外輸送產品，就乜都唔會發生。
- 如果有輸送帶由呢張枱向外輸送產品，枱上嘅產品就會由其中一條輸送帶運走。產品會停喺嗰條輸送帶嘅目的地，之後唔會再移動。
IOI-kun 檢查每張枱上係咪有至少一件產品。如果有，就將嗰張枱上嘅所有產品拎走。
- 將操作 1 入面反轉過方向嘅每條輸送帶再反轉一次，恢復原本方向。
IOI-kun 想透過執行以上整套操作最多 30 次，確定每條輸送帶嘅原本方向。
請寫一個程式，畀定每條輸送帶連接嘅枱嘅資料，實作 IOI-kun 嘅策略，透過執行以上整套操作最多 30 次，確定每條輸送帶嘅原本方向。
實作細節
你需要提交一個檔案。
檔案名係 conveyor.cpp，需要實作以下函式。程式要用預處理指令 #include 引入 conveyor.h。
喺 conveyor.cpp 入面，要實作以下函式。
void Solve(int N, std::vector<int> A, std::vector<int> B)每組測試資料只會呼叫呢個函式一次。
- 參數
N係枱嘅數目 $N$。 - 參數
A、B係長度為 $N-1$ 嘅陣列，描述輸送帶連接嘅枱。
- 參數
你嘅程式可以呼叫以下函式。
std::vector<int> Query(std::vector<int> x, std::vector<int> y)IOI-kun 透過呢個函式喺工廠執行操作。
- 參數
x係長度為 $N-1$ 嘅陣列。對 $0\le i\le N-2$，如果 $x[i]=1$，IOI-kun 就反轉輸送帶 $i$ 嘅方向；如果 $x[i]=0$，就唔反轉。 - 參數
y係長度為 $N$ 嘅陣列。對 $0\le j\le N-1$，如果 $y[j]=1$，IOI-kun 就喺枱 $j$ 上放一件產品；如果 $y[j]=0$，就唔放。 - 設呢個函式嘅回傳值係
z，佢係長度為 $N$ 嘅陣列。對 $0\le j\le N-1$，如果 $z[j]=1$，枱 $j$ 上就有至少一件產品；如果 $z[j]=0$，枱 $j$ 上就冇產品。 - 陣列
x嘅長度必須等於 $N-1$。唔符合就會判為 Wrong Answer [1]。 - 陣列
x嘅每個元素都必須係0或1。唔符合就會判為 Wrong Answer [2]。 - 陣列
y嘅長度必須等於 $N$。唔符合就會判為 Wrong Answer [3]。 - 陣列
y嘅每個元素都必須係0或1。唔符合就會判為 Wrong Answer [4]。 Query唔可以呼叫超過 30 次。如果超過 30 次，就會判為 Wrong Answer [5]。
- 參數
void Answer(std::vector<int> a)IOI-kun 透過呢個函式報告每條輸送帶嘅原本方向。
- 參數
a係長度為 $N-1$ 嘅陣列。對 $0\le i\le N-2$，如果 $a[i]=0$，輸送帶 $i$ 將產品由 $A_i$ 運去 $B_i$；如果 $a[i]=1$，就由 $B_i$ 運去 $A_i$。 - 陣列
a嘅長度必須等於 $N-1$。唔符合就會判為 Wrong Answer [6]。 - 陣列
a嘅每個元素都必須係0或1。唔符合就會判為 Wrong Answer [7]。 - 如果 IOI-kun 報告咗任何一條輸送帶嘅錯誤方向，就會判為 Wrong Answer [8]。
Answer必須恰好呼叫一次。如果呼叫多過一次，就會判為 Wrong Answer [9]。當Solve結束時，如果冇呼叫過Answer，就會判為 Wrong Answer [10]。
- 參數
重要事項
- 程式可以實作其他供內部使用嘅函式，亦可以使用全域變數。
- 程式唔可以使用標準輸入同標準輸出，亦唔可以用任何方式同其他檔案通訊。不過，程式可以向標準錯誤輸出除錯資訊。
編譯同測試
你可以喺比賽網頁下載一個壓縮檔，入面有用嚟測試程式嘅範例評測程式，亦有你嘅程式嘅範例原始碼檔案。
範例評測程式係 grader.cpp。要測試程式，請將 grader.cpp、conveyor.cpp 同 conveyor.h 放喺同一個目錄，再執行以下指令編譯。你亦可以改為執行壓縮檔入面嘅 compile.sh。
g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp
編譯成功後，就會產生可執行檔 grader。
留意，正式評測程式同範例評測程式唔同。範例評測程式會以單一行程執行，從標準輸入讀入資料，並向標準輸出寫出結果。
範例評測程式嘅輸入格式
範例評測程式會從標準輸入讀入以下資料。
$$ \begin{gathered} N\\ A_0\quad A_1\quad\cdots\quad A_{N-2}\\ B_0\quad B_1\quad\cdots\quad B_{N-2}\\ C_0\quad C_1\quad\cdots\quad C_{N-2} \end{gathered} $$
對 $0\le i\le N-2$，如果輸送帶 $i$ 將產品由枱 $A_i$ 運去枱 $B_i$，就有 $C_i=0$；否則 $C_i=1$。
範例評測程式嘅輸出格式
範例評測程式會向標準輸出寫出以下資訊（引號只為咗說明）。
- 如果程式被判為正確，就會用
Accepted: 22呢個格式報告Query嘅呼叫次數。 - 如果程式被判為任何類型嘅 Wrong Answer，範例評測程式就會用
Wrong Answer [4]呢個格式寫出錯誤類型。
如果程式符合多種 Wrong Answer 類型，範例評測程式只會報告其中一種。
喺範例評測程式入面，對於放咗產品嘅枱，產品會喺由嗰張枱向外輸送嘅輸送帶之中，均勻隨機揀一條去運送。選擇由偽隨機數決定，唔同次執行嘅結果都唔會改變。要改變偽隨機數嘅種子，可以用以下方式提供第一個整數參數執行範例評測程式。
./grader 2023
評測注意事項
部分測試資料嘅正式評測程式係自適應嘅。即係評測程式一開始唔會有固定答案，而係根據之前 Query 嘅呼叫作出回應。保證至少有一個答案，同評測程式所有回應都唔矛盾。
數據範圍
所有輸入資料都符合以下條件。
- $0\le A_i\le N-1$ ($0\le i\le N-2$)。
- $0\le B_i\le N-1$ ($0\le i\le N-2$)。
- 如果忽略輸送帶嘅方向，任何兩張枱都可以透過若干條輸送帶互相連通。
子任務
- (1 分) $N=2$。
- (14 分) $N=30$。
- (10 分) $N=100\,000$，$A_i=i$ ($0\le i\le N-2$)，$B_i=i+1$ ($0\le i\le N-2$)。
- (75 分) $N=100\,000$。
樣例
以下係範例評測程式嘅一份輸入，同埋對應嘅函式呼叫。
輸入格式 1
3 0 2 2 1 1 0
範例函式呼叫
| 函式呼叫 | 函式呼叫 | 回傳值 |
|---|---|---|
Solve(3, [0, 2], [2, 1]) |
||
Query([0, 0], [0, 0, 1]) |
[1, 0, 0] |
|
Query([1, 0], [1, 0, 1]) |
[0, 1, 1] |
|
Query([1, 1], [0, 0, 1]) |
[0, 0, 1] |
|
Query([0, 1], [1, 1, 1]) |
[1, 0, 1] |
|
Answer([1, 0]) |
說明
第一次呼叫 Query 時，除咗 [1, 0, 0]，另一個可能嘅回傳值係 [0, 1, 0]。
第二次呼叫 Query 時，枱 0 上嘅產品會經輸送帶 0 運去枱 2，然後停低。留意，呢件產品唔會再經輸送帶 1 運去枱 1。
留意，呢份樣例輸入唔符合任何子任務嘅限制。
喺比賽網頁可以取得嘅檔案之中，sample-02.txt 符合子任務 1 嘅限制，而 sample-03.txt 符合子任務 2 嘅限制。