시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 24 18 60.000%

문제

이 퍼즐은 m개의 검은색 원판과, n개의 흰색 원판으로 이루어진 임의의 수열(sequence)이 타원형 모양의 트랙에 배치되어 있는 구조입니다. 또 이 게임에서는 플립(flip)이라는 동작을 할 수 있는 디스크를 이용할 수 있습니다. 플립은 임의의 세 연속된 디스크를 골라 그림과 같이 회전시켜서, 가운데 디스크는 그대로고 양 끝 디스크들의 위치를 바꾸는 동작을 말합니다. (Figure 1 참고) 플립을 할 때에는 트랙 위 어느 디스크를 중심으로도 회전시킬 수 있습니다.

 

fns.png

fns2.png

m개의 검은색 원판과 n개의 흰색 원판으로 이루어진 수열이 주어질 때, 플립을 유한 번 수행하여 (Figure 2처럼) 검은색 원판은 검은색 원판끼리, 흰색 원판은 흰색 원판끼리 한 곳에 연속적으로 모여 있는 상태를 만들 수 있을지 없을지 판단하는 프로그램을 작성하세요.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스는 한 줄로 이루어져 있습니다. 처음 주어진 수는 수열의 길이(10 ≤ m+n ≤ 30)이고, 그 다음 m개의 0(흰색 디스크)과 n개의 1(검은색 디스크)로 이루어진 수열이 주어집니다.  m+n 은 10 이상 30 미만입니다. 또한 각각의 수는 공백으로 구분됩니다.

출력

각 테스트 케이스마다, 흰색과 검은색 디스크들을 분리해 낼 수 있으면 YES를, 아니면 NO를 한 줄에 출력합니다.

예제 입력

2
18 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1
14 1 1 0 0 1 1 1 0 0 1 1 0 1 0

예제 출력

YES
NO

힌트