23341번 - 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 ⊕ V_v∥ where ⊕ is the exclusive-or operator (equivalent to ^ in C) and ∥x∥ is the number of set bits in the binary representation non-negative integer x.

The node values V₁, V₂, ..., 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) ≠ 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 ∑_{u,v}∈EW_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₁, x₂, ..., x_n. For any k ∈ {1, 2, ..., 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 ≤ n ≤ 1000
• 1 ≤ m ≤ 5000
• -1 ≤ V_i < 2¹⁶
• 0 ≤ q ≤ 8
• t ∈ {0, 1}
• 0 ≤ u, v < n
• 0 ≤ i, j < 16