Little Z is a mediocre OI contestant who has a simple connected undirected graph with $n$ vertices and $m$ edges. The vertices are numbered $0, \ldots, n-1$ and the edges are numbered $0, \ldots, m-1$. The edge with index $i$ connects vertices $U_i$ and $V_i$.

Little Z does not want to solve problems, so he has devised a slacking plan: first, he writes down a permutation $p_0, \ldots, p_{n-1}$ of $0, \ldots, n-1$ on a piece of paper. Then, he performs an operation multiple times: he randomly selects an edge $(u, v)$ in the graph and swaps the values of $p_u$ and $p_v$.

For some reason, if at any moment the permutation $p$ satisfies $p_i = i$ for all $0 \le i \le n-1$, Little Z will suddenly realize how mediocre he is and stop slacking. Little Z does not want this to happen. Therefore, if you tell Little Z a sequence of $k$ such operations that makes the permutation $p$ satisfy $p_i = i$, he will stop slacking after at most $k-1$ operations. In this case, we say the cost Little Z spent on slacking is $k$. Specifically, if $p$ already satisfies $p_i = i$ before the first operation, the cost Little Z spent on slacking is $0$.

Since you know Little Z is mediocre and the provincial selection is approaching, you want to sabotage his slacking plan. You approach Little Z, and while forcing him to learn concepts, you sabotage his plan: in each of your operations, you can choose two integers $0 \le u, v < n$ and swap the values of $p_u$ and $p_v$. $u$ and $v$ can be the same, which means your operation does not change the permutation $p$. After each of your operations, you can choose to continue or stop and provide Little Z with a sequence of operations starting from the current permutation $p$ such that after $k$ operations by Little Z, $p_i = i$ for all $i$, making the cost Little Z spends on slacking equal to $k$. If you choose to continue, Little Z can perform one operation (he may also choose to skip): select an edge $(u, v)$ and swap the values of $p_u$ and $p_v$, then it is your turn again. (Little Z cannot force you to stop.)

Little Z hopes that after you finish your operations, the cost he spends on slacking will be as large as possible. You hope that after you finish your operations, the cost Little Z spends on slacking will be as small as possible. Little Z has asked Little U to calculate the cost he would spend on slacking if both parties play optimally. If you successfully make the cost Little Z spends on slacking less than or equal to this value, Little Z will deeply feel the gap between his level and yours and stop slacking, earning you $100\%$ of the points for this test case. If you only calculate the cost Little Z spends on slacking under optimal play but fail to provide the sequence, Little Z will still feel the gap but will not stop slacking, earning you $30\%$ of the points for this test case.

If you do not decide to stop after your first $T$ operations, Little Z will refuse to let you continue, and he will consider you unable to provide a valid solution. In this case, you can earn at most $30\%$ of the points for this test case.

Implementation Details

Your submitted code must include the file graph.h.

You do not need to implement the main function; you only need to implement the following function:

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);

The meanings of $n, m, T, U, V, p$ are as described in the problem. subtask indicates the index of the subtask this data belongs to.

This function can call the following two functions:

void Answer(int x);

int Swap(int u, int v);

Before the Solve function returns, you must call the Answer function exactly once, where the parameter $x$ is the cost Little Z spends on slacking when both parties play optimally. When you call Swap, you must ensure that Answer has already been called exactly once.

When you call the Swap function, the parameters you pass must satisfy $0 \le u, v < n$, indicating that you performed an operation to swap $p_u$ and $p_v$. Suppose the return value of this function is $r$: if $0 \le r < m$, it means Little Z chose the edge with index $r$ to perform an operation; otherwise, it means Little Z chose to skip this operation (in this case, it is guaranteed that $r = -1$).

If you decide to stop after an operation, do not call the Swap function; instead, return this operation as part of the return value to the interaction library. The return value of Solve is a pair consisting of a pair and a vector. The former corresponds to your last operation, and the latter corresponds to a sequence of operations starting from the permutation $p$ after your last operation, such that after $k$ operations by Little Z, $p_i = i$ for all $i$. $k$ is the length of this vector. The $i$-th item in this vector (at index $i-1$) represents the index of the edge used in the $i$-th operation.

Scoring

If the Solve function does not return normally (e.g., RE, TLE), your score for this test case is $0$. (Please do not use functions like quit.)

If you have not called Answer when the function returns, or if you call Answer more than once, or if you call Swap before calling Answer, your score for this test case is $0$.

If the parameter you pass to the Answer function is not equal to the cost Little Z spends on slacking when both parties play optimally, your score for this test case is $0$.

Except for the above cases, if your operations are invalid, or your returned operation sequence is invalid, or after performing all the operations you returned, $p$ does not satisfy $p_i = i$, your score for this test case is $0.3$.

Except for the above cases, if you have called the Swap function $T$ times, the interaction library will terminate the program immediately upon your $T$-th call, and your score for this test case is $0.3$.

Except for the above cases, your score for this test case is $1$.

The score for a subtask is the total score of that subtask multiplied by the minimum score among all test cases in that subtask.

Provided Files

There are two files in the graph directory of the provided files: graph.h and grader.cpp.

Taking a Linux system as an example, you can compile it into an executable file grader using the following command:

g++ -std=c++11 graph.cpp grader.cpp -o grader

Then execute the command:

./grader

The input format for grader is as follows:

The first line contains four integers $n, m, T, subtask$.

The second line contains $n$ positive integers, where the $i$-th positive integer represents the value of $p_{i-1}$.

The next $m$ lines, the $i$-th line contains two positive integers representing $U_{i-1}$ and $V_{i-1}$.

The Swap function in the provided grader.cpp always returns $-1$ and only checks if the operation is valid; it serves only as an example. It is recommended to modify the strategy in grader.cpp before testing your program. The grader used for evaluation is different from the one provided.

Subtasks

For all data, $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$. It is guaranteed that the cost Little Z spends on slacking when both parties play optimally does not exceed $10^7$. It is guaranteed that the given graph is connected.

It is guaranteed that the interaction library will adopt an optimal strategy.

Subtask 1 ($10$ pts): $n \le 8, T = 11$

Subtask 2 ($15$ pts): The given graph is guaranteed to be a chain, and edge $i$ connects vertex $i$ and vertex $i+1$, $n \le 400, T = 100001$

Subtask 3 ($15$ pts): The given graph is guaranteed to be a chain, and edge $i$ connects vertex $i$ and vertex $i+1$, $n \le 400, T = 1001$

Subtask 4 ($15$ pts): The given graph is guaranteed to be a chain, and edge $i$ connects vertex $i$ and vertex $i+1$, $T = 100001$

Subtask 5 ($10$ pts): The given graph is guaranteed to be a tree, $T = 100001$

Subtask 6 ($15$ pts): $n, m \le 400, T = 100001$

Subtask 7 ($20$ pts): $T = 100001$

It is guaranteed that the time taken by the interaction library will not exceed $2\,\mathrm{s}$.