题目背景

在洛谷上提交时，需要将两个文件合并成一个提交。

不要引入任何头文件，并在文件头加入以下内容：

void Alice(int N, int M, int A[], int B[] );
void InitG(int V, int U );
void MakeG(int pos, int C, int D );
void Bob(int V, int U, int C[], int D[] );
void InitMap(int N, int M );
void MakeMap(int A, int B );

题目描述

Alice 居住在 JOI 王国。她计划邀请居住在 IOI 共和国的 Bob。在邀请他之前，她打算将 JOI 王国的航线地图发送给他。JOI 王国是一个由 $N$ 个岛屿组成的岛国，岛屿编号从 $0$ 到 $N-1$。JOI 王国内共有 $M$ 条航线。对于每个 $i$（$0 \le i \le M-1$），第 $(i+1)$ 条航线连接岛屿 $A_i$ 和岛屿 $B_i$，且为双向航线。任意两条航线不会连接相同的两个岛屿。她必须使用一台由 JOI 王国运营的特殊电报机。她可以通过该电报机发送一个无向图。然而，当她使用它时，顶点编号和边编号会被随机打乱。

具体而言，信息的发送方式如下。设 $G$ 为 Alice 发送的图（令 $V$ 为图 $G$ 的顶点数，$U$ 为图 $G$ 的边数）：

• Alice 指定图 $G$ 的边数 $V$ 和边数 $U$。然后，她将数字 $0, 1, \ldots, V-1$ 分别分配给每个顶点，将数字 $0, 1, \ldots, U-1$ 分别分配给每条边。
• Alice 指定参数 $C_0, C_1, \ldots, C_{U-1}$ 和 $D_0, D_1, \ldots, D_{U-1}$。这些参数描述图 $G$ 的边，即对于每个 $j$（$0 \le j \le U-1$），图 $G$ 的第 $j$ 条边连接顶点 $C_j$ 和顶点 $D_j$。
• 图 $G$ 的顶点编号由 JOI 王国打乱。首先，JOI 王国生成一个序列 $p[0], p[1], \ldots, p[V-1]$，它是 $0, 1, \ldots, V-1$ 的一个排列。然后，$C_0, C_1, \ldots, C_{U-1}$ 被替换为 $p[C_0], p[C_1], \ldots, p[C_{U-1}]$，而 $D_0, D_1, \ldots, D_{U-1}$ 被替换为 $p[D_0], p[D_1], \ldots, p[D_{U-1}]$。
• 接着，图 $G$ 的边编号由 JOI 王国打乱。首先，JOI 王国生成一个序列 $q[0], q[1], \ldots, q[U-1]$，它是 $0, 1, \ldots, U-1$ 的一个排列。然后，$C_0, C_1, \ldots, C_{U-1}$ 被替换为 $C_{q[0]}, C_{q[1]}, \ldots, C_{q[U-1]}$，而 $D_0, D_1, \ldots, D_{U-1}$ 被替换为 $D_{q[0]}, D_{q[1]}, \ldots, D_{q[U-1]}$。
• 以下数据被发送给 Bob：$V$ 和 $U$ 的值，以及参数 $C_0, C_1, \ldots, C_{U-1}$ 和 $D_0, D_1, \ldots, D_{U-1}$ 的最新值。

请注意，使用这台电报机只能发送一个简单图。此处，“简单图”指不含重边和自环的图。

换句话说，她可以发送一个满足以下条件的图：对于任意 $i, j$（$0 \le i < j \le U-1$），$(C_i, D_i) \ne (C_j, D_j)$ 且 $(C_i, D_i) \ne (D_j, C_j)$ 成立；同时，对于任意 $i$（$0 \le i \le U-1$），$C_i \ne D_i$ 成立。

Alice 希望使用顶点数最少的图，将 JOI 王国的航线地图发送给 Bob。

任务

为了帮助 Alice 与 Bob 之间的通信，请编写以下两个程序：

• 给定 JOI 王国的岛屿数量 $N$、航线数量 $M$，以及表示 JOI 王国航线地图的序列 $A$、$B$，第一个程序应输出 Alice 发送的图 $G$ 的信息。
• 给定 Bob 收到的图 $G$ 的信息，第二个程序应恢复 JOI 王国的航线地图。

实现细节

你需要提交两个文件。

第一个文件为 Alice.cpp。该文件应输出 Alice 发送的图的信息。它应实现以下函数。程序应包含头文件 Alicelib.h。

• void Alice( int N, int M, int A[], int B[] )

  对于每个测试用例，该函数被调用一次。

  • 参数 $N$ 是 JOI 王国的岛屿数量。
  • 参数 $M$ 是 JOI 王国的航线数量。
  • 参数 $A[]$、$B[]$ 是长度为 $M$ 的序列，用于描述 JOI 王国的航线地图。

通过以下函数，函数 Alice 输出 Alice 发送的图 $G$ 的信息。

• void InitG( int V, int U )

  该函数指定图 $G$ 的顶点数和边数。

  • 参数 $V$ 是图 $G$ 的顶点数。参数 $V$ 应为介于 $1$ 到 $1500$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被视为 Wrong Answer [1]。
  • 参数 $U$ 是图 $G$ 的边数。参数 $U$ 应为介于 $0$ 到 $V(V-1)/2$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被视为 Wrong Answer [2]。

• void MakeG( int pos, int C, int D )

  该函数指定图 $G$ 的边。

  • 参数 pos 是由本次调用指定的边的编号。参数 pos 应为介于 $0$ 到 $U-1$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被视为 Wrong Answer [3]。该函数对相同的参数 pos 不应被调用超过一次；若被多次调用，你的程序将被视为 Wrong Answer [4]。
  • 参数 $C$ 和 $D$ 是图 $G$ 中边 pos 的两个顶点。$C$ 和 $D$ 应为介于 $0$ 到 $V-1$（含）之间的整数，且应满足 $C \ne D$。若 $C$ 或 $D$ 不满足这些条件，你的程序将被视为 Wrong Answer [5]。此处，$U$ 和 $V$ 是由函数 InitG 指定的整数。

在函数 Alice 中，调用函数 InitG 一次后，函数 MakeG 应被恰好调用 $U$ 次。若函数 InitG 被调用两次，你的程序将被视为 Wrong Answer [6]。若在调用函数 InitG 之前调用了函数 MakeG，你的程序将被视为 Wrong Answer [7]。若在函数 Alice 结束时未调用函数 InitG，或函数 MakeG 未被调用 $U$ 次，你的程序将被视为 Wrong Answer [8]。当函数 Alice 结束时，若 Alice 描述的图 $G$ 不是一个简单图，你的程序将被视为 Wrong Answer [9]。

若对函数 Alice 的调用被视为 Wrong Answer，你的程序将立即终止。

第二个文件为 Bob.cpp。该文件在给定 Bob 收到的图 $G$ 的信息后，输出 JOI 王国的航线地图。它应实现以下函数。程序应包含头文件 Boblib.h。

• void Bob( int V, int U, int C[], int D[] )

  对于每个测试用例，该函数被调用一次。

  • 参数 $V$ 是图 $G$ 的顶点数。
  • 参数 $U$ 是图 $G$ 的边数。
  • 参数 $C[]$、$D[]$ 是长度为 $U$ 的序列，用于描述图 $G$ 的边。

通过以下函数，函数 Bob 恢复 JOI 王国的航线地图，并输出航线地图的信息。

• void InitMap( int N, int M )

  该函数指定 JOI 王国的岛屿数量和航线数量。

  • 参数 $N$ 是恢复出的 JOI 王国岛屿数量。$N$ 应为一个整数，且必须等于 JOI 王国实际的岛屿数量。若两者不相等，你的程序将被视为 Wrong Answer [10]。
  • 参数 $M$ 是恢复出的 JOI 王国航线数量。$M$ 应为一个整数，且必须等于 JOI 王国实际的航线数量。若两者不相等，你的程序将被视为 Wrong Answer [11]。

• void MakeMap( int A, int B )

  该函数指定 JOI 王国的航线数量。

  • 参数 $A$ 和 $B$ 表示存在一条连接岛屿 $A$ 与岛屿 $B$ 的航线。$A$ 和 $B$ 应为介于 $0$ 到 $N-1$（含）之间的整数，且应满足 $A \ne B$。若 $A$ 或 $B$ 不满足这些条件，你的程序将被视为 Wrong Answer [12]。若在 JOI 王国中不存在连接岛屿 $A$ 与岛屿 $B$ 的航线，你的程序将被视为 Wrong Answer [13]。由该函数调用所描述的航线应与之前调用所描述的航线不同。当调用 MakeMap( A, B ) 时，若此前已调用过 MakeMap( A, B ) 或 MakeMap( B, A )，你的程序将被视为 Wrong Answer [14]。

此处，$N$ 是由 InitMap 指定的整数值。

在函数 Bob 中，调用函数 InitMap 一次后，函数 MakeMap 应被恰好调用 $M$ 次。若函数 InitMap 被调用两次，你的程序将被视为 Wrong Answer [15]。若在调用函数 InitMap 之前调用了函数 MakeMap，你的程序将被视为 Wrong Answer [16]。若在函数 Bob 结束时未调用函数 InitMap，或函数 MakeMap 未被调用 $M$ 次，你的程序将被视为 Wrong Answer [17]。此处，$M$ 是由 InitMap 指定的整数值。

若对函数 Bob 的调用被视为 Wrong Answer，你的程序将立即终止。

评分流程

评分按以下方式进行。若你的程序被视为 Wrong Answer，它将立即终止。

（1）调用一次函数 Alice，其参数描述 JOI 王国的航线地图信息。

（2）设 $G$ 为由函数 Alice 指定的图。调用一次函数 Bob，其参数为图 $G$ 的顶点编号的随机重排和边编号的随机重排。

（3）你的程序被评分。

重要提示

• 你的程序可以为内部使用实现其他函数，或使用全局变量。提交的文件将与评分器一起编译，并生成一个可执行文件。所有全局变量和内部函数应声明为 static，以避免与其他文件冲突。评分时，程序将作为两个独立进程（Alice 进程和 Bob 进程）运行。Alice 进程与 Bob 进程之间不能共享全局变量。

• 你的程序不应使用标准输入和标准输出。你的程序不应通过任何方式与其他文件通信。但，你的程序可以向标准错误输出调试信息。

编译与测试运行

你可以从竞赛网页下载一个归档文件，其中包含用于测试你程序的样例评分器。该归档文件还包含你程序的一个样例源代码文件。

样例评分器由一个源文件组成，即 grader.cpp。若你的程序为 Alice.cpp 和 Bob.cpp，为测试它们，你需要将这些文件（grader.cpp、Alice.cpp、Bob.cpp、Alicelib.h 和 Boblib.h）放入同一目录，并运行以下命令来编译你的程序：

g++ -std=c++14 -O2 -o grader grader.cpp Alice.cpp Bob.cpp

当编译成功后，将生成可执行文件 grader。

请注意，实际评分器与样例评分器不同。样例评分器将以单个进程方式运行，它将从标准输入读取输入数据，并将结果写入标准输出。

输入格式

样例评分器从标准输入读取以下数据。

• 第一行包含两个以空格分隔的整数，表示 JOI 王国由 $N$ 个岛屿组成，且 JOI 王国共有 $M$ 条航线。
• 接下来的 $M$ 行包含航线地图的信息。第 $(i+1)$ 行（其中 $0 \le i \le M-1$）包含两个以空格分隔的整数 $A_i$、$B_i$，它们描述 JOI 王国航线地图的信息。

输出格式

当程序成功终止时，样例评分器将以下信息写入标准输出。（引号本身不会实际输出。）

• 若你的程序被视为 Wrong Answer，样例评分器将以如下格式输出其类型：“Wrong Answer [1]”，然后终止。
• 若对函数 Alice 和 Bob 的调用均未被视为 Wrong Answer，样例评分器将输出 “Accepted.”，并同时输出 $V$ 的值。

若你的程序被视为多种类型的 Wrong Answer，样例评分器仅报告其中一种。

提示

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 1000$。
• $0 \le M \le N(N-1)/2$。
• $0 \le A_i \le N-1$（其中 $0 \le i \le M-1$）。
• $0 \le B_i \le N-1$（其中 $0 \le i \le M-1$）。
• $A_i \ne B_i$（其中 $0 \le i \le M-1$）。
• $(A_i, B_i) \ne (A_j, B_j)$ 且 $(A_i, B_i) \ne (B_j, A_j)$（其中 $0 \le i < j \le M-1$）。

子任务

共有 3 个子任务。每个子任务的得分和附加约束如下：

子任务 1 [22 分]

• $N \le 10$。

子任务 2 [15 分]

• $N \le 40$。

子任务 3 [63 分]

无附加约束。

评分规则

• 在子任务 1 或子任务 2 中，若你的程序解决了所有测试用例，你将获得满分。

• 在子任务 3 中，若你的程序解决了所有测试用例，你的得分按以下方式计算。令 $\text{MaxDiff}$ 为 $V - N$ 的最大值：

  • 当 $101 \le \text{MaxDiff}$ 时，你的得分为 $0$。
  • 当 $21 \le \text{MaxDiff} \le 100$ 时，你的得分为 $13 + \left\lfloor \dfrac{100 - \text{MaxDiff}}{4} \right\rfloor$。此处，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
  • 当 $13 \le \text{MaxDiff} \le 20$ 时，你的得分为 $33 + (20 - \text{MaxDiff}) \times 3$。
  • 当 $\text{MaxDiff} \le 12$ 时，你的得分为 $63$。

翻译由 Qwen3-235B 完成