추론

사설 탐정 홍 씨가 맡은 살인 사건의 정보를 정리하고 있다. 사건 관계자의 행적을 모아 $n$개의 진술 $S_1, S_2, \dots, S_n$을 적었다. 각 진술이 참인지 거짓인지는 아직 모르므로 홍 씨는 진술 하나하나를 사건 변수라고 부른다. 아래 여섯 진술이 사건 변수의 예다.

1. $S_1$: 김철수는 개를 기른다.
2. $S_2$: 박수철은 고양이를 좋아한다.
3. $S_3$: 안희영은 박수철을 좋아한다.
4. $S_4$: (생략)
5. $S_5$: (생략)
6. $S_6$: (생략)

홍 씨는 사건 변수 각각의 참 거짓과 변수 사이의 관계를 조사해 그 결과로 추론을 세웠다. 추론은 주장 하나 이상으로 이루어지고, 주장은 모두 다음 세 유형 중 하나다. 유형 1은 사건 변수 $S_i$가 참이라는 주장이다. 유형 2는 사건 변수 하나 이상을 모은 집합에 거짓인 변수가 적어도 하나 있다는 주장이다. 유형 3은 $S_i$와 함께 적힌 변수가 모두 참이면 $S_i$도 참이라는 주장이다. 세 유형은 다음과 같이 쓴다.

1. 유형 1: $S_i$ ($S_i$는 참이다.)
2. 유형 2: $S_{i_1}, S_{i_2}, \dots, S_{i_k} \to \emptyset$ ($S_{i_1}, S_{i_2}, \dots, S_{i_k}$ 중 적어도 하나는 거짓이다.)
3. 유형 3: $S_{j_1}, S_{j_2}, \dots, S_{j_k} \to S_i$ ($S_{j_1}, S_{j_2}, \dots, S_{j_k}$가 모두 참이면 $S_i$도 참이다.)

예를 들어 홍 씨의 추론이 다음 여덟 주장으로 이루어졌다고 하자.

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$

주장 1과 2는 유형 1, 주장 3은 유형 2, 주장 4부터 8까지는 유형 3이다. 추론이 타당하려면 주장 사이에 모순이 없어야 하고, $\to$ 왼쪽 변수가 모두 참인데 오른쪽 변수는 거짓이어야 하는 유형 3 주장이 없어야 한다. $\to$ 왼쪽에 거짓인 변수가 하나라도 있으면 오른쪽 변수의 참 거짓은 추론의 타당성을 해치지 않는다.

타당한 배정은 추론을 타당하게 만드는 사건 변수의 참 거짓 배정이다. 홍 씨는 자기 추론에 타당한 배정이 있는지 알고 싶다.

위 예에서는 주장 1과 2로 $S_1$과 $S_2$가 참이고, 주장 4로 $S_6$도 참이 된다. 그런데 주장 3은 $S_1$, $S_2$, $S_6$ 중 하나가 거짓이기를 요구하므로 이 추론은 타당하지 않다. 주장 3을 빼면 타당한 배정이 있다. 모든 변수를 참으로 두어도 되고, $S_4$만 거짓으로 두어도 된다.

사건 변수 $n$개로 이루어진 홍 씨의 추론이 주어질 때, 타당한 배정이 있는지 판정하는 프로그램을 작성하시오.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 네 정수 $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$)이 주어진다. $n$은 사건 변수의 개수이고, $m_1$, $m_2$, $m_3$은 각각 유형 1, 유형 2, 유형 3 주장의 개수다.

다음 $m_1$개 줄에는 각각 정수 $i$ ($1 \le i \le n$)가 주어지며, 유형 1 주장 $S_i$를 뜻한다.

다음 $m_2$개 줄에는 각각 정수 $k+1$개 $k, i_1, i_2, \dots, i_k$ ($1 \le k$, $1 \le i_1, i_2, \dots, i_k \le n$, $r \ne s$이면 $i_r \ne i_s$)가 주어지며, 유형 2 주장 $S_{i_1}, S_{i_2}, \dots, S_{i_k} \to \emptyset$을 뜻한다.

다음 $m_3$개 줄에는 각각 정수 $k+2$개 $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$, $r \ne s$이면 $j_r \ne j_s$, 모든 $r$에 대해 $i \ne j_r$)가 주어지며, 유형 3 주장 $S_{j_1}, S_{j_2}, \dots, S_{j_k} \to S_i$를 뜻한다.

출력은 표준 출력으로 한다. 테스트 케이스마다 정확히 한 줄을 출력한다. 추론이 타당하면 YES를, 타당하지 않으면 NO를 출력한다.