P15936 [TOPC 2021] A Hard Problem

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.

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