A16787 | Knit the Grid

伏都教女巫曾经编织过一块神奇的挂毯。起初，她拿了一块空白画布，可以表示为一个 $r \times c$ 的网格，有 $r$ 行和 $c$ 列，因此共有 $(r + 1) \times (c + 1)$ 个网格点。然后，她进行了若干次以下操作：在画布上沿网格线编织一个圈（闭合回路），该圈在编织过程中每个网格点最多经过一次。此外，任意两个圈都不共享任何网格点。

最后结果显示，不位于画布边界上的 $(r-1) \cdot (c-1)$ 个内部网格点中，每一个都恰好被一个圈经过。以下是 $r=2, c=3$ 时的一些圈排列示例，图中高亮显示了内部网格点：


随后，她将画布留在地板上过夜。夜里，有 $r \cdot c$ 只绿色的青蛙跳上了画布，每个单元格里坐一只。但这只是女巫麻烦的开始！因为接着，老巫婆来到了画布前，一根接一根地拆掉了画布上所有编织好的线条。每当她拆掉两个相邻网格点之间的一段编织线段时，与该线段相邻的单元格中的青蛙就会受到惊吓（根据线段是否在边界上，会有 $1$ 只或 $2$ 只青蛙受惊）。当一只青蛙受惊时，它会立即改变颜色：如果它是绿色的，就会变成棕色；如果是棕色的，就会变回绿色。

如果圈的排列如上图所示，那么青蛙的颜色将如下所示（灰色单元格代表绿色青蛙，白色单元格代表棕色青蛙）：


当伏都教女巫回到画布前时，她只看到画布上有两种颜色的青蛙，但编织的圈都不见了。根据给定的青蛙颜色排列，请判断它是否可能由上述过程产生；如果可能，请帮助女巫还原出一种可能的圈排列方案。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

每个测试用例的第一行包含两个整数 $r$ 和 $c$，表示网格的尺寸 ($2 \le r, c \le 10^3$)。

接下来的 $r$ 行，每行包含一个由 $c$ 个字符 'G' 或 'B' 组成的字符串，分别代表绿色（Green）和棕色（Brown）的青蛙。

保证所有测试用例中 $r \cdot c$ 的总和不超过 $2 \cdot 10^6$。

对于每个测试用例，如果给定的青蛙颜色可以由上述过程产生，则在第一行输出 YES，否则输出 NO。

如果答案为 YES，则额外输出 $2r+1$ 行由 $0$ 和 $1$ 字符组成的二进制字符串。

- 前 $r+1$ 行：每行长度为 $c$，表示水平网格线段。第 $i$ 行第 $j$ 个字符为 $1$ 表示对应的水平线段上有编织线，$0$ 表示没有。
- 后 $r$ 行：每行长度为 $c+1$，表示垂直网格线段。第 $i$ 行第 $j$ 个字符为 $1$ 表示对应的垂直线段上有编织线，$0$ 表示没有。