[Solution] Colorful Stamp solution codeforces

Colorful Stamp solution codeforces – A row of 𝑛n cells is given, all initially white. Using a stamp, you can stamp any two neighboring cells such that one becomes red and the other becomes blue. A stamp can be rotated, i.e. it can be used in both ways: as 𝙱𝚁BR and as 𝚁𝙱RB.

[Solution] Colorful Stamp solution codeforces

During use, the stamp must completely fit on the given 𝑛n cells (it cannot be partially outside the cells). The stamp can be applied multiple times to the same cell. Each usage of the stamp recolors both cells that are under the stamp.

For example, one possible sequence of stamps to make the picture 𝙱𝚁𝙱𝙱𝚆BRBBW could be 𝚆𝚆𝚆𝚆𝚆𝚆𝚆𝚁𝙱⎯⎯⎯⎯𝚆𝙱𝚁⎯⎯⎯⎯𝚁𝙱𝚆𝙱𝚁𝙱⎯⎯⎯⎯𝙱𝚆WWWWW→WWRB_W→BR_RBW→BRB_BW. Here 𝚆W𝚁R, and 𝙱B represent a white, red, or blue cell, respectively, and the cells that the stamp is used on are marked with an underline.

Given a final picture, is it possible to make it using the stamp zero or more times?

Input

The first line contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains an integer 𝑛n (1𝑛1051≤n≤105) — the length of the picture.

The second line of each test case contains a string 𝑠s — the picture you need to make. It is guaranteed that the length of 𝑠s is 𝑛n and that 𝑠s only consists of the characters 𝚆W𝚁R, and 𝙱B, representing a white, red, or blue cell, respectively.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

[Solution] Colorful Stamp solution codeforces

Output 𝑡t lines, each of which contains the answer to the corresponding test case. As an answer, output “YES” if it possible to make the picture using the stamp zero or more times, and “NO” otherwise.

You can output the answer in any case (for example, the strings “yEs“, “yes“, “Yes” and “YES” will be recognized as a positive answer).

Example
input

Copy
12
5
BRBBW
1
B
2
WB
2
RW
3
BRB
3
RBB
7
WWWWWWW
9
RBWBWRRBW
10
BRBRBRBRRB
12
BBBRWWRRRWBR
10
BRBRBRBRBW
5
RBWBW

[Solution] Colorful Stamp solution codeforces

output

Copy
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO

Colorful Stamp solution codeforces

The first test case is explained in the statement.

For the second, third, and fourth test cases, it is not possible to stamp a single cell, so the answer is “NO“.

For the fifth test case, you can use the stamp as follows: 𝚆𝚆𝚆𝚆𝚁𝙱⎯⎯⎯⎯𝙱𝚁⎯⎯⎯⎯𝙱WWW→WRB_→BR_B.

For the sixth test case, you can use the stamp as follows: 𝚆𝚆𝚆𝚆𝚁𝙱⎯⎯⎯⎯𝚁𝙱⎯⎯⎯⎯𝙱WWW→WRB_→RB_B.

For the seventh test case, you don’t need to use the stamp at all.

 

For Solution

Click here

Leave a Comment