呢題係互動題。
題目背景
隔咗半年，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$，當且僅當同 $x$ 號洞穴相連嘅所有通路都已經透過操作 3 記錄低，先會回傳 $1$。
評測嗰陣，互動庫會恰好呼叫 explore 一次。
本題保證，使用嘅圖喺互動開始之前已經完全確定，唔會根據同你程式嘅互動過程動態構造。所以題目入面嘅互動操作都係確定性嘅，你唔需要理會呢啲操作喺互動庫入面嘅具體實作。
資料保證，喺呼叫次數限制之內，互動庫運行所需時間唔超過 $1\mathrm{s}$；互動庫使用嘅記憶體大小固定，而且唔超過 $128\mathrm{MB}$。
實作方法
選手工作目錄已經提供咗 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\times10^4$ | $2M$ | 無 |
| 4 | 300 | $10N$ | 299 | $9\times10^4$ | $2M$ | 無 |
| 5 | 500 | $10N$ | 499 | $1.5\times10^5$ | $2M$ | 無 |
| 6 | 59998 | $N/2$ | $17N$ | $17N$ | 0 | A |
| 7 | 99998 | $N/2$ | $18N$ | $18N$ | 0 | A |
| 8 | 199998 | $N/2$ | $19N$ | $19N$ | 0 | A |
| 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 | 199996 | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| 14 | 199996 | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| 15 | 99995 | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| 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\times10^4$ | $2M$ | 無 |
| 19 | 1004 | 3000 | $10^7$ | $5\times10^4$ | $2M$ | 無 |
| 20 | 1004 | 3000 | $10^7$ | $5\times10^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$，令 $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$ 嘅個位數，分辨以上唔同嘅資料類型。