Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

C. Гамильтонова стена
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сэр Монокарп Гамильтон планирует покрасить свою стену. Стену можно представить как сетку, состоящую из $$$2$$$ строк и $$$m$$$ столбцов. Изначально стена полностью белая.

Монокарп хочет нарисовать на стене черное изображение. В частности он хочет, чтобы клетка $$$(i, j)$$$ ($$$j$$$-я клетка в $$$i$$$-й строке) была покрашена в черный, если $$$c_{i, j} =$$$ 'B', и была оставлена белой, если $$$c_{i, j} =$$$ 'W'. Кроме того он хочет, чтобы в каждом столбце была хотя бы одна черная клетка, поэтому для каждого $$$j$$$ выполняется следующее условие: $$$c_{1, j}$$$, $$$c_{2, j}$$$ или они обе равны 'B'.

Чтобы картинка получилась ровной, Монокарп хочет поставить кисть в какую-нибудь клетку $$$(x_1, y_1)$$$ и провести ей по пути $$$(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$$$ так, чтобы:

  • для каждого $$$i$$$ $$$(x_i, y_i)$$$ и $$$(x_{i+1}, y_{i+1})$$$ имели общую сторону;
  • все чёрные клетки встречались в пути ровно по одному разу;
  • в пути не встречались белые клетки.

Определите, может ли Монокарп покрасить стену.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — количество столбцов в стене.

В $$$i$$$-й из следующих двух строк записана строка $$$c_i$$$, состоящая из $$$m$$$ символов, где каждый символ — это 'B' или 'W'. $$$c_{i, j}$$$ равно 'B', если клетка $$$(i, j)$$$ должна быть покрашена черным, и 'W', если клетка $$$(i, j)$$$ должна быть оставлена белой.

Кроме того, для каждого $$$j$$$ выполняется следующее условие: $$$c_{1, j}$$$, $$$c_{2, j}$$$ или они обе равны 'B'.

Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите «YES», если Монокарп может покрасить стену. В противном случае выведите «NO».

Пример
Входные данные
6
3
WBB
BBW
1
B
B
5
BWBWB
BBBBB
2
BW
WB
5
BBBBW
BWBBB
6
BWBBWB
BBBBBB
Выходные данные
YES
YES
NO
NO
NO
YES
Примечание

В первом наборе входных данных Монокарп может провести кистью по пути $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$. Все черные клетки встречаются в пути ровно один раз, никакая белая клетка не встречается в пути.

Во втором наборе входных данных Монокарп может воспользоваться путем $$$(1, 1)$$$, $$$(2, 1)$$$.

В третьем наборе входных данных:

  • путь $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ не подходит, потому что пара клеток $$$(1, 3)$$$ и $$$(2, 4)$$$ не имеют общую сторону;
  • путь $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ не подходит, потому что клетка $$$(2, 3)$$$ посещается дважды;
  • путь $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ не подходит, потому что черная клетка $$$(1, 3)$$$ не встречается в пути;
  • путь $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$, $$$(1, 4)$$$, $$$(1, 3)$$$ не подходит, потому что белая клетка $$$(1, 4)$$$ встречается в пути.