Score : $300$ points

问题陈述

你得到了两个简单的无向图 $G$ 和 $H$，每个图都有 $N$ 个顶点：顶点 $1$, $2$, $\ldots$, $N$。图 $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$ 执行以下操作任意次数，可能为零次。

• 选择一对整数 $(i,j)$ 满足 $1\leq i<j\leq N$。支付 $A_{i,j}$ 日元，并且如果顶点 $i$ 和 $j$ 在 $H$ 中没有边，则添加一条；如果有，则移除它。

找出使 $G$ 和 $H$ 同构所需的最小总成本。

什么是简单的无向图？

简单无向图 是一个没有自环或多边的图，其中边没有方向。

图同构是什么意思？

如果存在一个排列 $(P_1,P_2,\ldots,P_N)$ 与 $(1,2,\ldots,N)$，使得对于所有 $1\leq i\lt j\leq N$：

• 如果图 $G$ 中顶点 $i$ 和 $j$ 之间存在边，则图 $H$ 中顶点 $P_i$ 和 $P_j$ 之间也存在边。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given simple undirected graphs $G$ and $H$, each with $N$ vertices: vertices $1$, $2$, $\ldots$, $N$. Graph $G$ has $M_G$ edges, and its $i$-th edge $(1\leq i\leq M_G)$ connects vertices $u_i$ and $v_i$. Graph $H$ has $M_H$ edges, and its $i$-th edge $(1\leq i\leq M_H)$ connects vertices $a_i$ and $b_i$.

You can perform the following operation on graph $H$ any number of times, possibly zero.

• Choose a pair of integers $(i,j)$ satisfying $1\leq i<j\leq N$. Pay $A_{i,j}$ yen, and if there is no edge between vertices $i$ and $j$ in $H$, add one; if there is, remove it.

Find the minimum total cost required to make $G$ and $H$ isomorphic.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multi-edges, where edges have no direction.

What does it mean for graphs to be isomorphic?

Two graphs $G$ and $H$ with $N$ vertices are isomorphic if and only if there exists a permutation $(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ such that for all $1\leq i\lt j\leq N$:

• an edge exists between vertices $i$ and $j$ in $G$ if and only if an edge exists between vertices $P_i$ and $P_j$ in $H$.

Constraints

• $1\leq N\leq8$
• $0\leq M _ G\leq\dfrac{N(N-1)}2$
• $0\leq M _ H\leq\dfrac{N(N-1)}2$
• $1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)$
• $(u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)$
• $1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)$
• $(a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)$
• $1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on $H$ to make it isomorphic to $G$ at a cost of $9$ yen.

• Choose $(i,j)=(1,3)$. There is an edge between vertices $1$ and $3$ in $H$, so pay $1$ yen to remove it.
• Choose $(i,j)=(2,5)$. There is no edge between vertices $2$ and $5$ in $H$, so pay $2$ yen to add it.
• Choose $(i,j)=(1,5)$. There is an edge between vertices $1$ and $5$ in $H$, so pay $1$ yen to remove it.
• Choose $(i,j)=(3,5)$. There is no edge between vertices $3$ and $5$ in $H$, so pay $5$ yen to add it.

After these operations, $H$ becomes:

You cannot make $G$ and $H$ isomorphic at a cost less than $9$ yen, so print 9.

Sample Input 2

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

Sample Output 2

3

For example, performing the operations $(i,j)=(2,3),(2,4),(3,4)$ on $H$ will make it isomorphic to $G$.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation $(i,j)=(4,5)$ once will make $G$ and $H$ isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that $G$ and $H$ may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

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

Sample Output 5

21214