Сэр Монокарп Гамильтон планирует покрасить свою стену. Стену можно представить как сетку, состоящую из \(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})\) имели общую сторону;
- все чёрные клетки встречались в пути ровно по одному разу;
- в пути не встречались белые клетки.
Определите, может ли Монокарп покрасить стену.
Выходные данные
На каждый набор входных данных выведите «YES», если Монокарп может покрасить стену. В противном случае выведите «NO».
Примечание
В первом наборе входных данных Монокарп может провести кистью по пути \((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)\) встречается в пути.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|