使两图同构

题目描述

给定两个简单无向图 $G$ 和 $H$，它们各有 $N$ 个顶点：顶点 $1, 2, \ldots, N$。 图 $G$ 有 $M_G$ 条边，第 $i$ 条边 $(1 \le i \le M_G)$ 连接顶点 $u_i$ 和 $v_i$。 图 $H$ 有 $M_H$ 条边，第 $i$ 条边 $(1 \le i \le M_H)$ 连接顶点 $a_i$ 和 $b_i$。

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

选择一对整数 $(i,j)$ 满足 $1 \le i \lt j \le N$。支付 $A_{i,j}$ 日元，如果图 $H$ 中顶点 $i$ 和 $j$ 之间没有边则添加一条，如果有则删除。

求使 $G$ 与 $H$ 同构所需的最小总费用。

什么是简单无向图？

简单无向图是指没有自环和重边、边没有方向的图。

两个图同构是什么意思？

两个各有 $N$ 个顶点的图 $G$ 和 $H$ 同构，当且仅当存在 $(1, 2, \ldots, N)$ 的一个排列 $(P_1, P_2, \ldots, P_N)$，使得对所有 $1 \le i \lt j \le N$：

图 $G$ 中顶点 $i$ 和 $j$ 之间存在边，当且仅当图 $H$ 中顶点 $P_i$ 和 $P_j$ 之间存在边。

输入格式

输入按以下格式从标准输入给出：

$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}$

输出格式

输出答案。

样例

5
4
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
1 5
3 1 4 1
5 9 2
6 5
3

9

例如，可以对 $H$ 进行以下四次操作，花费 9 日元使其与 $G$ 同构。

• 选择 $(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 日元添加它。

无法以少于 9 日元的费用使 $G$ 与 $H$ 同构，因此输出 9。

5
3
1 2
2 3
3 4
4
1 2
2 3
3 4
4 5
9 1 1 1
1 1 1
1 1
9

3

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

5
3
1 2
2 3
3 4
4
1 2
2 3
3 4
4 5
5 4 4 4
4 4 4
4 4
5

5

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

2
0
0
371

0

注意 $G$ 和 $H$ 可能没有边。也可能不需要任何操作。

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

21214

数据范围

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