311288: CF1966B. Rectangle Filling

B. Rectangle Fillingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

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

Output

NO
YES
YES
YES
YES
NO
YES
NO

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.

题目大意：
这个问题是关于一个由白色和黑色方块组成的 n×m 网格。你可以选择任意两个相同颜色的方块，并将它们之间的子矩形染成那种颜色。具体来说，如果你选择了两个相同颜色的位置 (x1, y1) 和 (x2, y2)，那么将所有满足 min(x1, x2) ≤ x ≤ max(x1, x2) 和 min(y1, y2) ≤ y ≤ max(y1, y2) 的位置 (x, y) 的颜色设置为 c。问题是，通过执行任意数量的操作（可能为零），是否可以使网格中的所有方块颜色相同。

输入数据格式：
输入的第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 m（1 ≤ n, m ≤ 500），分别表示网格的行数和列数。
接下来的 n 行，每行包含 m 个字符 'W' 和 'B'，表示网格方块的初始颜色。
所有测试用例的 n×m 之和不超过 3×10^5。

输出数据格式：
对于每个测试用例，如果可以使网格中的所有方块颜色相同，则输出 "YES"，否则输出 "NO"。
输出答案时大小写不敏感，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。

请注意，上述内容是对网页内容的概括性翻译，并未逐字逐句翻译，且公式已用 LaTeX 格式表示。题目大意： 这个问题是关于一个由白色和黑色方块组成的 n×m 网格。你可以选择任意两个相同颜色的方块，并将它们之间的子矩形染成那种颜色。具体来说，如果你选择了两个相同颜色的位置 (x1, y1) 和 (x2, y2)，那么将所有满足 min(x1, x2) ≤ x ≤ max(x1, x2) 和 min(y1, y2) ≤ y ≤ max(y1, y2) 的位置 (x, y) 的颜色设置为 c。问题是，通过执行任意数量的操作（可能为零），是否可以使网格中的所有方块颜色相同。 输入数据格式： 输入的第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 n 和 m（1 ≤ n, m ≤ 500），分别表示网格的行数和列数。 接下来的 n 行，每行包含 m 个字符 'W' 和 'B'，表示网格方块的初始颜色。 所有测试用例的 n×m 之和不超过 3×10^5。 输出数据格式： 对于每个测试用例，如果可以使网格中的所有方块颜色相同，则输出 "YES"，否则输出 "NO"。 输出答案时大小写不敏感，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。 请注意，上述内容是对网页内容的概括性翻译，并未逐字逐句翻译，且公式已用 LaTeX 格式表示。