← 返回题目列表

Codeforces · 1606/D

D. 红蓝矩阵

中文机器翻译题面 查看原题

给定一个矩阵,由 $$$n$$$ 行和 $$$m$$$ 列组成。第 $$$i$$$ 行的第 $$$j$$$ 个单元格包含一个整数 $$$a_{ij}$$$。

首先,您必须将矩阵的每一行着色为红色或蓝色,至少一行为红色,至少一行为蓝色。

然后,您必须选择一个整数 $$$k$$$ ($$$1 \le k < m$$$) 并以这样的方式切割彩色矩阵,使得前 $$$k$$$ 列成为单独的矩阵(左矩阵),最后 $$$m-k$$$ 列成为单独的矩阵(右矩阵)。

如果满足以下两个属性,则着色和剪裁被称为完美:

- 左侧矩阵中的每个红色单元格包含的整数大于左侧矩阵中的每个蓝色单元格;
- 右侧矩阵中的每个蓝色单元格包含的整数大于右侧矩阵中的每个红色单元格。

找到任何完美的着色和剪裁,或者报告没有。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 5 \cdot 10^5$$$; $$$n \cdot m \le 10^6$$$) - 分别是矩阵中的行数和列数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i1}, a_{i2}, \dots, a_{im}$$$ ($$$1 \le a_{ij} \le 10^6$$$)。

所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例打印一个答案。如果矩阵中没有完美的着色和切割,则打印“NO”。

否则,首先打印“YES”。然后是一个由 $$$n$$$ 字符组成的字符串:如果第 $$$i$$$ 行为红色,则第 $$$i$$$ 字符应为“R”;如果为蓝色,则第 $$$i$$$ 字符应为“B”。该字符串应至少包含一个“R”和至少一个“B”。最后,打印一个整数 $$$k$$$ ($$$1 \le k < m$$$) — 从左侧开始被剪切的列数。

示例

输入 #1

3
5 5
1 5 8 8 7
5 2 1 4 3
1 6 9 7 5
9 3 3 3 2
1 7 9 9 8
3 3
8 9 8
1 5 3
7 5 7
2 6
3 3 3 2 2 2
1 1 1 4 4 4

输出 #1

YES
BRBRB 1
NO
YES
RB 3

注意

第一个测试用例的着色和剪切: