我要找的书或许是目录之目录。

这是一道交互题。

给你一张 $n$ 个点 $m$ 条边的简单无向连通图，每条边有 可通行 和 不可通行 两种状态，初始每条边的状态均为不可通行。

第 $i(1\le i\le n)$ 个点上初始有权值 $p_i$，$p$ 是一个 $1\dots n$ 的排列。

你可以调用以下两种函数，你的目标是使得 $\forall 1\le i\le n,p_i=i$。调用函数的总次数不能超过 $10^5$。

void flip(int id);

功能是改变第 $id(1\le id\le m)$ 条边的状态。即，可通行变为不可通行，不可通行变为可通行。

vector<int> shuffle(int x);

对于这张图上只保留状态为可通行的边时 $x(1\le x\le n)$ 所属的连通块，交互库会将这个连通块中所有点的权值 $p_i$ 均匀随机重排列，然后返回一个长度为 $n$ 的 vector<int> 表示新的权值 $p$，下标为 $i(0\le i < n)$ 的项表示新的 $p_{i+1}$。

交互格式

你不需要，也不应该实现 main 函数。

你应确保提交的程序包含头文件 shuffle.h，可在程序开头加入以下代码实现：

#include "shuffle.h"

你应当实现下面的函数：

void solve(int n,int m,std::vector<std::pair<int,int>> edge,std::vector<int> p);

其中，n，m 和 p 的含义如题目所述；edge[i].first 和 edge[i].second 表示第 $i+1$ 条边的两个端点。

solve 被交互库调用完毕后：

• 如果你没有调用 shuffle 函数，那么你需要保证初始的 $p$ 满足 $\forall 1\le i\le n,p_i=i$。
• 否则，你需要保证最后一次 shuffle 函数返回的 $p$ 满足 $\forall 1\le i\le n,p_i=i$。

如何测试你的程序

在终端下输入如下命令进行编译：

g++ grader.cpp your_code.cpp -o shuffle -O2 -std=c++14

得到可执行文件 shuffle 后输入样例进行测试，如果测试通过将会输出 OK 和两个整数，分别为 flip 次数和 shuffle 次数。样例也在附件中，其输入格式为图的点数、边数、每条边的两个端点和 $p$。

数据规模与评分标准

本题采用捆绑测试。

对于所有数据，$2\le n\le 1000$，$n-1\le m \le 3000$。

其中每个子任务取其中分数倍率最低的测试点，乘上该子任务的满分得到最终分数。

对于子任务 $1$，若你调用函数总次数不超过 $10^5$，则分数倍率为 $1$，否则为 $0$。

对于子任务 $2$，设你调用函数的总次数为 $X$，分数倍率 $f(X)$ 定义如下：

$$ f(X)= \begin{cases} 1, & X\le 3\times 10^4,\\[4pt] \left(\dfrac{10^5-X}{7\times 10^4}\right)^2, & 3\times 10^4 \lt X \lt 10^5,\\[10pt] 0, & X\ge 10^5. \end{cases} $$

交互库的随机种子是确定的。也就是说，对于一份不含随机性的代码，多次提交的结果是相同的。保证在合法的交互次数内，交互库的运行时间不超过 $\texttt{3s}$。实际的交互库可能与下发的不同。

时间限制：$5\texttt{s}$

空间限制：$512\texttt{MB}$