有 $N$ 座居住著河狸的島嶼，編號從 $0$ 到 $N-1$。這些島嶼由 $N-1$ 座雙向橋樑連接。沿著橋樑可以往來任意兩座島嶼。每座島嶼直接相連的橋樑最多有 $18$ 座。每座島嶼都住著一隻河狸。

有時，一些河狸會聚集在某座島嶼開會。恰好有三隻河狸開會時，牠們會聚集在以下島嶼：

使這三隻河狸為了聚集而經過的橋樑總數最少的島嶼（這樣的島嶼唯一存在）。

注意，這座島嶼可能就是這三隻河狸中的某一隻居住的島嶼。

你對這 $N$ 座島嶼如何由橋樑連接感到好奇。你無法直接前往島嶼查看，因此打算向河狸發出一些指令。一條指令如下：

• 你指定三座島嶼 $u,v,w$（$0\le u\le N-1$、$0\le v\le N-1$、$0\le w\le N-1$、$u\ne v$、$u\ne w$、$v\ne w$），讓住在島嶼 $u,v,w$ 的河狸開會。
• 接著，你便能得知這三隻河狸聚集在哪座島嶼。

你希望用少量指令確定島嶼的連接方式。

請撰寫一個程式，給定島嶼數量，透過與河狸互動，確定島嶼的連接方式。

實作細節

你需要提交一個檔案。

檔案名稱為 meetings.cpp。它應實作下列函式，且程式應引入 meetings.h。

• void Solve(int N)

每筆測試資料恰好呼叫此函式一次。

• 參數 N 表示島嶼數量 $N$。

你的程式可以呼叫下列函式。

• int Query(int u, int v, int w)

給定你指定的三座島嶼的編號，此函式回傳住在這些島嶼上的河狸聚集開會的島嶼編號。

• 你透過參數 u、v、w 分別指定三座島嶼的編號 $u,v,w$。它們必須滿足 $0\le u\le N-1$、$0\le v\le N-1$、$0\le w\le N-1$、$u\ne v$、$u\ne w$ 且 $v\ne w$。否則，你的程式會被判定為 Wrong Answer [1]。

• 呼叫函式 Query 的次數不得超過 $100\,000$ 次。否則，你的程式會被判定為 Wrong Answer [2]。

• void Bridge(int u, int v)

你使用此函式回答島嶼如何由橋樑連接。

• 參數 u 和 v 表示島嶼 $u$ 和 $v$ 之間有一座直接連接的橋樑。
• 如果不滿足 $0\le u<v\le N-1$，你的程式會被判定為 Wrong Answer [3]。
• 如果島嶼 $u$ 和 $v$ 之間沒有直接連接的橋樑，你的程式會被判定為 Wrong Answer [4]。
• 如果以相同的參數 u 和 v 多次呼叫函式 Bridge，你的程式會被判定為 Wrong Answer [5]。
• 由於共有 $N-1$ 座橋樑，必須恰好呼叫函式 Bridge 共 $N-1$ 次。如果函式 Solve 執行結束時，呼叫函式 Bridge 的次數不是 $N-1$，你的程式會被判定為 Wrong Answer [6]。

重要注意事項

• 你的程式可以實作其他供內部使用的函式，或使用全域變數。
• 你的程式不得使用標準輸入和標準輸出，也不得以任何方式與其他檔案互動。不過，你的程式可以將除錯資訊輸出至標準錯誤。

編譯與測試執行

你可以從比賽網頁下載一個壓縮檔，其中包含用於測試程式的範例評測程式。壓縮檔也包含你的程式的範例原始碼檔案。

範例評測程式為 grader.cpp。若要測試你的程式，請將 grader.cpp、meetings.cpp 和 meetings.h 放在同一個目錄下，並執行下列指令來編譯程式。

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

編譯成功後，會產生可執行檔 grader。

注意，正式評測程式與範例評測程式不同。範例評測程式會以單一程序執行，從標準輸入讀取輸入資料，並將結果寫入標準輸出。

範例評測程式的輸入格式

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

$$ \begin{array}{l} N\\ A_0\ B_0\\ \vdots\\ A_{N-2}\ B_{N-2} \end{array} $$

$A_i$ 和 $B_i$（$0\le i\le N-2$）表示島嶼 $A_i$ 和 $B_i$ 之間有一座直接連接的橋樑。

範例評測程式的輸出格式

程式正常結束時，範例評測程式會將下列資訊寫入標準輸出（引號僅為清楚表示）。

• 如果你的程式被判定為正確，它會輸出呼叫函式 Query 的次數，例如 Accepted: 100。
• 如果你的程式被判定為答案錯誤，它會輸出錯誤類型，例如 Wrong Answer [1]。

如果你的程式同時符合多種類型的答案錯誤，範例評測程式只會回報其中一種。

資料範圍

關於 $A_i$ 和 $B_i$ 的定義，請參閱「範例評測程式的輸入格式」一節。

• $3\le N\le 2\,000$。
• $0\le A_i<B_i\le N-1$（$0\le i\le N-2$）。
• 沿著橋樑可以往來任意兩座島嶼。
• 每座島嶼直接相連的橋樑最多有 $18$ 座。

子任務

1. （7 分）$N\le 7$。
2. （10 分）$N\le 50$。
3. （12 分）$N\le 300$。

4. （71 分）沒有額外限制。

5. 對於子任務 1、2 和 3，如果你的程式正確處理該子任務的所有測試資料，便可獲得該子任務的滿分。

6. 對於子任務 4，如果你的程式正確處理所有測試資料，得分如下，其中 $X$ 是在單筆測試資料中呼叫函式 Query 的次數最大值。
   • 若 $40\,000<X\le 100\,000$，得 49 分；
   • 若 $X\le 40\,000$，得 71 分。

範例

以下是範例評測程式的一組範例輸入及對應的函式呼叫。

輸入格式 1

5
0 1
0 2
1 3
1 4

範例呼叫