Alice và Bob có một bãi cỏ trước nhà, hình dạng là một hình chữ nhật kích thước \(N\) mét x \(M\) mét. Mỗi năm, họ cố gắng cắt cỏ theo một số hoa văn thú vị. Họ từng cắt bằng kéo, việc này rất tốn thời gian; nhưng giờ họ đã có một chiếc máy cắt cỏ tự động mới với nhiều chế độ cài đặt, và họ muốn dùng thử nó.

Máy cắt cỏ mới có cài đặt độ cao - bạn có thể đặt nó ở bất kỳ độ cao \(h\) nào từ 1 đến 100 milimét, và nó sẽ cắt tất cả cỏ cao hơn \(h\) mà nó đi qua xuống độ cao \(h\). Bạn vận hành nó bằng cách đưa máy vào bãi cỏ từ bất kỳ phần nào của mép bãi cỏ; sau đó máy cắt cỏ sẽ đi theo một đường thẳng, vuông góc với mép bãi cỏ mà nó đã đi vào, cắt cỏ trong một dải rộng 1m, cho đến khi nó ra khỏi bãi cỏ ở phía bên kia. Độ cao của máy cắt cỏ chỉ có thể được cài đặt khi nó không ở trên bãi cỏ.

Alice và Bob có một số hoa văn cỏ khác nhau mà họ có thể có trên bãi cỏ của mình. Đối với mỗi hoa văn đó, họ muốn biết liệu có thể cắt cỏ thành hoa văn này bằng máy cắt cỏ mới của họ hay không. Mỗi hoa văn được mô tả bằng cách chỉ định độ cao của cỏ trên mỗi ô vuông 1m x 1m của bãi cỏ.

Ban đầu, cỏ cao 100mm trên toàn bộ bãi cỏ.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên: \(N\) và \(M\). Tiếp theo là \(N\) dòng, với dòng thứ \(i\) chứa \(M\) số nguyên \(a_{i,j}\), mỗi số \(a_{i,j}\) mô tả độ cao mong muốn của cỏ ở ô thứ \(j\) của hàng thứ \(i\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là từ "YES" nếu có thể tạo ra hoa văn thứ x bằng máy cắt cỏ, hoặc "NO" nếu không thể.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le N, M \le 10\).

• \(1 \le a_{i,j} \le 2\).

• Large dataset (Test set 2 - Hidden):

• \(1 \le N, M \le 100\).
• \(1 \le a_{i,j} \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2013, Vòng loại, bài Lawnmower.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.