더 어려운 충족 가능성

완전 한정 불리언 2-CNF 식은 $Q_1 x_1 \dots Q_n x_n \, F(x_1, \dots, x_n)$ 형태이다. 각 $Q_i$는 전칭 한정자 $\forall$ (모든) 또는 존재 한정자 $\exists$ (존재한다) 중 하나이다. $F$는 $m$개의 절 $s \lor t$의 논리곱($\land$)이다. $s$와 $t$는 부정이 붙거나 붙지 않은 변수이며, 같은 변수일 수도 있다. 이 식에는 자유 변수가 없으므로 참 또는 거짓으로 평가된다.

다음 재귀 알고리즘으로 식을 평가할 수 있다.

1. 한정자가 없으면 나머지 식의 값(참 또는 거짓)을 반환한다.
2. 그렇지 않으면 $z = 0, 1$에 대해 $F_z = Q_2 x_2 \dots Q_n x_n \, F(z, x_2, \dots, x_n)$을 재귀적으로 평가한다.
3. $Q_1 = \exists$이면 $F_0 \lor F_1$을 반환한다. $Q_1 = \forall$이면 $F_0 \land F_1$을 반환한다.

주어진 완전 한정 2-CNF 식들이 참인지 판정하라.

첫 줄에 테스트 케이스의 수 $t$ ($1 \leq t \leq 10^5$)가 주어진다. 각 테스트 케이스의 첫 줄에는 변수의 수 $n$과 절의 수 $m$ ($1 \leq n, m \leq 10^5$)이 주어진다. 다음 줄에는 한정자를 나타내는 길이 $n$의 문자열 $s$가 주어진다. $s_i$가 A이면 $Q_i$는 $\forall$이고, E이면 $Q_i$는 $\exists$이다.

이어지는 $m$개의 줄에는 각각 두 정수 $u_i$, $v_i$ ($-n \leq u_i, v_i \leq n$, $u_i, v_i \neq 0$)가 주어진다. $u_i \geq 1$이면 절의 첫 번째 변수는 $x_{u_i}$이다. $u_i \leq -1$이면 첫 번째 변수는 $x_{-u_i}$의 부정이다. 두 번째 변수도 $v_i$로 같은 방식으로 나타낸다.

모든 테스트 케이스의 $n$ 합은 $10^5$을 넘지 않으며, $m$ 합도 $10^5$을 넘지 않는다.

각 테스트 케이스마다 식이 참이면 TRUE, 거짓이면 FALSE를 출력한다.

첫 번째 예제는 식 $\forall x_1 \exists x_2 \, (x_1 \lor x_2) \land (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 x_2) \land (x_1 \lor x_3)$이다. $x_1 = 1$, $x_3 = 1$을 대입하면 $x_2$의 어떤 값으로도 두 번째 절을 참으로 만들 수 없으므로 식은 거짓이다.