JOI 股份有限公司的工廠裡有 $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 再次反轉方向，使其恢復原本的方向。
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，則沒有產品。 - 陣列
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 次。若超過，程式會被判為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{array}{c} N \\ A_0\ A_1\ \cdots\ A_{N-2} \\ B_0\ B_1\ \cdots\ B_{N-2} \\ C_0\ C_1\ \cdots\ C_{N-2} \end{array} $$
對於 $0 \le i \le N-2$，若輸送帶 $i$ 從桌子 $A_i$ 向桌子 $B_i$ 運送產品，則 $C_i=0$；否則 $C_i=1$。
範例評測程式的輸出格式
範例評測程式會向標準輸出輸出以下資訊（原文的引號僅用於說明）。
- 若程式被判為正確，會以
Accepted: 22的形式回報Query的呼叫次數。 - 若程式被判為任何類型的錯誤答案，範例評測程式會以
Wrong Answer [4]的形式輸出其類型。
若程式同時符合多種錯誤答案的條件，範例評測程式只會回報其中一種。
在範例評測程式中，對於放了產品的桌子，會從所有由該桌子向外運送產品的輸送帶中，以均勻隨機的方式選出運送產品的輸送帶。這個選擇由偽隨機數決定，不同次執行的結果不會改變。若要改變偽隨機數的種子，請以下列方式將一個整數作為第一個引數執行範例評測程式。
./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 的限制。