AT_abc371_c.[ABC371C] Make Isomorphic

给定一个包含 $N$ 个顶点（顶点 $1,2,\ldots,N$）的简单无向图 $G$ 和 $H$。$G$ 有 $M_G$ 条边，第 $i$ 条边（$1\leq i\leq M_G$）连接顶点 $u_i$ 和顶点 $v_i$。$H$ 有 $M_H$ 条边，第 $i$ 条边（$1\leq i\leq M_H$）连接顶点 $a_i$ 和顶点 $b_i$。

你可以对图 $H$ 重复进行如下操作任意次（可以为 $0$ 次）：

• 选择一组整数 $(i,j)$，满足 $1\leq i<j\leq N$。支付 $A_{i,j}$ 日元，如果顶点 $i$ 和顶点 $j$ 之间没有边，则添加一条边；如果已经有边，则删除该边。

请你求出，为了使 $G$ 和 $H$ 同构，至少需要支付多少日元。

什么是简单无向图？简单无向图是指不包含自环和重边，且边没有方向的图。

什么是图的同构？对于 $N$ 个顶点的图 $G$ 和 $H$，如果存在一个排列 $(P_1,P_2,\ldots,P_N)$，使得对于任意 $1\leq i<j\leq N$，有：

• 当且仅当 $G$ 中存在连接顶点 $i$ 和顶点 $j$ 的边时，$H$ 中存在连接顶点 $P_i$ 和顶点 $P_j$ 的边，

则称 $G$ 和 $H$ 是同构的。

输入以如下格式从标准输入读入。

$N$ $M_G$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{M_G}$ $v_{M_G}$
$M_H$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{M_H}$ $b_{M_H}$
$A_{1,2}$ $A_{1,3}$ $\ldots$ $A_{1,N}$ $A_{2,3}$ $\ldots$ $A_{2,N}$
$\vdots$
$A_{N-1,N}$

请输出答案。

数据范围

• $1\leq N\leq 8$
• $0\leq M_G\leq\dfrac{N(N-1)}{2}$
• $0\leq M_H\leq\dfrac{N(N-1)}{2}$
• $1\leq u_i<v_i\leq N\ (1\leq i\leq M_G)$
• $(u_i,v_i)\neq(u_j,v_j)\ (1\leq i<j\leq M_G)$
• $1\leq a_i<b_i\leq N\ (1\leq i\leq M_H)$
• $(a_i,b_i)\neq(a_j,b_j)\ (1\leq i<j\leq M_H)$
• $1\leq A_{i,j}\leq 10^6\ (1\leq i<j\leq N)$
• 输入均为整数

样例解释 1

给定的图如下所示。

例如，可以对 $H$ 依次进行如下 $4$ 次操作，支付 $9$ 日元使 $G$ 和 $H$ 同构：

• 以 $(i,j)=(1,3)$ 进行操作。$H$ 中有顶点 $1$ 和 $3$ 的边，支付 $1$ 日元将其删除。
• 以 $(i,j)=(2,5)$ 进行操作。$H$ 中没有顶点 $2$ 和 $5$ 的边，支付 $2$ 日元将其添加。
• 以 $(i,j)=(1,5)$ 进行操作。$H$ 中有顶点 $1$ 和 $5$ 的边，支付 $1$ 日元将其删除。
• 以 $(i,j)=(3,5)$ 进行操作。$H$ 中没有顶点 $3$ 和 $5$ 的边，支付 $5$ 日元将其添加。

操作后，$H$ 如下所示。

无法用 $8$ 日元或更少使 $G$ 和 $H$ 同构，因此输出 9。

样例解释 2

例如，依次对 $(i,j)=(2,3),(2,4),(3,4)$ 进行 $3$ 次操作即可使 $G$ 和 $H$ 同构。

样例解释 3

例如，仅对 $(i,j)=(4,5)$ 进行 $1$ 次操作即可使 $G$ 和 $H$ 同构。

样例解释 4

$G$ 和 $H$ 也可能都没有边。也有可能不需要进行任何操作。

由 ChatGPT 4.1 翻译