CF2181K.Knit the Grid

The voodoo lady once knitted a magical tapestry. Initially, she took a blank canvas that can be represented as an $r \times c$ grid with $r$ rows and $c$ columns, thus having $(r + 1) \times (c + 1)$ grid points. Then she did the following operation some number of times: she knitted a cycle on the canvas along the grid lines, passing through each grid point at most once within that cycle. Additionally, no two cycles share any grid point.

In the end, it turned out that exactly one cycle passes through each of the $(r-1) \cdot (c-1)$ inner grid points that don't lie on the canvas' border. Here are some examples of cycle arrangements for $r=2$, $c=3$ with the inner grid points highlighted:

Then she left the canvas on the floor overnight. During the night, $r\cdot c$ green frogs hopped on the canvas, with one sitting in each cell. But that was only the beginning of the voodoo lady's troubles! Because then, the old witch came to the canvas, and one-by-one, ripped away every knitted line on the canvas. Every time she ripped away a knitted line segment between two adjacent grid points, the frogs in the cells adjacent to that line segment got startled (there were one or two startled frogs, depending on whether the line segment was on a border or not). When a frog got startled, it instantly changed its color: if the frog was green, it became brown; and if it was brown, it became green again.

If the cycles were arranged as in the pictures above, then the colors would be as follows (greyed out cells represent green frogs and white cells represent brown ones):

When the voodoo lady came back to her canvas, she only saw that there were frogs of two colors on her canvas, but no knitted cycles. From the given arrangement of the frog colors, determine whether it could have been produced by the described process, and if so, help the voodoo lady to restore a possible arrangement of cycles.

伏都女巫曾编织过一幅魔法挂毯。起初，她取了一块空白画布，该画布可表示为一个 $r \times c$ 的网格（含 $r$ 行、$c$ 列），因此共有 $(r + 1) \times (c + 1)$ 个网格点。随后，她重复执行以下操作若干次：沿着网格线在画布上编织一个环路，该环路在单次遍历中至多经过每个网格点一次；此外，任意两个环路互不共享任何网格点。

最终结果是：恰好有一个环路经过每一个内部网格点——即所有不位于画布边界的 $(r-1) \cdot (c-1)$ 个网格点。以下是 $r=2$、$c=3$ 时若干种环路排布示例（其中内部网格点已高亮标出）：

接着，她将画布留在地板上过夜。当夜，$r\cdot c$ 只绿色青蛙跳上了画布，每格恰好坐有一只青蛙。但这仅仅是伏都女巫麻烦的开始！因为随后，一位老巫婆来到画布前，将画布上所有编织的线段逐一撕去。每当她撕去连接两个相邻网格点的一条编织线段时，与该线段相邻的格子中的青蛙便会受惊（受惊青蛙数量为一或两只，取决于该线段是否位于画布边界上）。一旦青蛙受惊，它会立即变色：若原为绿色，则变为棕色；若原为棕色，则变回绿色。

若环路排布如上图所示，则最终青蛙颜色分布如下（灰色格子代表绿色青蛙，白色格子代表棕色青蛙）：

当伏都女巫回到画布前时，她只见画布上布满两种颜色的青蛙，而所有编织的环路均已消失。现给定青蛙的颜色分布，请判断该分布是否可能由上述过程产生；若可能，请帮助伏都女巫还原一种可行的环路排布方案。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $r$ and $c$, denoting the dimensions of the grid ($2 \le r, c \le 10^3$).

Each of the next $r$ lines contains a string consisting of $c$ characters G or B denoting green and brown frogs respectively.

It is guaranteed that the sum of $r \cdot c$ over all test cases does not exceed $2 \cdot 10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

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

接下来的 $r$ 行中，每行包含一个长度为 $c$ 的字符串，由字符 G 或 B 组成，分别表示绿色青蛙和棕色青蛙。

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

For each test case, on the first line output "YES" if the given frog colors could have been produced by the described process, and "NO" otherwise.

If the answer is YES, output $2r+1$ more lines with binary strings (with 0 and 1 characters). The first $r+1$ of those lines should have length $c$ each and represent the horizontal grid line segments and the next $r$ lines have length $c+1$ each and represent the vertical grid line segments of the answer as explained below.

In the first $r+1$ lines $j$-th character of the $i$-th line is 1 if the horizontal grid line segment that is $j$-th from the left and $i$-th from the top should have a knitted line along it, and 0 otherwise.

In the next $r$ lines $j$-th character of the $i$-th line is 1 if the vertical grid line segment that is $j$-th from the left and $i$-th from the top should have a knitted line along it, and 0 otherwise.

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

如果答案为“YES”，则再输出 $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。

The first test case is the first example of a cycle arrangement from the statement.

In the second sample test case, the output shown in the sample is illustrated in the first picture below. The cycle arrangement in the second picture is also correct, while in the third picture it is not, because some grid points are shared by more than one cycle. Leaving the grid empty would also not be correct, because there would be no cycle passing through inner grid points.

第一个测试用例对应题目陈述中循环排列的第一个示例。

在第二个样例测试用例中，样例中显示的输出如下面第一张图所示。第二张图中的循环排列同样正确；而第三张图中的排列则不正确，因为某些网格点被多个循环共同占用。若使网格为空，也不符合要求，因为此时将不存在任何经过内部网格点的循环。