小 Z 是一個很菜的 OI 選手，他有一個 $n$ 個點 $m$ 條邊的簡單連通無向圖，點從 $0, \ldots, n-1$ 編號，邊從 $0, \ldots, m-1$ 編號，編號為 $i$ 的邊連接點 $U_i$ 和 $V_i$。
小 Z 現在不想做題，於是他想了一個摸魚計畫：首先，他用鉛筆在紙上寫下了一個 $0, \ldots, n-1$ 的排列 $p_0, \ldots, p_{n-1}$。然後，他會多次進行操作：隨機選出一條圖上的邊 $u,v$，交換 $p_u$ 和 $p_v$ 的值。
由於某些原因，如果某個時刻，排列 $p$ 滿足對於所有 $0\le i \le n-1$ 都有 $p_i=i$，小 Z 就會突然想起自己有多菜並停止摸魚。小 Z 不想讓這種情況發生，所以，如果你告訴小 Z 一種通過 $k$ 次這樣的操作使排列 $p$ 滿足 $p_i=i$ 的方案，他就會在至多進行 $k-1$ 次操作之後停止摸魚，這時我們認為小 Z 在摸魚上花費的代價為 $k$。特別地，如果小 Z 第一次操作前 $p$ 就滿足 $p_i=i$，那麼小 Z 在摸魚上花費的代價為 $0$。
由於你知道小 Z 很菜，而且快要省選了，你想要破壞小 Z 的摸魚計畫。於是你找到了小 Z，一邊強行給他講知識點，一邊對他的摸魚計畫進行破壞：你的每次操作可以選出兩個整數 $0 \le u,v < n$，然後交換 $p_u$ 和 $p_v$ 的值。$u,v$ 可以相同，這表示你的這步操作不改變排列 $p$。在你的每次操作之後，你可以選擇繼續操作，或者結束操作並告訴小 Z 一種從此時的排列 $p$ 開始，在小 Z 的 $k$ 次操作後對所有 $i$ 都滿足 $p_i=i$ 的方案，使得小 Z 接下來在摸魚上花費的代價為 $k$。如果你選擇繼續操作，小 Z 可以先進行一次操作 (他也可以選擇跳過)：選出一條邊 $u,v$，然後交換 $p_u$ 和 $p_v$ 的值，然後再次由你操作。(小 Z 不能主動讓你停止操作)
小 Z 希望，在你結束操作後，接下來花費在摸魚上花費的代價儘可能大。你希望，在你結束操作之後，小 Z 接下來在摸魚上花費的代價儘可能小。小 Z 事先請小 U 幫他算出了如果雙方都採取最優策略，小 Z 花費在摸魚上的代價。所以如果你成功地使小 Z 花費在摸魚上的代價小於等於這個值，小 Z 會深深地感覺到自己和你的水平差距並停止摸魚，所以你會獲得這個測試點 $100\%$ 的分數。如果你僅僅算出了雙方都採取最優策略時小 Z 花費在摸魚上的代價，但是沒能給出方案，小 Z 也會感覺到自己和你的水平差距，但是他不會停止摸魚，所以你會獲得這個測試點 $30\%$ 的分數。
如果你的前 $T$ 次操作後沒有決定結束，小 Z 會拒絕讓你繼續操作，這時他會認為你無法給出一個合法方案，在這種情況下你至多能獲得這個測試點 $30\%$ 的分數。
實作細節
你所提交的程式碼必須包含檔案 graph.h
你不需要實作主函式，你只需要實作如下函式：
std::pair<std::pair<int, int>, std::vector<int> > Solve(int n, int m, int T, std::vector<int> U, std::vector<int> V, std::vector<int> p, int subtask);其中 $n,m,T,U,V,p$ 的含義如題目敘述所述。subtask 表示這組資料所在的子任務的編號。
這個函式可以呼叫如下兩個函式：
void Answer(int x);
int Swap(int u, int v);在 Solve 函式返回之前，你必須呼叫恰好一次 Answer 函式，其中傳入的參數 $x$ 為雙方都採取最優策略時，小 Z 花費在摸魚上的代價。在你呼叫 Swap 時，你必須確保 Answer 已經被呼叫恰好一次。
當你呼叫 Swap 函式時，你傳入的參數必須滿足 $0 \le u, v < n$，表示你進行了一次交換 $p_u$ 和 $p_v$ 的操作。假設這個函式的返回值為 $r$，若 $0 \le r < m$，表示小 Z 選擇編號為 $r$ 的邊進行了一次操作，否則表示小 Z 選擇跳過這次操作 (出現這種情況時保證 $r = -1$)。
如果你決定在一次操作之後結束操作，不要呼叫 Swap 函式，而是把這次操作作為返回值告訴互動庫。Solve 的返回值是一個 pair 和一個 vector 構成的 pair，前者對應於你的最後一次操作，後者對應於你給出的一種從你最後一次操作結束後的排列 $p$ 開始，用 $k$ 次小 Z 的操作使排列 $p$ 滿足 $p_i=i$ 的方案。$k$ 即是這個 vector 的長度。這個 vector 中的第 $i$ 項 (下標為 $i-1$) 表示第 $i$ 次操作的邊的編號。
評分方式
如果 Solve 函式沒有正常返回 (比如 RE，TLE)，你在這個測試點的評分為 $0$。（所以請不要使用 quit 等函式）
如果你在函式返回時還沒有呼叫 Answer，或者呼叫 Answer 超過一次，或者在呼叫 Answer 之前呼叫了 Swap，你在這個測試點的評分為 $0$。
如果你傳入 Answer 函式的參數不等於雙方都採取最優策略時，小 Z 花費在摸魚上的代價，你在這個測試點的評分為 $0$。
除上述情況下，如果你的操作不合法，或你返回的操作序列不合法，或在進行你返回的所有操作之後，$p$ 不滿足 $p_i=i$，你在這個測試點的評分為 $0.3$。
除上述情況外，如果你呼叫了 Swap 函式 $T$ 次，在你的第 $T$ 次呼叫時，互動庫會立刻退出程式，你在這個測試點的評分為 $0.3$。
除上述情況之外，你在這個測試點的評分為 $1$。
一個子任務的得分是這個子任務的總分乘以這個子任務所有測試點評分最小值。
下發檔案說明
下發檔案中的 graph 目錄下有兩個檔案：graph.h 和 grader.cpp
以 Linux 系統下為例，你可以用以下指令編譯得到一個可執行檔 grader。
g++ -std=c++11 graph.cpp grader.cpp -o grader然後執行指令
./gradergrader 的輸入格式如下：
第一行輸入四個整數 $n,m,T,subtask$。
第二行輸入 $n$ 個正整數，第 $i$ 個正整數表示 $p_{i-1}$ 的值。
接下來的 $m$ 行中的第 $i$ 行包含兩個正整數，表示 $U_{i-1}$ 和 $V_{i-1}$。
下發檔案中的 grader.cpp 的 Swap 函式始終返回 $-1$，且只會檢驗操作是否合法，僅作為一個例子。建議在測試程式前先修改 grader.cpp 中的策略。用於評測的 grader 與下發檔案中的不同。
子任務
對於所有資料，$2 \le n, m \le 100000, 0 \le p_i, U_i, V_i < n$，$\forall 0\le i < j < n, p_i \neq p_j$，$1 \le subtask \le 7$。保證雙方都採取最優策略時，小 Z 在摸魚上花費的代價不超過 $10^7$。保證給定的圖連通。
保證互動庫會採取某種最優策略。
- Subtask 1 ($10$ pts) : $n \le 8, T = 11$
- Subtask 2 ($15$ pts) : 保證給定的圖是一條鏈，保證邊 $i$ 連接點 $i$ 和點 $i+1$，$n \le 400, T = 100001$
- Subtask 3 ($15$ pts) : 保證給定的圖是一條鏈，保證邊 $i$ 連接點 $i$ 和點 $i+1$，$n \le 400, T = 1001$
- Subtask 4 ($15$ pts) : 保證給定的圖是一條鏈，保證邊 $i$ 連接點 $i$ 和點 $i+1$，$T = 100001$
- Subtask 5 ($10$ pts) : 保證給定的圖是一棵樹，$T = 100001$
- Subtask 6 ($15$ pts) : $n,m \le 400, T = 100001$
- Subtask 7 ($20$ pts) : $T = 100001$
保證互動庫花費的時間不會超過 $2\,\mathrm{s}$。