這是一道互動題。
題目背景
時隔半年，I 君的商店終於開不下去了，他決定轉讓商店，做一名探險家去探索未知的廣闊世界。
根據古書記載，他在一個大荒漠的腹地找到了未知文明創造的地下宮殿，宮殿由 $N$ 個大型洞穴和 $M$ 條連接這些洞穴的雙向通路構成。I 君能藉助古書分辨所處的洞穴，但書中並沒有記錄 $M$ 條通路的連接結構，因此他難以搜尋傳說中藏在宮殿裡的無盡財寶。
不過現在 I 君發現了一個神祕機關，透過它可以獲知宮殿的資訊，I 君決定利用這個機關來得到宮殿的連接結構，請你來協助他。
題目敘述
地下宮殿可以抽象成一張 $N$ 個點、$M$ 條邊的無向簡單圖（簡單圖滿足任意兩點之間至多存在一條直接相連的邊），洞穴從 $0\sim n-1$ 編號。目前你並不知道邊有哪些。
每個洞穴都擁有一個光源，光源有開啟、關閉兩種狀態，只有當光源處於開啟狀態時它所在的洞穴才會被照亮。初始時所有的光源都處於關閉狀態，而光源的狀態只能用 I 君發現的神祕機關改變。更具體地，使用神祕機關可以進行如下四種操作：
- 向機關給定一個編號 $x$，機關將會改變 $x$ 號洞穴，以及與 $x$ 號洞穴有通路直接相連的洞穴的光源狀態。即原來開啟的光源將會關閉；原來關閉的光源將會開啟。
- 向機關給定一個編號 $x$，機關將會顯示當前 $x$ 號洞穴光源的狀態。
- 向機關給定兩個編號 $x,y$，表示你確定有一條連接 $x$ 號洞穴與 $y$ 號洞穴的通路，並讓機關記錄。
- 向機關給定一個編號 $x$，機關將會判斷與 $x$ 號洞穴相連的通路是否都已被記錄。
機關在完成上一次操作後才能進行下一次操作。機關不能隨意使用，因此每種操作的使用次數都有限制，分別為 $L_m,L_q,M,L_c$。你的任務是，編寫一個程式，幫助 I 君決定如何合理利用神祕機關，從而正確地找到這 $M$ 條通路。
實作細節
你不需要，也不應該實作主函式，你只需要實作函式 explore(N, M)，這裡的 $N$ 和 $M$ 分別表示洞穴和通路的個數。你可以透過呼叫如下四個函式來和互動程式庫進行互動：
modify(x)這個函式可以令機關執行操作 1，給定的編號為 $x$。
你需要保證 $0\le x<N$，這個函式沒有回傳值。
query(x)這個函式可以令機關執行操作 2，給定的編號為 $x$。
你需要保證 $0\le x<N$，這個函式回傳 $0$ 或 $1$，表示目前 $x$ 號洞穴的光源為關閉（$0$ 表示）或開啟（$1$ 表示）狀態。
report(x, y)這個函式可以令機關執行操作 3，給定的編號為 $x,y$。
你需要保證 $0\le x,y<N$ 且 $x\ne y$，這個函式沒有回傳值。
check(x)這個函式可以令機關執行操作 4，給定的編號為 $x$。
- 你需要保證 $0\le x<N$，這個函式回傳 $0$ 或 $1$，其中回傳 $1$ 若且唯若與 $x$ 號洞穴相連的所有通路都已透過操作 3 被記錄。
評測時，互動程式庫會恰好呼叫 explore 一次。
本題保證所使用的圖在互動開始之前已經完全確定，不會根據和你的程式的互動過程動態構造，因此題目中的互動操作都是確定性的，你不需要關心這些操作在互動程式庫中的具體實作。
資料保證在呼叫次數限制下，互動程式庫執行所需的時間不超過 1s；互動程式庫使用的記憶體大小固定，且不超過 128MB。
實作方法
選手工作目錄下已經提供了一個 template_explore.cpp/c/pas，請將這個檔案複製一份，重新命名為 explore.cpp/c/pas，然後在其基礎上作答。
對 C++ / C 語言選手
- 請確保你的程式開頭有
#include "explore.h"。 - 你需要實作的函式
explore的介面資訊如下：
void explore(int N, int M);- 你可以呼叫的互動函式的介面如下：
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);對 Pascal 語言選手
- 注意：Pascal 的程式碼中實作介面的語法較為複雜，請選手直接在下發的
template_explore.pas的基礎上作答，而不是自己從頭實作程式碼。 - 你需要實作的函式
explore的介面資訊如下：
procedure _explore(N, M : longint);- 注意：這裡的函式名稱是
_explore而非explore，如果使用explore將導致編譯失敗。 - 你可以呼叫的互動函式的介面如下：
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;測試程式方式
試題目錄下的 grader.cpp/c 以及 graderhelperlib.pas 是我們提供的互動程式庫參考實作，最終測試時所用的互動程式庫實作與該參考實作有所不同，因此選手的解法不應該依賴互動程式庫實作。
對 C/C++ 語言的選手
- 你需要在本題目錄下使用如下命令編譯得到可執行程式：
- 對於 C 語言：
gcc grader.c explore.c -o explore -O2 -lm - 對於 C++ 語言：
g++ grader.cpp explore.cpp -o explore -O2 -lm
對於 Pascal 語言的選手
- 你需要在本題目錄下使用如下命令編譯得到可執行程式：
fpc grader.pas -o"explore" -O2
對於編譯得到的可執行程式
- 可執行檔將從標準輸入讀入以下格式的資料：
第一行包含三個整數 $L_m,L_q,L_c$，第二行包含兩個整數 $N,M$，意義如題面敘述。
接下來 $M$ 行，每行兩個整數 $x,y$，描述一條連接 $x$ 號洞穴與 $y$ 號洞穴的通路。
- 讀入完成之後，互動程式庫將呼叫恰好一次函式
explore，用輸入的資料測試你的函式。你的函式正確回傳後，互動程式庫會判斷你的計算是否正確，若正確則會輸出Correct和互動函式呼叫次數相關資訊，否則會輸出相應的錯誤資訊。
互動
假設可執行檔讀入的資料為：
100 200 300 3 2 0 1 1 2
資料第一行的三個整數分別表示三種操作的呼叫次數限制，即 modify(x) 呼叫次數不能超過 $100$，query(x) 呼叫次數不能超過 $200$，check(x) 呼叫次數不能超過 $300$。
資料第二行的兩個整數分別表示洞穴數和通路條數，即 $N=3$，$M=2$。
report(x, y) 呼叫次數不能超過 $M$，該例子中即不超過 $2$ 次。
下面是一個正確的互動過程：
| 選手程式 | 互動程式庫 | 說明 |
|---|---|---|
呼叫 explore(3, 2) |
開始測試 | |
呼叫 modify(0) |
對 $0$ 號洞穴做操作 1 | |
呼叫 query(2) |
回傳 $0$ | 目前 $2$ 號洞穴的光源狀態是關閉 |
呼叫 report(0, 1) |
發現了通路 $(0,1)$ 並記錄 | |
呼叫 check(0) |
回傳 $1$ | 與 $0$ 號洞穴相關的通路都已被記錄 |
呼叫 report(2, 1) |
發現了通路 $(2,1)$ 並記錄 | |
| 執行結束並回傳 | 向螢幕列印 Correct |
互動結束，結果正確 |
下發檔案說明
在本試題目錄下：
grader.cpp/c以及graderhelperlib.pas是我們提供的互動程式庫參考實作。explore.h和grader.pas是標頭檔，選手不用關心具體內容。template_explore.cpp/c/pas是我們提供的範例解題原始碼。explore1.in、explore2.in、explore3.in是範例輸入，可供測試。
選手注意對所有下發檔案做好備份。評測只收取本試題目錄下的 explore.c/cpp/pas，並且對該程式以外的檔案的修改無效。
評分方式
最終評測只會收取 explore.cpp/c/pas，修改選手目錄下其他檔案對評測無效。
本題首先會受到和傳統題相同的限制。例如編譯錯誤會導致整道題目得 $0$ 分，執行時錯誤、超過時間限制、超過空間限制等會導致相應測試點得 $0$ 分等。你只能存取自己定義的和互動程式庫給出的變數及其對應的記憶體空間，嘗試存取其他空間將可能導致編譯錯誤或執行錯誤。
在上述條件基礎上，在一個測試點中，你得到滿分，若且唯若：
- 你的每次函式呼叫均合法，且呼叫
modify、query和check的次數分別不超過 $L_m,L_q,L_c$。 - 由於
report的呼叫次數限制為 $M$，你的每次呼叫都必須記錄一條新的且存在的邊；即每次呼叫report(x, y)時，應滿足：有一條連接 $x$ 號洞穴和 $y$ 號洞穴的通路，且在這次呼叫之前從未呼叫過report(x, y)或report(y, x)。 - 你實作的函式
explore正常回傳。 - 在
explore函式回傳時，你已經透過呼叫report記錄了全部 $M$ 條通路。
資料範圍
本題共 25 個測試點，每個測試點 4 分。每個測試點的資料規模和相關限制見下表。
| 測試點編號 | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | 特殊性質 |
|---|---|---|---|---|---|---|
| $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | 無 |
| $2$ | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | 無 |
| $3$ | $200$ | $10N$ | $200$ | $4\times 10^4$ | $2M$ | 無 |
| $4$ | $300$ | $10N$ | $299$ | $9\times 10^4$ | $2M$ | 無 |
| $5$ | $500$ | $10N$ | $499$ | $1.5\times 10^5$ | $2M$ | 無 |
| $6$ | $59998$ | $N/2$ | $17N$ | $17N$ | $0$ | A |
| $7$ | $99998$ | $N/2$ | $18N$ | $18N$ | $0$ | A |
| $8,9$ | $199998$ | $N/2$ | $19N$ | $19N$ | $0$ | A |
| $10$ | $99997$ | $N-1$ | $18N$ | $18N$ | $0$ | B |
| $11$ | $199997$ | $N-1$ | $19N$ | $19N$ | $0$ | B |
| $12$ | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $13,14$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $15,16$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $17$ | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $18$ | $1004$ | $2000$ | $10^7$ | $5\times 10^4$ | $2M$ | 無 |
| $19,20$ | $1004$ | $3000$ | $10^7$ | $5\times 10^4$ | $2M$ | 無 |
| $21$ | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | 無 |
| $22$ | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | 無 |
| $23$ | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | 無 |
| $24$ | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | 無 |
| $25$ | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | 無 |
再次提醒，題目保證測試所使用的圖在互動開始之前已經完全確定，而不會根據和你的程式的互動動態構造。
表中特殊性質欄中變數的含義如下：
A：保證每個點的度數恰好為 $1$。
B：保證對於每個 $x>0$，存在恰好一個 $y<x$ 的 $y$ 使得 $x$ 號洞穴與 $y$ 號洞穴有通路直接相連。
C：存在 $0\sim N-1$ 的一個排列 $p_0,p_1,\ldots,p_{N-1}$，使得對任意 $1\le i<N$，存在一條連接洞穴編號分別為 $p_{i-1}$ 與 $p_i$ 的通路。
D：保證圖連通。
- 提示：你的程式可以透過判斷傳入的 $N$ 的個位來區分上述不同的資料類型。