Problem11165--矩形填充

11165: 矩形填充

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

一个 $n\times m$ 的网格,由黑色与白色格子组成。

在一次操作中,你可以选择任意两个相同颜色的格子,以这两个格子为对角的子矩形中所有格子都改成与它俩相同颜色。

形式化地说,如果你选中的两个格子坐标为 $(x_1,y_1),(x_2,y_2)$,颜色都是 $c$,满足 $\text{min}(x_1,x_2)≤x≤\text{max}(x_1,x_2),\ \text{min}(y_1,y_2)≤y≤\text{may}(y_1,y_2)$ 的所有坐标 $(x,y)$ 对应的格子都被改成颜色 $c$。

下图展现了两次操作:

请问,是否能通过若干次上述操作(也可以为 $0$ 次),将整个网格变成同一种颜色?你需要回答 $t$ 组询问。

Input

第一行为一个整数 $t$;

接下来为 $t$ 组询问,每组询问的组成如下:

第一行为两个整数 $n,m$;

接下来有 $n$ 行,每行 $m$ 个字符,$s_{ij}$ 表示第 $i$ 行第 $j$ 列的格子,为 W 表示白色,为 B 表示黑色。

Output

$t$ 行,第 $i$ 为对第 $i$ 组询问的回答,如果能做到,输出 YES,否则输出 NO

Constraints

$1 \leq t \leq 10^4$
$1 \leq n,m \leq 500$
题目保证所有的 $n \cdot m$ 之和不超过 $3 \cdot 10^5$。

Sample 1 Input

3
6 6
WWWWBW
WBWWWW
BBBWWW
BWWWBB
WWBWBB
BBBWBW
4 5
BBBBB
BBBBB
WWWWW
WWWWW
4 4
WWBW
BBWB
WWBB
BBBB

Sample 1 Output

YES
NO
YES

Source/Category