题目背景

原题为 P11838 [USACO25FEB] Printing Sequences B

题目描述

Gooby 发明了一个全新的编程语言——G语言。这门语言主要用来输出一系列数字序列。

定义：

一个程序是一个非空的语句序列。

一个语句的形式或者是 "PRINT $c$"，其中 $c$ 是一个整数，表示输出一个整数 $c$。 或者是 "REP $o$"，随后是一段程序，随后是 "END"，其中 $o$ 是一个不小于 1 的整数，表示循环语句，意思是将被 “REP” 和 “END” 括起来的语句执行 $o$ 遍。

演示：

例如 Gooby 编写了下面这段程序。

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

该程序输出序列为 $[1,2,2,1,2,2,1,2,2]$。

现在 Gooby 想要输出一个包含 $N$（$1 \le N \le 100$）个正整数的序列。他希望使用不超过 $K$（$1 \le K \le 3$）个 "PRINT" 语句。但是 Gooby 可以使用任意数量的 "REP" 语句。同时注意，序列中的每个正整数都不超过 $K$。

对于 $T$（$1 \le T \le 100$）个独立的测试用例中的每一个，求 Gooby 是否可以编写一个程序，使用至多 $K$ 个 "PRINT" 语句输出给定的序列。

输入格式

输入的第一行包含 $T$。

每一个测试用例的第一行包含空格分隔的两个整数 $N$ 和 $K$。

每一个测试用例的第二行包含一个由 $N$ 个空格分隔的正整数组成的序列，每个数都不超过 $K$，为 Gooby 想要输出的序列。

输出格式

对于每一个测试用例输出一行，如果能够做到，就输出 YES，否则输出 NO。

输入输出样例 #1

输入 #1

2
1 1
1
4 1
1 1 1 1

输出 #1

YES
YES

输入输出样例 #2

输入 #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

输出 #2

YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO

输入输出样例 #3

样例3下载

说明/提示

样例 1 解释：

对于第二个测试用例，以下代码使用了 $1$ 个 "PRINT" 语句输出了序列 $[1,1,1,1]$。

REP 4
    PRINT 1
END

样例 2 解释：

对于第一个测试用例，以下代码使用了 $2$ 个 "PRINT" 语句输出了序列 $[1,2,2,2]$。

PRINT 1
REP 3
    PRINT 2
END

对于第二个测试用例，答案是 "NO"，因为使用不超过 $2$ 个 "PRINT" 语句输出序列 $[1,1,2,1]$ 是不可能的。

对于第六个测试用例，以下代码使用了 $3$ 个 "PRINT" 语句输出了序列 $[3,3,1,2,2,1,2,2]$。

REP 2
    PRINT 3
END
REP 2
    PRINT 1
    REP 2
        PRINT 2
    END
END

• 测试点 $1$：$K=1$。
• 测试点 $2\sim 5$：$K \le 2$。
• 测试点 $6\sim 10$：没有额外限制。