eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сложить их вместе

Сложить их вместе

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Том разработал специальный вид головоломки: она включает в себя целую кучу одинаковых фигур. Они имеют форму трех квадратов, сложенных в виде буквы L. Квадрат в углу черный, два прилежащие к нему квадрата белые.

prb4011

На вход головоломки подается картинка из черных и белых квадратов на прямоугольной сетке. Задача состоит в том, чтобы воссоздать эту картинку с помощью имеющихся фигур. Фигуры можно вращать, но они не должны перекрываться.

Том уже разработал несколько хороших картин, и он хочет узнать, могут ли они вообще быть сложены при помощи фигур. Вместо того, чтобы проверять это для каждой картинки вручную, он хочет написать программу, которая определит это для него. Вы можете помочь ему?

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

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

  • одна строка с двумя целыми числами n и m (1n, m500): высота и ширина сетки, содержащей картинку.

  • n строк, каждая из которых содержит m символов сетки. Символом может быть 'B', 'W' или '.', что соответствует черной, белой или пустой клетке соответственно.

Сетка содержит как минимум один черный или белый квадрат.

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

Для каждого теста вывести одну строку, содержащую "YES" или "NO" в зависимости от того, возможно ли сложить заданную картинку фигурками головоломки. Считайте, что количество фигурок неограничено.

Пример

Входные данные #1
2
3 4
BWW.
WWBW
..WB
3 3
W..
BW.
WBW
Выходные данные #1
YES
NO
Источник 2011 ACM Northwestern Europe (NWERC), Problem D