Description

Alice 和 Bob 家门前有一片草坪，形状为一个长 $N$ 米、宽 $M$ 米的矩形。他们每年都会尝试修剪草坪，以呈现一些有趣的图案。以前他们使用手动剪刀修剪草坪，非常费时费力；但现在他们有了一台新的自动割草机，可以选择不同的割草高度，因此他们想尝试使用它。

这台新的割草机可以设定割草的高度：你可以将其设定为任意一个在 $1$ 到 $100$ 毫米之间的整数高度 $h$，然后它会将所有遇到的高度超过 $h$ 的草修剪到高度 $h$。使用时，你需要从草坪的任意一条边进入；割草机会沿着垂直于该边的直线，以 $1$ 米宽的路径穿过整个草坪，直到从对面的边缘离开草坪为止。割草机的高度只能在它离开草坪时重新设定。

Alice 和 Bob 设计了若干种想要实现的草坪图案。他们想知道，对于每个给定的草坪图案，是否能用新割草机修剪出来。每个图案通过给出草坪上每个 $1$m $\times$ $1$m 方格所希望的草高来描述。

草坪最开始的草高均为 $100$ 毫米。

Input Format

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $M$。接下来 $N$ 行，每行包含 $M$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列的草坪方格所希望的草高。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例的编号（从 $1$ 开始），$y$ 是单词 "YES" 或 "NO"（不含引号）。如果割草机能实现第 $x$ 个图案，输出 "YES"，否则输出 "NO"。

3
3 3
2 1 2
1 1 1
2 1 2
5 5
2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2
1 3
1 2 1

Case #1: YES
Case #2: NO
Case #3: YES

Hint

限制条件

• $1 \leq T \leq 100$

小数据集（10 分，测试集 1 - 可见）

• $1 \leq N, M \leq 10$
• $1 \leq a_{i,j} \leq 2$

大数据集（30 分，测试集 2 - 不可见）

• $1 \leq N, M \leq 100$
• $1 \leq a_{i,j} \leq 100$

翻译由 ChatGPT-4.5 完成。