SP5142 PAIRGRPH - A Pair of Graphs

我们认为两个图是等价的，当且仅当它们的节点能够通过一一对应关系配对，并且在这种配对下它们的边完全一致。现给定两个无向简单图 $A$ 和 $B$，它们的顶点数量相同。请找到一系列操作，使得两个图能变得等价，并且这些操作的总成本最低。操作有以下两种类型： - **添加任意边 $(x, y)$：** 此操作的前提是这条边之前不存在。添加操作在图 $A$ 上的成本为 $I_A$，在图 $B$ 上的成本为 $I_B$。 - **删除已存在的边 $(x, y)$：** 删除操作在图 $A$ 上的成本为 $D_A$，在图 $B$ 上的成本为 $D_B$。

输入包括若干个测试用例。 每个测试用例以三个整数 $N$、$M_A$ 和 $M_B$ 开始，分别表示顶点的总数、图 $A$ 中的边数以及图 $B$ 中的边数。其中 $1 \le N \le 8$，$0 \le M_A, M_B \le \frac{N(N-1)}{2}$。 接下来是四个整数 $I_A$、$I_B$、$D_A$ 和 $D_B$，分别代表在两个图上进行相应操作的成本，限制为 $0 \le I_A, I_B, D_A, D_B \le 32767$。 接下来的 $M_A + M_B$ 行描述了图 $A$ 和图 $B$ 的边信息。每行有两个整数 $X$ 和 $Y$，表示一条边的两个顶点，满足 $X \ne Y$ 和 $0 \le X, Y < N$。 测试用例之间用一个空行隔开。若遇到 $N = 0$，$M_A = 0$，且 $M_B = 0$，则表示文件结束，不需要处理。

输出每个测试用例的最小成本结果。

- 每个图的顶点数 $N$ 满足 $1 \le N \le 8$。 - 图 $A$ 和图 $B$ 中的边数 $M_A, M_B$ 满足 $0 \le M_A, M_B \le \frac{N(N-1)}{2}$。 - 操作成本 $I_A, I_B, D_A, D_B$ 满足 $0 \le I_A, I_B, D_A, D_B \le 32767$。 **本翻译由 AI 自动生成**