Deduction

Hong, a private detective, is organizing the information about a murder case he is working on. From the movements of the people connected to the case he wrote down $n$ statements $S_1, S_2, \dots, S_n$. He does not yet know whether each statement is true, so he calls every statement an incident variable. The six statements below are an example.

1. $S_1$: Cheolsu Kim keeps a dog.
2. $S_2$: Sucheol Park likes cats.
3. $S_3$: Heeyoung Ahn likes Sucheol Park.
4. $S_4$: (omitted)
5. $S_5$: (omitted)
6. $S_6$: (omitted)

Hong examined the truth of each incident variable and the relations between the variables, and built a deduction from the result. A deduction is one or more assertions, and every assertion has one of three types. Type 1 says that an incident variable $S_i$ is true. Type 2 says that a set of one or more incident variables contains at least one false variable. Type 3 says that $S_i$ is true whenever the variables written with it are all true. The three types are written like this.

1. Type 1: $S_i$ ($S_i$ is true.)
2. Type 2: $S_{i_1}, S_{i_2}, \dots, S_{i_k} \to \emptyset$ (At least one of $S_{i_1}, S_{i_2}, \dots, S_{i_k}$ is false.)
3. Type 3: $S_{j_1}, S_{j_2}, \dots, S_{j_k} \to S_i$ (If $S_{j_1}, S_{j_2}, \dots, S_{j_k}$ are all true, then $S_i$ is also true.)

Suppose Hong's deduction is the following eight assertions.

1. $S_1$
2. $S_2$
3. $S_1, S_2, S_6 \to \emptyset$
4. $S_1 \to S_6$
5. $S_2 \to S_6$
6. $S_1, S_6 \to S_3$
7. $S_2, S_4 \to S_1$
8. $S_5, S_6 \to S_2$

Assertions 1 and 2 have Type 1, assertion 3 has Type 2, and assertions 4 to 8 have Type 3. The deduction is valid when the assertions do not contradict each other and no Type 3 assertion has every variable on the left of $\to$ true while the variable on its right must be false. If some variable on the left of $\to$ is false, the truth of the variable on the right does not break the deduction.

A valid assignment is an assignment of true and false to the incident variables that makes the deduction valid. Hong wants to know whether his deduction has a valid assignment.

In the example above, assertions 1 and 2 make $S_1$ and $S_2$ true, and assertion 4 then makes $S_6$ true. Assertion 3 requires one of $S_1$, $S_2$, $S_6$ to be false, so this deduction is not valid. Once assertion 3 is dropped, a valid assignment exists. Setting every variable to true works, and so does setting only $S_4$ to false.

Given Hong's deduction over $n$ incident variables, write a program that decides whether a valid assignment exists.

Your program reads from standard input. The first line has the number of test cases $T$. Each test case starts with a line of four integers $n$, $m_1$, $m_2$, $m_3$ ($1 \le n \le 1500$, $1 \le m_1 < n$, $0 \le m_2, m_3 \le 1500$), where $n$ is the number of incident variables and $m_1$, $m_2$, $m_3$ are the numbers of Type 1, Type 2 and Type 3 assertions.

Each of the next $m_1$ lines has one integer $i$ ($1 \le i \le n$) for the Type 1 assertion $S_i$.

Each of the next $m_2$ lines has $k+1$ integers $k, i_1, i_2, \dots, i_k$ ($1 \le k$, $1 \le i_1, i_2, \dots, i_k \le n$, and $i_r \ne i_s$ for $r \ne s$) for the Type 2 assertion $S_{i_1}, S_{i_2}, \dots, S_{i_k} \to \emptyset$.

Each of the next $m_3$ lines has $k+2$ integers $k, j_1, j_2, \dots, j_k, i$ ($1 \le k \le n-1$, $1 \le j_1, j_2, \dots, j_k, i \le n$, $j_r \ne j_s$ for $r \ne s$, and $i \ne j_r$ for every $r$) for the Type 3 assertion $S_{j_1}, S_{j_2}, \dots, S_{j_k} \to S_i$.

Your program writes to standard output. Print exactly one line for each test case. Print YES if the deduction is valid, and NO otherwise.