题目描述

小 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

然后执行命令

./grader

grader 的输入格式如下：

第一行输入四个整数 $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}$。