Migrated from Lutece 3211 布尔公式

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

lllei 想要帮你复习离散数学，于是有了以下问题：

一个完全量化的 2-CNF 是指一个满足以下条件的布尔公式：

1. 该公式具有以下形式：$Q_1x_1...Q_nx_nF(x_1, ..., x_n)$
2. 每个 $Q_i$ 都是量词，意即 $Q_i$ 代表 $\forall$（任意），或者 $\exists$（存在）
3. $F$ 首先是一个合取范式，并且每个子句都是二元的，即类似于这种形式：$(s_1 \lor t_1) \land (s_2 \lor t_2) ... (s_n \lor t_n)$。$F$ 的子句有 $m$ 个。

由于其公式是完全量化的（没有自由变元），该公式的值是确定的。

现在给你一个完全量化的 2-CNF，请你求出该公式的值。

Input

第一行一个整数，代表数据组数。

接下来对于每一组数据：

第一行有两个整数 $n, m$ 代表变元数量，子句数量。

接下来是一个具有 $n$ 个字符的字符串，对于第 $i$ 个字符，若为 A，代表 $Q_i$ 为 $\forall$；若为 E，代表 $Q_i$ 为 $\exists$。

接下来 $m$ 行，每行两个整数 $u_i, v_i$，代表第 $i$ 个子句的形式：

若 $u_i \ge 1$，则代表 $x_{u_i}$；若 $u_i \le -1$，则代表 $\overline{x_{u_i}}$。$v_i$ 的含义类似。

Output

对于每一组数据，输出 TRUE 或者 FALSE，代表每组公式的值。

Samples

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

Constraints

$1 \le t \le 10^5$

$1 \le n, m \le 10^5$

$-n \le u_i, v_i \le n; u_i, v_i \neq 0$

保证 $n$ 之和不超过 $10^5$，保证 $m$ 之和不超过 $10^5$

Note

第一组数据代表的 2-CNF 为：

$$\forall x_1 \exists x_2 (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor x_2) $$

第二组数据代表的 2-CNF 为：

$$\exists x_1 \forall x_2 (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor x_2) $$

第三组数据代表的 2-CNF 为：

$$\forall x_1 \exists x_2 \forall x_3 (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor \overline{x_3}) $$

Resources

2024 UESTC ICPC Training for Graph