Red-Blue Matrix

题意翻译

### 题意简述 给一个 $n$ 行 $m$ 列的矩阵，第 $i$ 行 $j$ 列的元素是 $a_{i,j}$。 现在要求把矩阵的每一行涂成红色或蓝色，要求至少有一行为红，一行为蓝。 将矩阵沿第 $k$ 列分割，第 $1$\~$k$ 列称作左矩阵，第 $k+1$\~$m$ 列称作右矩阵。分割方案要求满足： * 左矩阵中所有**红色**元素比所有**蓝色**元素大； * 右矩阵中所有**蓝色**元素比所有**红色**元素大； 求出一种染色及分割方案。 ### 输入格式 多组数据。第一行一个整数 $T\ (1\le T\le 1000)$ 表示数据组数。 对于每组数据，先是一行两个整数 $n,m\ (2 \le n, m \le 5 \cdot 10^5;\ n\cdot m\le 10^6)$，表示矩阵大小。 加下来 $n$ 行，每行 $m$ 个数，表示这个矩阵。 ### 输出格式 如果无解，输出一行 `NO`； 如果有解，先输出一行 `YES`，第二行输出一个长度为 $n$ 的，由 `R` 和 `B` 组成的字符串，表示每一行染成红色（`R`）还是蓝色（`B`）。最后输出满足题意的整数 $k$，也输出在第二行。

题目描述

You are given a matrix, consisting of $ n $ rows and $ m $ columns. The $ j $ -th cell of the $ i $ -th row contains an integer $ a_{ij} $ . First, you have to color each row of the matrix either red or blue in such a way that at least one row is colored red and at least one row is colored blue. Then, you have to choose an integer $ k $ ( $ 1 \le k < m $ ) and cut the colored matrix in such a way that the first $ k $ columns become a separate matrix (the left matrix) and the last $ m-k $ columns become a separate matrix (the right matrix). The coloring and the cut are called perfect if two properties hold: - every red cell in the left matrix contains an integer greater than every blue cell in the left matrix; - every blue cell in the right matrix contains an integer greater than every red cell in the right matrix. Find any perfect coloring and cut, or report that there are none.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of testcases. Then the descriptions of $ t $ testcases follow. The first line of each testcase contains two integers $ n $ and $ m $ ( $ 2 \le n, m \le 5 \cdot 10^5 $ ; $ n \cdot m \le 10^6 $ ) — the number of rows and the number of columns in the matrix, respectively. The $ i $ -th of the next $ n $ lines contains $ m $ integers $ a_{i1}, a_{i2}, \dots, a_{im} $ ( $ 1 \le a_{ij} \le 10^6 $ ). The sum of $ n \cdot m $ over all testcases doesn't exceed $ 10^6 $ .

输出格式

For each testcase print an answer. If there are no perfect colorings and cuts in the matrix, then print "NO". Otherwise, first, print "YES". Then a string, consisting of $ n $ characters: the $ i $ -th character should be 'R' if the $ i $ -th row is colored red and 'B' if it's colored blue. The string should contain at least one 'R' and at least one 'B'. Finally, print an integer $ k $ ( $ 1 \le k < m $ ) — the number of columns from the left that are cut.

输入输出样例

输入样例 #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

说明

The coloring and the cut for the first testcase: