有 $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}{ll} 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

函數呼叫範例