Printing Sequences

시간 제한2초메모리 제한2048 MB

요약

값이 1부터 K까지이고 K가 3 이하인 목표 수열이 주어질 때, PRINT 문을 K개 이하로 써서 중첩 REP 반복문으로 그 수열을 출력하는 프로그램을 만들 수 있는지 판정한다.

난이도: 어려움10점 중 8점
유형: 분할 정복, 완전 탐색, 구현, 재귀
정답자: 아직 제출이 없습니다

문제

Bessie is learning to code using a simple programming language. She first defines a valid program, then executes it to produce some output sequence.

Defining:

A program is a nonempty sequence of statements.
A statement is either of the form "PRINT $c$ " where $c$ is an integer, or "REP $o$ ", followed by a program, followed by "END," where $o$ is an integer that is at least 1.

Executing:

Executing a program executes its statements in sequence.
Executing the statement "PRINT $c$ " appends $c$ to the output sequence.
Executing a statement starting with "REP $o$ " executes the inner program a total of $o$ times in sequence.

An example of a program that Bessie knows how to write is as follows.

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

The program outputs the sequence $\[1,2,2,1,2,2,1,2,2]$ .

Bessie wants to output a sequence of $N$ ( $1 \le N \le 100$ ) positive integers. Elsie challenges her to use no more than $K$ ( $1 \le K \le 3$ ) "PRINT" statements. Note that Bessie can use as many "REP" statements as she wants. Also note that each positive integer in the sequence is no greater than $K$ .

For each of $T$ ( $1 \le T \le 100$ ) independent test cases, determine whether Bessie can write a program that outputs some given sequence using at most $K$ "PRINT" statements.

입력

The first line contains $T$ .

The first line of each test case contains two space-separated integers, $N$ and $K$ .

The second line of each test case contains a sequence of $N$ space-separated positive integers, each at most $K$ , which is the sequence that Bessie wants to produce.

출력

For each test case, output "YES" or "NO" (case sensitive) on a separate line.

예제2

예제 1
입력
```
2
1 1
1
4 1
1 1 1 1
```
예상 출력
```
YES
YES
```

예제 2

입력

11
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3

예상 출력

YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO