이력 청소 가능한 DFA

결정적 유한 오토마타(DFA)는 유한한 입력 문자열을 받아 수락하거나 거절하는 유한 상태 기계다. 위 그림은 DFA 하나를 상태 다이어그램으로 그린 것이다. 이 오토마타에는 원으로 그린 상태 $S_0$, $S_1$, $S_2$가 있고, 입력으로 0과 1로 이루어진 유한 수열을 읽는다. 모든 상태에는 0으로 나가는 화살표와 1로 나가는 화살표가 하나씩 있어서, 기호를 하나 읽을 때마다 현재 상태에서 그 화살표가 가리키는 상태로 옮겨 간다. 예를 들어 상태가 $S_0$이고 읽은 기호가 1이면 $S_1$로 옮겨 가고, 이를 $\delta(S_0, 1) = S_1$로 쓴다. 이 표기를 문자열 전체로 확장하면 $\delta(S_0, 10) = S_2$나 $\delta(S_1, 011010) = S_0$ 같은 식을 쓸 수 있다.

DFA에는 아무 데서도 오지 않는 화살표로 표시하는 시작 상태와 이중 원으로 표시하는 수락 상태 집합이 있다. 시작 상태가 $q_0$인 DFA는 $\delta(q_0, w)$가 수락 상태일 때, 그리고 그때만 문자열 $w$를 수락한다. 위 그림에서 $S_0$은 시작 상태이면서 수락 상태이고, 이 DFA는 빈 문자열을 포함해 3의 배수인 이진수만 수락한다.

이제 상태가 $S_0, S_1, \dots, S_{n-1}$인 DFA $D$를 생각하자. 모든 $i, j \in \{0, \dots, n-1\}$에 대해 $\delta(S_i, w) = \delta(S_j, w)$가 성립하면 문자열 $w$를 $D$의 이력 청소 문자열이라고 한다. 즉 어느 상태에서 출발하든 $w$를 읽고 나면 DFA가 공통된 상태 하나에 놓인다. $D$의 이력 청소 문자열이 하나라도 존재하면 $D$를 이력 청소 가능이라고 한다. 0과 1로 이루어진 수열을 입력으로 받는 DFA가 주어질 때, 이 DFA가 이력 청소 가능인지 판정하시오.

첫 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 500$). 각 테스트 케이스의 첫 줄에는 상태가 $S_0, S_1, \dots, S_{n-1}$인 DFA의 상태 개수 $n$이 주어진다 ($2 \le n \le 500$). 둘째 줄에는 $n$개의 정수 $a_0, a_1, \dots, a_{n-1}$이, 셋째 줄에는 $n$개의 정수 $b_0, b_1, \dots, b_{n-1}$이 공백으로 구분되어 주어진다 ($0 \le a_i, b_i < n$). 이는 $0 \le i < n$인 모든 $i$에 대해 $\delta(S_i, 0) = S_{a_i}$, $\delta(S_i, 1) = S_{b_i}$라는 뜻이다.

각 테스트 케이스마다 그 DFA의 답을 한 줄에 출력한다. 이력 청소 가능하면 YES를, 그렇지 않으면 NO를 출력한다.