P9798 [NERC 2018] Harder Satisfiability

Translated from Problem H of [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf).

We define a “fully quantified Boolean 2-CNF formula” (abbreviated as 2-CNF) as an expression of the form $Q_1 x_1 \ldots Q_n x_n F(x_1,\ldots x_n)$. Each $Q_i$ has only two possible values: the “universal quantifier” $\forall$ and the “existential quantifier” $\exists$. Then $F$ is a conjunction ($\mathtt{AND}$ operation) of $m$ clauses of the form $s \lor t$ ($\mathtt{OR}$ operation), where $s$ and $t$ are not necessarily different and are not necessarily negated (or $\texttt{false}$). Since the 2-CNF formula is fully specified, it has no free variables (that is, the final value is fixed as either $\texttt{true}$ or $\texttt{false}$). To evaluate a 2-CNF formula, we can use the following simple recursive algorithm: - If there is no quantifier (i.e., no $\forall$ or $\exists$), return the value of the remaining expression. - Otherwise, recursively compute: $F_z = Q_2x_2 \ldots Q_nx_n F(z,x_2,\ldots,x_n)$, where $z = 0,1$. - If the current quantifier is $\exists$, return $F_0 \lor F_1$ ($\mathtt{OR}$ operation). Otherwise, if it is $\forall$, return $F_0 \land F_1$.

The first line contains an integer $t (1 \leq t \leq 10^5)$, the number of test cases. Then follow $t$ test cases. For each test case, the first line contains two integers $n(1 \leq n \leq 10^5)$ and $m (1 \leq m \leq 10^5)$. Here, $n$ is the number of quantifiers, and $m$ is the number of clauses in $F$. The next line contains a string $s$ of length $n$. If $s_i =$ `A`, then $Q_i = \forall$; if $s_i =$ `E`, then $Q_i = \exists$. In the next $m$ lines, each line contains two integers $u_i,v_i(-n \leq u_i,v_i \leq n)$. If $u_i \geq 1$, then the literal is $x_{u_i}$; if $u_i \leq -1$, then the literal is $-(x_{-u_i})$. The same applies to $v_i$.

For each test case, if the 2-CNF formula is true, output `TRUE`; otherwise output `FALSE`.

The testdata guarantees $1 \leq t \leq 10^5$, $1 \leq n,m \leq 10^5$, and $-n \leq u_i,v_i \leq n$. The first 2-CNF formula can be simplified to $\forall x_1 \exists x_2(x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor x_2) = \forall x_1 \exists x_2 x_1 \oplus x_2$. For any $x_1$, there exists $x_2 = \overline{x_1}$ that makes the result true. The second 2-CNF changes the order of the formula. For any $x_1$, you can choose $x_2 = x_1$, making the expression `FALSE`. The third expression is $\forall x_1 \exists x_2 \forall x_3 (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor \overline{x_3})$. If we set $x_1 = 1$ and $x_3 = 1$, then there is no value of $x_2$ that can make the sentence evaluate to true, so the formula is false. Translated by ChatGPT 5