Red-Black Boolean Expression

Let $S$ be a set of $N$ boolean variables $X_1, X_2, \ldots, X_N$ and their negations $\neg X_1, \neg X_2, \ldots, \neg X_N$. You are given the initial values of all variables. A *2-CNF boolean expression* is defined as a [conjunction](https://en.wikipedia.org/wiki/Logical_conjunction) of clauses, where each clause is a [disjunction](https://en.wikipedia.org/wiki/Logical_disjunction) of two ele