Painting
View as PDFAs a talented artist, Van was invited to be a judge for a painting competition organized by VNOI. Each contestant must create a painting on a grid of size ~n \times m~, with rows numbered from ~1~ to ~n~ from top to bottom, and columns numbered from ~1~ to ~m~ from left to right. The cell in row ~i~ and column ~j~ on the grid has an integer value ~c_{i,j}~, representing the color index of that cell in the painting. Van will evaluate the submissions and decide the final results.
However, in this era of advanced AI, it is very likely that some contestants have exploited AI to forge their submissions. Through the investigation, Van discovered how AI was used to generate the painting as follows:
The AI starts from a blank canvas, with every cell colored ~c_{i,j} = 0~.
The AI uses one of the following operations (zero or multiple times) to color the painting:
Choose any row (~1 \leq i \leq n~) and color ~c~, coloring the cells in that row with color ~c~.
Choose any column (~1 \leq j \leq m~) and color ~c~, coloring the cells in that column with color ~c~.
Van knows you are a talented engineer, so he asks you to check whether the contestant's painting could have been created by AI, and if so, provide any sequence of drawing operations that satisfies this.
Input
Each test consists of multiple test cases. The first line of the dataset contains a positive integer ~t~ (~1 \leq t \leq 100~) – the number of test cases. The description of each test case is as follows:
The first line contains two positive integers ~n, m~ (~1 \leq n, m \leq 1500~) – the number of rows and columns of the painting grid.
The ~i~-th line in the next ~n~ lines contains ~m~ positive integers ~c_{i,1}, c_{i,2}, \ldots, c_{i,m}~ (~1 \le c_{i,j} \le n \cdot m~) – the color indices of the cells in the ~i~-th row.
It is guaranteed that:
the sum of ~n~ across test cases does not exceed ~1500~,
the sum of ~m~ across test cases does not exceed ~1500~.
Output
For each test case, if it is certain that the painting cannot be created by AI, print ~\mathtt{NO}~. Otherwise,
On the first line, print ~\mathtt{YES}~.
On the next line, print an integer ~k~ (~1 \leq k \leq 5000~), the number of drawing operations needed for the painting. The drawing method does not need to be optimal.
Each line ~i~ in the next ~k~ lines should print three integers ~t, j, c~ (~t = 0~, ~1 \le j \le n~ or ~t = 1~, ~1 \le j \le m~; ~1 \le c \le n \cdot m~) – describing the ~i~-th drawing operation.
~t = 0~ for row coloring, ~t = 1~ for column coloring,
~i~ is the row or column position of the operation,
~c~ is the color index.
If there is a way to draw, it can be shown that no more than ~5000~ operations are needed with the given constraints.
If there are multiple valid drawing methods, print any of them.
Scoring
| Subtask | Score | Constraints |
|---|---|---|
| 1 | ~500~ | ~\sum n, \sum m \leq 200~ |
| 2 | ~750~ | No additional constraints |
| Total | ~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
Below is an illustration for the first test case of the first example.
To draw this figure, we need ~4~ lines drawn in the following order:
Draw color ~1~ (red in the image) in columns 1 and 2
Draw color ~3~ (blue in the image) in column 3
Draw color ~2~ (green in the image) in row 3.
Below is an illustration for the second test case of the first example. It can be seen that there is no way to draw to create the table as shown above. This is a valid submission.
Below is an illustration for the second test case of the second example. Good luck!
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
easy