有一个由白色和黑色方块组成的 $$$n \times m$$$ 网格。在一项操作中,您可以选择任意两个相同颜色的方块,并将它们之间的子矩形中的所有方块涂上该颜色。
正式来说,如果您选择位置 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$,这两个位置当前的颜色 $$$c$$$ 相同,则设置所有 $$$(x, y)$$$ 的颜色,其中 $$$\min(x_1, x_2) \le x \le \max(x_1, x_2)$$$ 和 $$$\min(y_1, y_2) \le y \le \max(y_1, y_2)$$$ 到 $$$c$$$。
该图显示了网格上两个可能操作的序列:
在执行任意次数的操作(可能为零)后,网格中的所有方块是否可能具有相同的颜色?
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500$$$) - 分别是网格中的行数和列数。
接下来的 $$$n$$$ 行包含 $$$m$$$ 字符“W”和“B”——网格方块的初始颜色。
保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$3\cdot 10^5$$$。
输出
对于每个测试用例,如果可以使网格中的所有方块颜色相同,则打印“YES”,否则打印“NO”。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
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
输出 #1
NO YES YES YES YES NO YES NO
注意
在第一个示例中,不可能通过操作更改任何方块的颜色,因此我们输出 NO。
第二个例子就是上图所示的情况。如图所示,两次操作后所有方块都可能变成白色,因此我们输出 YES。
在第三个和第四个示例中,所有方块都已经是相同的颜色,因此我们输出 YES。
在第五个示例中,我们可以通过两个操作完成所有操作。首先,选择位置 $$$(2, 1)$$$ 和 $$$(1, 4)$$$ 并将所有方块用 $$$1 \le x \le 2$$$ 和 $$$1 \le y \le 4$$$ 着色为白色。然后,选择位置 $$$(2, 1)$$$ 和 $$$(3, 4)$$$ 并将所有方块用 $$$2 \le x \le 3$$$ 和 $$$1 \le y \le 4$$$ 着色为白色。经过这两个操作后,所有方块都变成白色。