{"raw_statement":[{"iden":"background","content":"翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) H 题。"},{"iden":"statement","content":"我们定义一个“完全量化的布尔类型的 2-CNF 公式”（下简称 2-CNF）是以 $Q_1 x_1 \\ldots Q_n x_n F(x_1,\\ldots x_n)$ 构成的，$Q_i$ 只有两种，一种是“通用量词” $\\forall$，另一种是“存在量词” $\\exists$。然后 $F$ 是一个 $m$ 子句的 $s \\lor t$（$\\mathtt{OR}$ 运算） 的连词（$\\mathtt{AND}$ 运算），其中 $s$ 和 $t$ 不一定不同且不一定是否定（为 $\\texttt{false}$）。由于 2-CNF 公式是给定的，所以并没有自由变量（即答案固定为 $\\texttt{true}$ 或 $\\texttt{false}$）。\n\n至于计算 2-CNF 公式的值，我们可以使用一个简单的递归算法来求：\n\n- 如果没有量词（即 $\\forall$ 或 $\\exists$ ），则返回剩余表达式的返回值。\n\n- 否则，我们使用递归计算公式：$F_z = Q_2x_2 \\ldots Q_nx_n F(z,x_2,\\ldots,x_n)$，此处 $z = 0,1$。\n\n- 如果当前符号为 $\\exists$，则返回 $F_0 \\lor F_1$（$\\mathtt{OR}$ 运算）。否则符号为 $\\forall$ 返回 $F_0 \\land F_1$。\n"},{"iden":"input","content":"第一行是一个整数 $t (1 \\leq t \\leq 10^5)$，表示数据组数。\n\n接下来 $t$ 组数据，每组数据第一行两个整数 $n(1 \\leq n \\leq 10^5)$ 和 $m (1 \\leq m \\leq 10^5)$，$n$ 表示量词的长度，$m$ 表示在 $F$ 中的元素个数。\n\n然后一行，一串长度为 $n$ 的字符串 $s$，如果 $s_i = $ `A`，则 $Q_i = \\forall$，否则若 $s_i = $ `E`，则 $Q_i = \\exists$。\n\n接下来 $m$ 行，一行两个整数 $u_i,v_i(-n \\leq u_i,v_i \\leq n)$，如果 $u_i \\geq 1$ 则第 $i$ 个变量是 $x_{u_i}$，如果 $u_i \\leq -1$ 则第 $i$ 个变量是 $-(x_{-u_i})$，$v_i$ 同理。"},{"iden":"output","content":"对于每组数据，如果 2-CNF 公式为真输出 `TRUE`，否则输出 `FALSE`。"},{"iden":"note","content":"数据保证 $1 \\leq t \\leq 10^5$，$1 \\leq n,m \\leq 10^5$，$-n \\leq u_i,v_i \\leq n$。\n\n第一个 2-CNF 公式可以化简为 $\\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$，对于任意的 $x_1$ 都存在 $x_2 = \\overline{x_1}$ 使得答案为真。\n\n第二个 2-CNF 改变了公式的顺序，对于任意的 $x_1$，都可以选择 $x_2 = x_1$，使得表达式为 `FALSE`。\n\n第三个表达式是 $\\forall x_1 \\exists x_2 \\forall x_3 (x_1 \\lor \\overline{x_2}) \\land (\\overline{x_1} \\lor \\overline{x_3})$，如果令 $x_1 = 1$，$x_3 = 1$，则没有 $x_2$ 的值可以使得句子赋值为真，所以公式为假。"}],"translated_statement":null,"sample_group":[["3\n2 2\nAE\n1 -2\n-1 2\n2 2\nEA\n1 -2\n-1 2\n3 2\nAEA\n1 -2\n-1 -3\n","TRUE\nFALSE\nFALSE\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}