Hamiltonian Wall
Contest: Educational Codeforces Round 139 (Rated for Div. 2)
Difficulty rating: 1300
Tags: dp, implementation

Sir Monocarp Hamilton is planning to paint his wall. The wall can be represented as a grid, consisting of $$$2$$$ rows and $$$m$$$ columns. Initially, the wall is completely white.

Monocarp wants to paint a black picture on the wall. In particular, he wants cell $$$(i, j)$$$ (the $$$j$$$-th cell in the $$$i$$$-th row) to be colored black, if $$$c_{i, j} =$$$ 'B', and to be left white, if $$$c_{i, j} =$$$ 'W'. Additionally, he wants each column to have at least one black cell, so, for each $$$j$$$, the following constraint is satisfied: $$$c_{1, j}$$$, $$$c_{2, j}$$$ or both of them will be equal to 'B'.

In order for the picture to turn out smooth, Monocarp wants to place down a paint brush in some cell $$$(x_1, y_1)$$$ and move it along the path $$$(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$$$ so that:

- for each $$$i$$$, $$$(x_i, y_i)$$$ and $$$(x_{i+1}, y_{i+1})$$$ share a common side;
- all black cells appear in the path exactly once;
- white cells don't appear in the path.

Determine if Monocarp can paint the wall.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of columns in the wall.

The $$$i$$$-th of the next two lines contains a string $$$c_i$$$, consisting of $$$m$$$ characters, where each character is either 'B' or 'W'. $$$c_{i, j}$$$ is 'B', if the cell $$$(i, j)$$$ should be colored black, and 'W', if the cell $$$(i, j)$$$ should be left white.

Additionally, for each $$$j$$$, the following constraint is satisfied: $$$c_{1, j}$$$, $$$c_{2, j}$$$ or both of them are equal to 'B'.

The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print "YES" if Monocarp can paint a wall. Otherwise, print "NO".

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

Note:
In the first testcase, Monocarp can follow a path $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$ with his brush. All black cells appear in the path exactly once, no white cells appear in the path.

In the second testcase, Monocarp can follow a path $$$(1, 1)$$$, $$$(2, 1)$$$.

In the third testcase:

- the path $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ doesn't suffice because a pair of cells $$$(1, 3)$$$ and $$$(2, 4)$$$ doesn't share a common side;
- the path $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ doesn't suffice because cell $$$(2, 3)$$$ is visited twice;
- the path $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ doesn't suffice because a black cell $$$(1, 3)$$$ doesn't appear in the path;
- the path $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$, $$$(1, 4)$$$, $$$(1, 3)$$$ doesn't suffice because a white cell $$$(1, 4)$$$ appears in the path.

Example input:
6
3
WBB
BBW
1
B
B
5
BWBWB
BBBBB
2
BW
WB
5
BBBBW
BWBBB
6
BWBBWB
BBBBBB

Example output:
YES
YES
NO
NO
NO
YES

Editorial:
Why is there a constraint of each column having at least one black cell? Does the problem change a lot if there were white columns? Well, if such a column was inbetween some black cells, then the answer would be "NO". If it was on the side of the grid, you could remove it and proceed to solve without it. So, that doesn't really change the problem other than removing some casework.
Let's try to fix a start. Find a column that has only one black cell in it. If there are no such columns, the answer is immediately "YES". Otherwise, the path will always go through it in known directions: to the left and to the right (if both of them exist). Let's solve the problem separately for the left part of the path and for the right one — find a path that starts to the left of it and covers everything to the left and the same for the right part.
Consider the right part.
If the next column also has one black cell, then we can determine where to go uniquely. If this cell is on the opposite row, then the answer is "NO". Otherwise, go there and proceed further.
Let it have two black cells now. Find the entire two black row rectangle of maximum size that starts there. If there's nothing after it, you can easily traverse it any way you like. Otherwise, you have to traverse it in such a way that you end up in its last column, then go to the right from there. Turns out, there's only one way to achieve that. Go up/down to another row, go right, up/down to another row, right and so on. Now you just have to check if you end up in the correct row.
Thus, you can simulate the path to the left and to the right and check if you never get stuck.
Overall comlexity: $$$O(n)$$$ per testcase.