Hội Họa
Xem dạng PDFLà một họa sĩ tài ba, Văn được mời làm giám khảo cho một kỳ thi hội họa do VNOI tổ chức. Mỗi thí sinh tham gia sẽ phải tự mình vẽ lên một bức họa là một bảng hình lưới có kích thước ~n \times m~, với hàng được đánh số từ ~1~ đến ~n~ theo thứ tự từ trên xuống dưới, và cột được đánh số từ ~1~ đến ~m~ từ trái qua phải. Ô nằm ở hàng ~i~ và cột ~j~ trên lưới mang một giá trị số nguyên ~c_{i,j}~, biểu thị chỉ số màu của ô đó trong bức tranh. Văn sẽ là người thẩm định các bài dự thi và quyết định kết quả chung cuộc.
Tuy nhiên, trong thời đại AI phát triển mạnh mẽ, rất có khả năng một số thí sinh đã lợi dụng AI để làm giả bài thi của mình. Qua quá trình điều tra, Văn phát hiện ra cách AI được sử dụng để sinh ra bức tranh như sau:
AI xuất phát từ một bức vẽ trống, với mọi ô có màu ~c_{i,j} = 0~.
AI sử dụng một trong hai thao tác sau (không hoặc nhiều lần) để tô màu cho bức tranh:
Chọn một hàng bất kỳ (~1 \leq i \leq n~) và màu ~c~, tô các ô nằm trên hàng đó bằng màu ~c~.
Chọn một cột bất kỳ (~1 \leq j \leq m~) và màu ~c~, tô các ô nằm trên cột đó bằng màu ~c~.
Văn biết bạn là một kỹ sư tài năng, do đó Văn nhờ bạn kiểm tra xem bức tranh của thí sinh có thể là do AI tạo ra hay không, và nếu có thể, hãy đưa ra một trình tự bất kỳ các thao tác vẽ thỏa mãn để làm bằng chứng.
Input
Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \leq t \leq 100~) – số lượng testcase. Mô tả của mỗi test case như sau:
Dòng đầu tiên chứa hai số nguyên dương ~n, m~ (~1 \leq n, m \leq 1500~) – số lượng hàng và cột của lưới bảng vẽ.
Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên dương ~c_{i,1}, c_{i,2}, \ldots, c_{i,m}~ (~1 \le c_{i,j} \le n \cdot m~) – chỉ số màu của các ô nằm trên hàng thứ ~i~.
Đảm bảo rằng:
tổng của ~n~ qua các testcase không vượt quá ~1500~,
tổng của ~m~ qua các testcase không vượt quá ~1500~.
Output
Với mỗi test case, nếu chắc chắn rằng bài làm không phải do AI tạo ra, hãy in ra ~\mathtt{NO}~. Ngược lại,
Dòng đầu tiên, hãy in ra ~\mathtt{YES}~.
Dòng tiếp theo, hãy in ra một số nguyên ~k~ (~1 \leq k \leq 5000~) là số phép vẽ cần có cho bảng vẽ. Không yêu cầu cách vẽ phải tối ưu.
Mỗi dòng ~i~ trong ~k~ dòng tiếp theo hãy in ra ba số nguyên ~t, j, c~ (~t = 0~, ~1 \le j \le n~ hoặc ~t = 1~, ~1 \le j \le m~; ~1 \le c \le n \cdot m~) – mô tả thao tác vẽ thứ ~i~.
~t = 0~ với thao tác tô hàng, ~t = 1~ với thao tác tô cột,
~i~ là vị trí hàng hoặc cột của thao tác,
~c~ là chỉ số màu vẽ.
Nếu như tồn tại cách vẽ, có thể chứng minh rằng rằng cần không quá ~5000~ thao tác với giới hạn đã cho.
Nếu như có nhiều cách vẽ thỏa mãn, hãy in ra cách vẽ bất kỳ.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~500~ | ~\sum n, \sum m \leq 200~ |
| 2 | ~750~ | Không có ràng buộc gì thêm |
| Tổng | ~1250~ |
Sample Input 1
2
3 3
1 1 3
1 1 3
2 2 2
2 2
1 2
3 4
Sample Output 1
YES
4
0 1 1
0 2 1
1 3 3
0 3 2
NO
Sample Input 2
2
3 4
1 1 1 1
1 1 1 1
1 2 2 1
5 20
8 8 8 8 1 8 1 1 1 1 1 8 1 1 8 1 8 8 8 8
8 1 1 1 1 8 1 1 1 1 1 8 1 1 8 1 8 1 1 1
8 1 8 8 1 8 1 1 1 1 1 8 8 8 8 1 8 8 8 8
8 1 1 8 1 8 1 1 1 1 1 8 1 1 8 1 8 1 1 1
8 8 8 8 1 8 8 8 8 1 1 8 1 1 8 1 8 1 1 1
Sample Output 2
YES
6
1 4 1
1 3 2
1 2 2
1 1 1
0 2 1
0 1 1
NO
Notes
Dưới đây là hình minh họa cho test case thứ nhất của ví dụ đầu tiên.
Để vẽ được hình này ta cần ~4~ đường vẽ theo thứ tự như sau:
Kẻ màu ~1~ (màu đỏ trong hình) ở cột 1, 2
Kẻ màu ~3~ (màu xanh dương trong hình) ở cột 3
Kẻ màu ~2~ (màu xanh lá trong hình) ở hàng 3.
Dưới đây là minh họa cho test case thứ hai của ví dụ đầu tiên. Có thể thấy không có cách vẽ nào để tạo ra được bảng như trên. Đây là một bài làm hợp lệ.
Dưới đây là hình minh họa cho test case thứ hai của ví dụ thứ hai. Good luck!
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
easy