Yin Yang
Contest: Codeforces Round 783 (Div. 1)
Difficulty rating: 3500
Tags: implementation

You are given a rectangular grid with $$$n$$$ rows and $$$m$$$ columns. $$$n$$$ and $$$m$$$ are divisible by $$$4$$$. Some of the cells are already colored black or white. It is guaranteed that no two colored cells share a corner or an edge.

Color the remaining cells in a way that both the black and the white cells becomes orthogonally connected or determine that it is impossible.

Consider a graph, where the black cells are the nodes. Two nodes are adjacent if the corresponding cells share an edge. If the described graph is connected, the black cells are orthogonally connected. Same for white cells.

Input format:
The input consists of multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 4000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$8 \le n, m \le 500$$$, $$$n$$$ and $$$m$$$ are divisible by $$$4$$$) — the number of rows and columns.

Each of the next $$$n$$$ lines contains $$$m$$$ characters. Each character is either 'B', 'W' or '.', representing black, white or empty cell respectively. Two colored (black or white) cell does not share a corner or an edge.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$250\,000$$$.

Output format:
For each testcase print "NO" if there is no solution, otherwise print "YES" and a grid with the same format. If there are multiple solutions, you can print any.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Solution for test case 1:

Test case 2: one can see that the black and the white part can't be connected in the same time. So the answer is "NO".

Example input:
4
8 8
.W.W....
.....B.W
.W.W....
.....W.W
B.B.....
....B.B.
B.W.....
....B.B.
8 8
B.W..B.W
........
W.B..W.B
........
........
B.W..B.W
........
W.B..W.B
8 12
W.B.........
....B...B.W.
B.B.........
....B...B.B.
.B..........
........B...
.W..B.B...W.
............
16 16
.W............W.
...W..W..W.W....
.B...........B.W
....W....W......
W......B....W.W.
..W.......B.....
....W...W....B.W
.W....W....W....
...B...........W
W.....W...W..B..
..W.W...W......B
............W...
.W.B...B.B....B.
.....W.....W....
..W......W...W..
W...W..W...W...W

Example output:
YES
BWWWWWWW
BWBBBBBW
BWBWWWBW
BWBWBWBW
BWBWBWBW
BWBBBWBW
BWWWWWBW
BBBBBBBW
NO
YES
WWBBBBBBBBBB
BWWWBBBBBBWB
BBBWBBBWWWWB
BBBWBBBWBBBB
BBBWBBBWBBBB
BBBWWWWWBBBB
BWWWBBBWWWWB
BBBBBBBBBBBB
YES
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WBBBBBBBBBBBBBWW
WBBBWBWWWWBWWBWW
WBBWWBBBWWBWWBWW
WBWWWBWWWWBWWBWW
WBBWWBBBWWBWWBWW
WWBWWWWWWWWWWWWW
WWBBBBBBBBBBBBWW
WBBBWWWBWWWBWBWW
WWWBWBBBWBBBWBBB
WWWBWBWWWWWBWWBW
WWWBWBBBWBBBWWBW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW

Editorial:
Border: cells in the first or last row or first or last column. One can see that on the border both the black and the white part is connected. So there is no answer if there is a "BWBW" subsequence on the border.
Otherwise there is a solution.
Solve an easier task first. Assume that there is no colored cell on the border.
Than there is a nice construction. Color white all cells in the first column, and in the $$$4*k+2$$$-nd and $$$4*k+3$$$-rd row, which is not in the last column.
We can see that the stripes (2 consequtive white rows) are connected, because no two initially colored cell share a corner. Also different stripes are connected to each other because of the left column. If there is a white colored cell in a middle of a black stripe, then it is orthogonally adjacent to a white stripe.
Similarly the black cells will be connected too.
If there are colored cells on the border, than it might be impossible to construct exactly this. But the most of the cells might be the same: the white stripes, and the white column on the left side. In this way, the white part is connected. For the black part, there might be $$$3$$$ issues: the border is not connected to the black stripes, there are isolated black cells in the $$$2$$$-nd or $$$n-1$$$-th row, different black stripes might be unconnected. All of these issues is solvable locally with changing the color of some cells from white to black and vice versa.