[ABC371] C - Make Isomorphic

C - Make Isomorphic

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 300 分

题面

给定两个简单无向图 和 ，它们都有 个顶点：顶点 、、、。图 有 条边，第 条边 连接顶点 和 。图 有 条边，第 条边 连接顶点 和 。

你可以对图 执行以下操作任意次，也可以不执行：

• 选择满足 的整数对 。支付 日元，如果 中顶点 和 之间没有边，则添加一条；如果有，则移除。

找到使 和 同构所需的最小总成本。

什么是简单无向图？

简单无向图 是一种没有自环或多重边的图，边没有方向。

图同构是什么意思？

具有 个顶点的两个图 和 同构 当且仅当存在排列 ，使得对于所有的 ：

• 中顶点 和 之间存在边 当且仅当 中顶点 和 之间存在边。

限制条件

• 所有输入值均为整数。

---

输入

输入格式如下，从标准输入中读入：

输出

输出答案。

---

输入样例 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

输出样例 1

9

给定的图如下：

例如，您可以对 执行以下四次操作，以 9 日元的成本使其同构于 。

• 选择 。 中顶点 和 之间存在边，因此支付 1 日元将其移除。
• 选择 。 中顶点 和 之间没有边，因此支付 2 日元添加它。
• 选择 。 中顶点 和 之间存在边，因此支付 1 日元将其移除。
• 选择 。 中顶点 和 之间没有边，因此支付 5 日元添加它。

执行这些操作后， 变为：

您无法以少于 9 日元的成本使 和 同构，因此输出 9。

---

输入样例 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

输出样例 2

3

例如，在 上执行操作 将使其同构于 。

---

输入样例 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

输出样例 3

5

例如，执行操作 一次将使 和 同构。

---

输入样例 4

2
0
0
371

输出样例 4

0

请注意 和 可能没有边。

同时，可能不需要任何操作。