题目描述

You are given a simple undirected graph consisting of $n$ nodes and $m$ edges. The nodes are numbered from 1 to $n$, and the edges are numbered from 1 to $m$. Node $i$ has a non-negative integer value $V_i$ and the weight $W_{u,v}$ of edge $\{u, v\}$ is defined as $\| V_u \oplus V_v \|$ where $\oplus$ is the exclusive-or operator (equivalent to ^ in C) and $\| x \|$ is the number of set bits in the binary representation of non-negative integer $x$.

The node values $V_1, V_2, \dots, V_n$ must satisfy $q$ constraints. Each of the constraints can be represented as a 5-tuple $(t, u, i, v, j)$.

• if $t = 0$, then $getBit(V_u, i) = getBit(V_v, j)$
• if $t = 1$, then $getBit(V_u, i) \neq getBit(V_v, j)$

where the function $getBit(x, i)$ returns the $(i + 1)$-th least significant bit of $x$. For examples, $getBit(11, 0)$ is 1 and $getBit(11, 2) = 0$. In the C programming language, $getBit(x, i)$ can be computed by ((x >> i) & 1U) if $x$ is a 32-bit unsigned integer and $i$ is a non-negative integer at most 31.

Unfortunately, some node values are missing now. Your task is to assign new values to them to minimize $\sum_{\{u,v\} \in E} W_{u,v}$ without violating any given constraint. Please write a program to help yourself to complete this task.

输入格式

The input consists of five parts. The first part contains one line, and that line contains two positive integers $n$ and $m$. $n$ is the number of nodes, and $m$ is the number of edges. The second part contains $m$ lines. Each of them contains two integers $u$ and $v$, indicating an edge $\{u, v\}$ of the given graph. The third part contains one line. That line consists of $n$ space-separated integers $x_1, x_2, \dots, x_n$. For any $k \in \{1, 2, \dots, n\}$, if the node value $V_k$ is missing, $x_k$ will be -1; otherwise, $V_k$ is $x_k$. The fourth part contains one integer $q$, indicating the number of constraints. The fifth part contains $q$ lines, and each of them contains five space-separated integers $t, u, i, v, j$ indicating that $(t, u, i, v, j)$ is a constraint.

输出格式

Output an integer which is the minimum value under the $q$ constraints. If it is not possible to satisfy all the constraints, output -1.

4 4
1 3
1 2
3 2
0 3
-1 -1 60091 51514
2
1 2 0 1 5
0 2 6 0 15

13

3 2
0 1
1 2
-1 -1 -1
2
1 2 0 1 5
0 1 5 2 0

-1

提示

• $1 \leq n \leq 1000$
• $1 \leq m \leq 5000$
• $-1 \leq V_i < 2^{16}$
• $0 \leq q \leq 8$
• $t \in \{0, 1\}$
• $0 \leq u, v < n$
• $0 \leq i, j < 16$