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, \dots, V-1$ 中的一个编号，并为每条边分配 $0, 1, \dots, U-1$ 中的一个编号。
• Alice 指定参数 $C_0, C_1, \dots, C_{U-1}$ 和 $D_0, D_1, \dots, D_{U-1}$。这些参数描述了 $G$ 的边，即对于每个 $j$ ($0 \le j \le U-1$)，第 $j$ 条边连接顶点 $C_j$ 和顶点 $D_j$。
• $G$ 的顶点编号由 JOI 王国打乱。首先，JOI 王国生成一个序列 $p[0], p[1], \dots, p[V-1]$，它是 $0, 1, \dots, V-1$ 的一个排列。然后，$C_0, C_1, \dots, C_{U-1}$ 被替换为 $p[C_0], p[C_1], \dots, p[C_{U-1}]$，$D_0, D_1, \dots, D_{U-1}$ 被替换为 $p[D_0], p[D_1], \dots, p[D_{U-1}]$。
• 然后，$G$ 的边编号由 JOI 王国打乱。首先，JOI 王国生成一个序列 $q[0], q[1], \dots, q[U-1]$，它是 $0, 1, \dots, U-1$ 的一个排列。然后，$C_0, C_1, \dots, C_{U-1}$ 被替换为 $C_{q[0]}, C_{q[1]}, \dots, C_{q[U-1]}$，$D_0, D_1, \dots, D_{U-1}$ 被替换为 $D_{q[0]}, D_{q[1]}, \dots, D_{q[U-1]}$。
• 以下数据被发送给 Bob：$V$ 和 $U$ 的值，以及参数 $C_0, C_1, \dots, C_{U-1}$ 和 $D_0, D_1, \dots, D_{U-1}$ 的最新值。

注意，使用此电报机只能发送简单图。这里，简单图是指没有重边和自环的图。 换句话说，她可以发送满足以下条件的图：对于每一对 $i, j$ ($0 \le i < j \le U-1$)，满足 $(C_i, D_i) \neq (C_j, D_j)$ 且 $(C_i, D_i) \neq (D_j, C_j)$；对于每个 $i$ ($0 \le i \le U-1$)，满足 $C_i \neq D_i$。

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

实现细节

你需要提交两个文件。 第一个文件是 Alice.cpp。该文件输出 Alice 发送的图的信息。它应实现以下函数。程序应包含 Alicelib.h。

• void Alice( int N, int M, int A[], int B[] ) 对于每个测试用例，此函数被调用一次。
  • 参数 $N$ 是 JOI 王国的岛屿数量。
  • 参数 $M$ 是 JOI 王国的航线数量。
  • 参数 $A[], B[]$ 是长度为 $M$ 的序列，描述了 JOI 王国的航线图。

使用以下函数，函数 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 不应被调用超过一次。如果对于同一个 pos 调用超过一次，程序将被视为 Wrong Answer [4]。
  • 参数 $C$ 和 $D$ 是图 $G$ 中边 pos 的顶点。$C$ 和 $D$ 应为 $0$ 到 $V-1$ 之间的整数（包含边界）。此外，必须满足 $C \neq D$。如果 $C$ 或 $D$ 不满足这些条件，程序将被视为 Wrong Answer [5]。

在函数 Alice 中，调用一次 InitG 后，应恰好调用 MakeG $U$ 次。如果 InitG 被调用两次，程序将被视为 Wrong Answer [6]。如果 MakeG 在 InitG 之前被调用，程序将被视为 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 \neq B$。如果 $A$ 或 $B$ 不满足这些条件，程序将被视为 Wrong Answer [12]。如果 JOI 王国中不存在连接岛屿 $A$ 和岛屿 $B$ 的航线，程序将被视为 Wrong Answer [13]。通过此函数调用描述的航线应与之前调用描述的航线不同。当调用 MakeMap( A, B ) 时，如果之前已经调用过 MakeMap( A, B ) 或 MakeMap( B, A )，程序将被视为 Wrong Answer [14]。

在函数 Bob 中，调用一次 InitMap 后，应恰好调用 MakeMap $M$ 次。如果 InitMap 被调用两次，程序将被视为 Wrong Answer [15]。如果 MakeMap 在 InitMap 之前被调用，程序将被视为 Wrong Answer [16]。如果 Bob 终止时未调用 InitMap，或者 MakeMap 未被调用 $M$ 次，程序将被视为 Wrong Answer [17]。 如果对函数 Bob 的调用被视为 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 \neq B_i$ ($0 \le i \le M-1$)。 $(A_i, B_i) \neq (A_j, B_j)$ 且 $(A_i, B_i) \neq (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 + \lfloor \frac{100 - \text{MaxDiff}}{4} \rfloor$。这里，$\lfloor x \rfloor$ 是不超过 $x$ 的最大整数。
  • 当 $13 \le \text{MaxDiff} \le 20$ 时，得分为 $33 + (20 - \text{MaxDiff}) \times 3$。
  • 当 $\text{MaxDiff} \le 12$ 时，得分为 63。