Background

Translated from Problem H of NERC 2018.

Problem Description

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

Input Format

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

Output Format

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

3
2 2
AE
1 -2
-1 2
2 2
EA
1 -2
-1 2
3 2
AEA
1 -2
-1 -3

TRUE
FALSE
FALSE

Hint

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