Rectangle Filling
Contest: Codeforces Round 941 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, implementation

There is an $$$n \times m$$$ grid of white and black squares. In one operation, you can select any two squares of the same color, and color all squares in the subrectangle between them that color.

Formally, if you select positions $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, both of which are currently the same color $$$c$$$, set the color of all $$$(x, y)$$$ where $$$\min(x_1, x_2) \le x \le \max(x_1, x_2)$$$ and $$$\min(y_1, y_2) \le y \le \max(y_1, y_2)$$$ to $$$c$$$.

This diagram shows a sequence of two possible operations on a grid:

Is it possible for all squares in the grid to be the same color, after performing any number of operations (possibly zero)?

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500$$$) — the number of rows and columns in the grid, respectively.

Each of the next $$$n$$$ lines contains $$$m$$$ characters 'W' and 'B' — the initial colors of the squares of the grid.

It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.

Output format:
For each test case, print "YES" if it is possible to make all squares in the grid the same color, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, it is impossible to ever change the color of any square with an operation, so we output NO.

The second example is the case pictured above. As shown in that diagram, it is possible for all squares to be white after two operations, so we output YES.

In the third and fourth examples, all squares are already the same color, so we output YES.

In the fifth example we can do everything in two operations. First, select positions $$$(2, 1)$$$ and $$$(1, 4)$$$ and color all squares with $$$1 \le x \le 2$$$ and $$$1 \le y \le 4$$$ to white. Then, select positions $$$(2, 1)$$$ and $$$(3, 4)$$$ and color all squares with $$$2 \le x \le 3$$$ and $$$1 \le y \le 4$$$ to white. After these two operations all squares are white.

Example input:
8
2 1
W
B
6 6
WWWWBW
WBWWWW
BBBWWW
BWWWBB
WWBWBB
BBBWBW
1 1
W
2 2
BB
BB
3 4
BWBW
WBWB
BWBW
4 2
BB
BB
WW
WW
4 4
WWBW
BBWB
WWBB
BBBB
1 5
WBBWB

Example output:
NO
YES
YES
YES
YES
NO
YES
NO

Editorial:
If either pair of opposite corners is the same color, then we can choose those corners to make everything the same color in one operation.
Otherwise, we have four cases for the colors of the corners:
Notice that these are all essentially rotations of each other, so we can only consider the first case by symmetry:
If any of the squares in the first row are black, then we can color everything black in two operations:
In the same way, if any of the squares in the last row are white, then we can color everything white in two operations.
Otherwise, the grid looks like this:
Notice that no matter how many operations we do, all squares in the top row will remain white, and all squares in the bottom row will remain black, so we can never make everything the same color.
So, considering the four cases from earlier, the solution is:
NO if all squares in the top row are the same color, all squares in the bottom row are the same color, and these two colors are different
NO if all squares in the leftmost column are the same color, all squares in the rightmost column are the same color, and these two colors are different
YES otherwise
Complexity: $$$O(nm)$$$