У Z — начинающий олимпиадник, у которого есть простой связный неориентированный граф с $n$ вершинами и $m$ ребрами. Вершины пронумерованы от $0$ до $n-1$, а ребра — от $0$ до $m-1$. Ребро с номером $i$ соединяет вершины $U_i$ и $V_i$.

Z не хочет решать задачи, поэтому придумал план безделья: сначала он записывает на бумаге перестановку $p_0, \ldots, p_{n-1}$ чисел от $0$ до $n-1$. Затем он многократно выполняет операцию: выбирает случайное ребро $(u, v)$ в графе и меняет местами значения $p_u$ и $p_v$.

По некоторым причинам, если в какой-то момент перестановка $p$ удовлетворяет условию $p_i = i$ для всех $0 \le i \le n-1$, Z внезапно вспоминает, как мало он знает, и прекращает бездельничать. Z не хочет, чтобы это произошло. Если вы укажете Z способ, позволяющий за $k$ таких операций привести перестановку $p$ к виду $p_i = i$, то он прекратит бездельничать не более чем через $k-1$ операций. В этом случае мы считаем, что цена безделья Z равна $k$. В частности, если до первой операции Z перестановка $p$ уже удовлетворяет $p_i = i$, то цена безделья Z равна $0$.

Поскольку вы знаете, что Z слаб, а скоро отборочный тур, вы хотите сорвать его план. Вы подходите к Z и, объясняя ему темы, мешаете его плану: каждая ваша операция заключается в выборе двух целых чисел $0 \le u, v < n$ и обмене значений $p_u$ и $p_v$. Значения $u$ и $v$ могут совпадать, что означает, что ваша операция не меняет перестановку $p$. После каждой вашей операции вы можете либо продолжить, либо закончить и сообщить Z способ, который, начиная с текущей перестановки $p$, приведет к $p_i = i$ за $k$ операций Z, чтобы цена безделья Z составила $k$. Если вы решите продолжить, Z может сначала выполнить одну операцию (или пропустить её): выбрать ребро $(u, v)$ и поменять местами $p_u$ и $p_v$, после чего снова наступает ваш ход. (Z не может заставить вас прекратить операции).

Z хочет, чтобы после того, как вы закончите, цена его безделья была как можно больше. Вы хотите, чтобы после того, как вы закончите, цена безделья Z была как можно меньше. Z заранее попросил U помочь ему вычислить цену безделья, если обе стороны будут придерживаться оптимальной стратегии. Если вам удастся сделать цену безделья Z меньше или равной этому значению, Z глубоко осознает разницу в уровне между вами и прекратит бездельничать, за что вы получите $100\%$ баллов за этот тест. Если вы вычислили цену безделья при оптимальной игре, но не смогли предоставить план, Z также осознает разницу в уровне, но не прекратит бездельничать, за что вы получите $30\%$ баллов.

Если после $T$ ваших операций вы не решили закончить, Z откажется продолжать, посчитав, что вы не можете предоставить корректный план. В этом случае вы получите не более $30\%$ баллов за этот тест.

Детали реализации

Ваш код должен включать файл graph.h.

Вам не нужно реализовывать функцию main, достаточно реализовать следующую функцию:

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$ означает, что Z выбрал ребро с номером $r$ для своей операции, либо $r = -1$, если Z решил пропустить ход.

Если вы решили закончить после операции, не вызывайте Swap, а верните эту операцию как часть результата. Возвращаемое значение Solve — это pair, состоящая из пары (ваша последняя операция) и vector (план из $k$ операций Z, приводящий $p$ к $p_i = i$). $k$ — это длина вектора. $i$-й элемент вектора (индекс $i-1$) — это номер ребра для $i$-й операции.

Оценивание

Если функция Solve завершается некорректно (например, RE, TLE), оценка за тест — $0$.

Если при возврате из функции Answer не была вызвана, была вызвана более одного раза или Swap была вызвана до Answer, оценка за тест — $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

Затем выполните:

./grader

Формат входных данных grader:

Первая строка: четыре целых числа $n, m, T, subtask$.

Вторая строка: $n$ целых чисел, $i$-е число — значение $p_{i-1}$.

Следующие $m$ строк: $i$-я строка содержит два целых числа $U_{i-1}$ и $V_{i-1}$.

Функция Swap в предоставленном grader.cpp всегда возвращает $-1$ и только проверяет корректность операций. Рекомендуется изменить стратегию в grader.cpp перед тестированием. Интерактор, используемый при проверке, отличается от предоставленного.

Подзадачи

Для всех данных $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$ баллов): $n \le 8, T = 11$

Subtask 2 ($15$ баллов): Граф — цепь, ребро $i$ соединяет $i$ и $i+1$, $n \le 400, T = 100001$

Subtask 3 ($15$ баллов): Граф — цепь, ребро $i$ соединяет $i$ и $i+1$, $n \le 400, T = 1001$

Subtask 4 ($15$ баллов): Граф — цепь, ребро $i$ соединяет $i$ и $i+1$, $T = 100001$

Subtask 5 ($10$ баллов): Граф — дерево, $T = 100001$

Subtask 6 ($15$ баллов): $n, m \le 400, T = 100001$

Subtask 7 ($20$ баллов): $T = 100001$

Гарантируется, что время работы интерактора не превышает $2\,\mathrm{s}$.