2280

2280. 最优标号

题目

给定一个无向图 $G=(V,E)$，每个顶点都有一个标号，它是一个 $[0,2^{31}-1]$ 内的整数。

不同的顶点可能会有相同的标号。

对每条边 $(u,v)$，我们定义其费用 $cost(u,v)$ 为 $u$ 的标号与 $v$ 的标号的异或值。

现在我们知道一些顶点的标号。

你需要确定余下顶点的标号使得所有边的费用和尽可能小。

输入格式

第一行有两个整数 $N,M$，$N$ 是图的点数，$M$ 是图的边数。

接下来有 $M$ 行，每行有两个整数 $u,v$，代表一条连接 $u,v$ 的边。

接下来有一个整数 $K$，代表已知标号的顶点个数。

接下来的 $K$ 行每行有两个整数 $u,p$，代表点 $u$ 的 标号 是 $p$。

假定这些 $u$ 不会重复。

所有点 编号 从 $1$ 到 $N$。

输出格式

输出一行一个整数，即最小的费用和。

数据范围

$1 \le N \le 500$,

$0 \le M \le 3000$,

$1 \le K \le N$

输入样例：

3 2
1 2
2 3
2
1 5
3 100

输出样例：

97

题解