本題請不要使用標準輸入輸出流，不過你仍然可以輸出除錯訊息至標準錯誤流（stderr）。

你的程式需要在一開始使用前置處理器引入 lib0906.h，詳細請參考範例實作。

你需要完成以下的一個函式：

std::vector<std::pair<int, int>> treeguessr(int n);

• 在一筆測試資料中，treeguessr 會被呼叫恰一次。
• n 為遊戲中樹的節點數。
• 節點的編號為 $1, 2, \ldots, n$。
• 回傳值必須為一個長度為 $n - 1$ 的陣列，其中若第 $i$ 項為 $(u_i, v_i)$，則代表樹 $T$ 的第 $i$ 條邊連接節點 $u_i$ 與節點 $v_i$。邊可以用任意順序輸出。

你可以呼叫以下函式：

int query(int p, std::vector<int> S);

• 引數 $p$ 需滿足 $1 \leq p \leq n$。
• 引數 $S$ 需滿足 $|S| > 0$ 且 $\forall s \in S, 1 \leq s \leq n$。
• 回傳值是一個整數，表示 $\textrm{query}(p, S)$ 的值。
• query 不得被呼叫超過 $\textbf{2\ 000\ 000}$ 次。

如果任意一個條件沒有被滿足，你的程式會被判斷為 Wrong Answer 並且獲得 0 分，否則，你的程式將依照 Scoring 中的敘述評分。

假設 $n = 4$，一個被判斷為 Accepted 的範例互動狀況如下：

評測程式端	參賽者程式端
呼叫 treeguessr(4)。
	呼叫 query(1, {4})。
回傳 2。
	呼叫 query(2, {1, 4})。
回傳 1。
	呼叫 query(3, {1})。
回傳 1。
	呼叫 query(4, {1, 2})。
回傳 2。
	回傳 {{1, 2}, {1, 3}, {3, 4}}。

• $2 \leq n \leq 1500$
• 樹 $T$ 不會隨著互動過程而改變。

假設在所有測試資料中，你呼叫 query 的次數最大值為 $q$，你的得分會是該子題的得分乘上倍數 $p$，由下列方式計算：

• 如果 $q \leq 10\ 100$， $$p = 1$$
• 否則， $$p = \frac{10\ 100}{q}$$

範例評分程式以下列方式輸入：

• line $1$: $n$
• line $2+i (0\leq i < n - 1)$: $u_i$ $v_i$

範例評分程式以下列方式輸出：

如果你的程式被判斷為 Accepted，範例評分程式會輸出 Accepted: q，其中 q 為呼叫 query 的次數。接著輸出 $n - 1$ 行，第 $i$ 行有兩個整數 $u_i, v_i$ 代表你回傳的第 $i$ 條邊連接的點。

如果你的程式被判斷為 Wrong Answer，範例評分程式會輸出 Wrong Answer: MSG，其中 MSG 以及其代表的意思為以下列表的其中一個：

• p must be between 1 and n: query 函式傳入的 $p$ 不在 $1$ 至 $n$ 的範圍內。
• S must be nonempty: query 函式傳入的 $S$ 為空。
• elements in S must be between 1 and n: query 函式傳入的 $S$ 內有不在 $1$ 至 $n$ 範圍內的數。
• Too many queries: query 的呼叫次數過多。
• invalid answer：回傳的陣列長度不是 $n - 1$。

如果有多個原因，範例評分程式只會輸出任何一個。

另外請注意，範例評分程式並不會幫你檢查你回傳的數值是否是正確的。

由於 Windows Defender 以及各種奇怪東西的限制，本題的範例編譯指令不提供 Windows 批次檔。編譯及測試教學請參考下列說明。

• 如果你的系統是 Linux，你可以直接執行 compile.sh 編譯你的程式，編譯結果會是 treeguessr.exe，請直接用命令列執行該檔案。
• 如果你的系統是 MacOS，你需要將 compile.sh 當中的 -static 參數移除，其餘與 Linux 相同。
• 如果你的系統是 Windows，你有以下的選擇：
  1. 本地測試時加入 #include "grader.cpp"，並且以單一檔案的編譯執行方式測試，請注意這一行上傳時需要刪除，否則你會獲得一個 Compile Error。
  2. 將 compile.sh 的變數替換後直接於命令列執行，請注意你需要確保 g++ 在系統的環境變數 PATH 中。
  3. 如果你的電腦已經有 WSL (Windows Subsystem for Linux)，你可以直接使用 WSL 並按照 Linux 的做法。
  4. 使用電腦教室的 Ubuntu（啟動時可以選擇系統）並按照 Linux 的做法。

IOICamp 2025 Day2 pF