全量化布尔 2-CNF 公式具有以下形式：$Q_1x_1 \dots Q_nx_n F(x_1, \dots, x_n)$。 其中每个 $Q_i$ 是两个量词之一：全称量词 $\forall$（“对于所有”），或存在量词 $\exists$（“存在”）；$F$ 是 $m$ 个子句 $s \lor t$（布尔或）的合取（布尔与），其中 $s$ 和 $t$ 是某些变量（不一定不同），可能带有或不带有否定。该公式没有自由变量，因此其求值结果为 true 或 false。我们可以通过一个简单的递归算法来评估给定的全量化公式：
- 如果没有量词，返回剩余表达式的值 true 或 false。
- 否则，递归评估公式：$F_z = Q_2x_2 \dots Q_nx_n F(z, x_2, \dots, x_n)$，其中 $z = 0, 1$。
- 如果 $Q_1 = \exists$，返回 $F_0 \lor F_1$；否则如果 $Q_1 = \forall$，返回 $F_0 \land F_1$。
给定一些全量化布尔 2-CNF 公式，判断它们是否为真。
输入格式
第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示变量的数量和 $F$ 中子句的数量。下一行包含一个长度为 $n$ 的字符串 $s$，描述量词。如果 $s_i = \text{'A'}$，则 $Q_i$ 是全称量词 $\forall$；否则如果 $s_i = \text{'E'}$，则 $Q_i$ 是存在量词 $\exists$。 接下来的 $m$ 行描述 $F$ 中的子句。每行包含两个整数 $u_i$ 和 $v_i$ ($-n \le u_i, v_i \le n; u_i, v_i \neq 0$)。如果 $u_i \ge 1$，则第 $i$ 个子句中的第一个变量是 $x_{u_i}$。否则，如果 $u_i \le -1$，则第一个变量是 $\neg x_{-u_i}$（即 $x_{-u_i}$ 的否定）。第二个变量在第 $i$ 个子句中的描述方式相同。
所有测试用例的 $n$ 之和不超过 $10^5$；所有测试用例的 $m$ 之和不超过 $10^5$。
输出格式
对于每个测试用例，如果给定的公式为真，则输出 “TRUE”，否则输出 “FALSE”。
样例
输入 1
3 2 2 AE 1 -2 -1 2 2 2 EA 1 -2 -1 2 3 2 AEA 1 -2 -1 -3
输出 1
TRUE FALSE FALSE
说明
第一个样例对应公式 $\forall x_1 \exists x_2 (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_2) = \forall x_1 \exists x_2 x_1 \oplus x_2$。对于任意 $x_1$，我们可以选择 $x_2 = x_1$ 使其为真，因此该公式为真。
第二个样例改变了量词的顺序。现在答案是 “FALSE”，因为对于 $x_1$ 的任何值，我们都可以选择 $x_2 = x_1$，公式变为假。
第三个公式是 $\forall x_1 \exists x_2 \forall x_3 (x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_3)$。如果我们代入 $x_1 = 1, x_3 = 1$，则没有任何 $x_2$ 的赋值能使第二个子句为真，因此该公式为假。