A Hard Problem

$n$개의 정점과 $m$개의 간선으로 이루어진 단순 무향 그래프가 주어진다. 정점은 $1$부터 $n$까지, 간선은 $1$부터 $m$까지 번호가 매겨진다. 정점 $i$는 음이 아닌 정수 값 $V_i$를 가지며, 간선 $\{u, v\}$의 가중치 $W_{u,v}$는 $\lVert V_u \oplus V_v \rVert$로 정의된다. 여기서 $\oplus$는 배타적 논리합 연산자(C 언어의 ^에 해당)이고, $\lVert x \rVert$는 음이 아닌 정수 $x$의 이진 표현에 포함된 1의 개수다.

정점 값 $V_1, V_2, \ldots, V_n$은 $q$개의 제약을 만족해야 한다. 각 제약은 5-튜플 $(t, u, i, v, j)$로 나타낼 수 있다.

• $t = 0$이면 $\textit{getBit}(V_u, i) = \textit{getBit}(V_v, j)$
• $t = 1$이면 $\textit{getBit}(V_u, i) \neq \textit{getBit}(V_v, j)$

여기서 함수 $\textit{getBit}(x, i)$는 $x$의 $(i + 1)$번째로 낮은 비트를 반환한다. 예를 들어 $\textit{getBit}(11, 0)$은 1이고 $\textit{getBit}(11, 2) = 0$이다. C 언어에서 $x$가 32비트 부호 없는 정수이고 $i$가 31 이하의 음이 아닌 정수라면, $\textit{getBit}(x, i)$는 ((x >> i) & 1U)로 계산할 수 있다.

아쉽게도 일부 정점의 값이 지금은 없다. 당신의 과제는 주어진 제약을 위반하지 않으면서 $\sum_{\{u,v\} \in E} W_{u,v}$를 최소화하도록 그 정점들에 새 값을 할당하는 것이다. 이 과제를 해결하는 프로그램을 작성하라.

입력은 다섯 부분으로 이루어진다. 첫 번째 부분은 한 줄로, 두 양의 정수 $n$과 $m$을 포함한다. $n$은 정점의 수, $m$은 간선의 수다. 두 번째 부분은 $m$개의 줄로 이루어진다. 각 줄은 두 정수 $u$와 $v$를 포함하며, 주어진 그래프의 간선 $\{u, v\}$를 나타낸다. 세 번째 부분은 한 줄로 이루어진다. 그 줄은 공백으로 구분된 $n$개의 정수 $x_1, x_2, \ldots, x_n$으로 이루어진다. 임의의 $k \in \{1, 2, \ldots, n\}$에 대해 정점 값 $V_k$가 없으면 $x_k$는 -1이고, 그렇지 않으면 $V_k$는 $x_k$이다. 네 번째 부분은 하나의 정수 $q$를 포함하며, 제약의 수를 나타낸다. 다섯 번째 부분은 $q$개의 줄로 이루어지고, 각 줄은 공백으로 구분된 다섯 개의 정수 $t, u, i, v, j$를 포함하며 $(t, u, i, v, j)$가 제약임을 나타낸다.

$q$개의 제약 아래에서 최솟값을 정수로 출력한다. 모든 제약을 만족하는 것이 불가능하면 -1을 출력한다.

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