Олимпиадный тренинг

Задача . F. Инь и Ян

Задача

Дана прямоугольная сетка, состоящая из $n$ строк и $m$ столбцов. $n$ и $m$ делятся на $4$. Некоторые клетки уже покрашены в черный или белый. Гарантируется, что никакие две покрашенные клетки не являются соседями по стороне или углу.

Покрасьте оставшиеся клетки таким образом, чтобы и черные, и белые клетки стали ортогонально связными, или определите, что это невозможно.

Рассмотрим граф, в котором вершины — черные клетки. Две вершины соединены ребром, если соответствующие черные клетки являются соседями по стороне. Если получившийся граф связен, черные клетки считаются ортогонально связными. Аналогично для белых клеток.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка ввода содержит одно целое число $t$ ($1 \le t \le 4000$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора содержит два целых числа $n$, $m$ ($8 \le n, m \le 500$, $n$ и $m$ делятся на $4$) — количество строк и столбцов.

Каждая из следующих $n$ строк содержит $m$ символов. Каждый символ — 'B', 'W' или '.' — кодирует черную, белую или пустую клетку соответственно. Никакие две покрашенные (черные или белые) клетки не являются соседями по стороне или углу.

Гарантируется, что сумма $n \cdot m$ по всем наборам входных данных не превосходит $250\,000$.

Выходные данные

Для каждого набора входных данных выведите «NO», если решения не существует. В ином случае выведите «YES» и сетку в том же формате. Если существует несколько решений, выведите любое.

Примечание

Решение для первого набора входных данных:

$\text{[math]}$

Второй набор: можно показать, что черная и белая части не могут быть соединены одновременно. Таким образом, ответ «NO»

Примеры

№	Входные данные	Выходные данные
1	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	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

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет