Two Towers
Contest: Educational Codeforces Round 143 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, implementation, strings

There are two towers consisting of blocks of two colors: red and blue. Both towers are represented by strings of characters B and/or R denoting the order of blocks in them from the bottom to the top, where B corresponds to a blue block, and R corresponds to a red block.

These two towers are represented by strings BRBB and RBR.

You can perform the following operation any number of times: choose a tower with at least two blocks, and move its top block to the top of the other tower.

The pair of towers is beautiful if no pair of touching blocks has the same color; i. e. no red block stands on top of another red block, and no blue block stands on top of another blue block.

You have to check if it is possible to perform any number of operations (possibly zero) to make the pair of towers beautiful.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of three lines:

- the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 20$$$) — the number of blocks in the first tower and the number of blocks in the second tower, respectively;
- the second line contains $$$s$$$ — a string of exactly $$$n$$$ characters B and/or R, denoting the first tower;
- the third line contains $$$t$$$ — a string of exactly $$$m$$$ characters B and/or R, denoting the second tower.

Output format:
For each test case, print YES if it is possible to perform several (possibly zero) operations in such a way that the pair of towers becomes beautiful; otherwise print NO.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

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

Note:
In the first test case, you can move the top block from the first tower to the second tower (see the third picture).

In the second test case, you can move the top block from the second tower to the first tower $$$6$$$ times.

In the third test case, the pair of towers is already beautiful.

Example input:
4
4 3
BRBB
RBR
4 7
BRBR
RRBRBRB
3 4
RBR
BRBR
5 4
BRBRR
BRBR

Example output:
YES
YES
YES
NO

Editorial:
Note that it does not make sense to move several blocks first from the left tower to the right, and then from the right to the left, since this is similar to canceling the last actions.
Using the fact described above and small restrictions on the input data, one of the possible solutions is the following: choose which tower will be the one where we take blocks from (try both options), iterate over the number of operations, and then check that both towers are beautiful after that number of operations.
There is a faster solution: move all the blocks to the left tower, and then check that there is no more than one pair of adjacent blocks of the same color. If there are no such pairs, then we can divide the tower into two in an arbitrary way, and if there is exactly one pair, then we need to make a "cut" exactly between two blocks of the same color. Otherwise, there will always be a pair of adjacent blocks of the same color in one of the towers.