seuOJ484 - 染色游戏（hard version）

题目描述

简单版将由新手组选手解决，简单版和困难版的唯一区别是需要解决的问题不同。

在一个叫做“异彩”的神秘世界里，颜色是一切的源泉。人们饮食、居住、学习、工作，乃至于情感表达与社交互动，都与颜色有着紧密的联系。每个人生而就有自己的颜色，这个颜色会在他们成长中得以延伸和深化，勾绘出这个人的性格、情感与经历。

在“异彩”世界中，人们将颜色与特定的情感或性格相联结，因此颜色也成为了判断或揣摩他人意图的一种方式。

在这个世界里，还有一种被称为“染色”的神秘力量。它能够改变事物原有的颜色，赋予新的含义，甚至能够改变整个世界的色彩。这种力量被一部分有能力掌握的人所独占和使用，被称为“染色师”。

"染色游戏"，就是在这样的背景下，由一群染色师发起的一个游戏。游戏的目标是通过操控颜色，完成各种复杂的任务，以最终决定谁能够掌握更高级的染色技巧。最终胜出者，会获得染色师之间的最高荣誉。

有一个 n×nn\times n 的网格，初始时网格中的所有的方格都是无色的。染色师每次会选择第 ii 行，第 jj 列的一个方格，并且把与这个方格同一行或同一列的所有方格都染成同一种颜色 cc，且每次新的染色会覆盖掉原先的颜色。可莉就是一名染色师，现在有人交个了她一个染色任务，她希望你能够告诉她按照什么顺序对网格进行染色，才能顺利完成染色任务。

输入格式

第一行，一个整数 t(1≤t≤10)t(1\le t\le 10)，代表数据组数。

对于每组数据：
第一行，一个整数 n(1≤n≤500)n(1\le n \le 500)，代表网格的大小。
接下来，一个 n×nn\times n 的方阵，其中第 ii 行第 jj 列的数字为 ci,j(0≤ci,j≤n×n)c_{i,j}(0\le c_{i,j}\le n\times n)，代表这个格子的颜色，如果 ci,j=0c_{i,j}=0，则代表这个格子没有染过色。

输出格式

对于每组数据，如果存在某种染色方式使得方阵网格可以被染成给出的染色任务形式，先输出一行 "YES"，然后输出一行正整数 m(0≤m≤2n)m(0\le m \le 2n)，代表你给出的染色方案操作次数。最后输出连续的 mm 行，每行四个整数 op,i,j,c(0≤op≤1;1≤i,j≤n;1≤c≤n×n)op,i,j,c(0\le op \le 1;1\le i,j \le n;1\le c \le n\times n) ,代表你当前染色的是行 (op=0op=0) 还是列 (op=1op=1) 与你选择的方格位置 (i,j)(i,j) 和你本次所染的颜色。

你不需要最小化 mm。

如果不存在任何染色方案，输出一行 "NO"。

任何满足题目要求的答案都会被判做正确的。

样例

输入样例：

4
2
0 1
1 1
3
2 2 2
0 2 3
3 2 3
2
0 0
0 0
2
1 2 
3 4

输出样例：

YES
2
0 2 2 1
1 2 2 1
YES
4
1 2 3 3
0 3 3 3
1 1 2 2
0 1 2 2
YES
0
NO