巫毒女士曾经编织过一张神奇的挂毯。最初,她拿了一块空白画布,可以表示为 $$$r \times c$$$ 网格,其中包含 $$$r$$$ 行和 $$$c$$$ 列,因此具有 $$$(r + 1) \times (c + 1)$$$ 网格点。然后她多次进行以下操作:沿着网格线在画布上编织一个循环,在该循环内最多穿过每个网格点一次。此外,没有两个循环共享任何网格点。
最后,事实证明,恰好有一个循环经过每个不在画布边框上的 $$$(r-1) \cdot (c-1)$$$ 内部网格点。以下是 $$$r=2$$$、$$$c=3$$$ 的循环安排示例,其中突出显示内部网格点:
![]() | ![]() | ![]() |
然后她把画布留在地板上过夜。晚上,$$$r\cdot c$$$ 绿色青蛙在画布上跳跃,每个牢房里都有一只。但这只是巫毒女士麻烦的开始!因为这时,老巫婆来到了画布前,将画布上的每一根编织线都一一撕掉了。每当她撕掉两个相邻网格点之间的编织线段时,与该线段相邻的单元格中的青蛙就会受到惊吓(有一只或两只受惊的青蛙,具体取决于该线段是否位于边界上)。当青蛙受到惊吓时,它的颜色会立即改变:如果青蛙是绿色的,它就会变成棕色;如果青蛙是绿色的,它就会变成棕色的。如果它是棕色的,它又会变成绿色。
如果循环按照上图排列,那么颜色将如下(灰色单元格代表绿色青蛙,白色单元格代表棕色青蛙):
![]() | ![]() | ![]() |
当巫毒女士回到画布前时,她只看到画布上有两种颜色的青蛙,但没有针织循环。根据给定的青蛙颜色排列,确定它是否可以通过所描述的过程产生,如果是,请帮助巫毒女士恢复可能的周期排列。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$r$$$ 和 $$$c$$$,表示网格的尺寸 ($$$2 \le r, c \le 10^3$$$)。
接下来的 $$$r$$$ 行包含一个由 $$$c$$$ 字符组成的字符串 G or B 分别表示绿色和棕色青蛙。
保证所有测试用例的 $$$r \cdot c$$$ 总和不超过 $$$2 \cdot 10^6$$$。
输出
对于每个测试用例,在第一行输出“是“如果给定的青蛙颜色可以通过所描述的过程产生,并且”NO”否则。
如果答案是 是,输出 $$$2r+1$$$ 多行二进制字符串(带有 0 和 1 字符)。这些线的第一条 $$$r+1$$$ 的长度应为 $$$c$$$,代表水平网格线段,接下来的 $$$r$$$ 线的长度应为 $$$c+1$$$,代表答案的垂直网格线段,如下所述。
在第一个 $$$r+1$$$ 行中,第 $$$i$$$ 行的第 $$$j$$$ 个字符是 1 如果从左边算起第 $$$j$$$ 和从顶部算起第 $$$i$$$ 的水平网格线段应该有一条针织线,并且 0 否则。
在接下来的 $$$r$$$ 行中,第 $$$i$$$ 行的第 $$$j$$$ 个字符是 1 如果从左边算起第 $$$j$$$ 和从顶部算起第 $$$i$$$ 的垂直网格线段应该有一条针织线,并且 0 否则。
示例
输入复制
32 3BBGGBB3 3GGGGGGGGG3 3GGGBBBGGG
输出复制
YES00110110000111100YES111010010111100111111001NO
注意
第一个测试用例是语句中循环排列的第一个示例。
在第二个示例测试用例中,示例中显示的输出如下面第一张图片所示。第二张图中的循环排列也是正确的,而第三张图中则不然,因为某些网格点被多个循环共享。将网格留空也是不正确的,因为不会有循环穿过内部网格点。
![]() | ![]() | ![]() |








