题目描述

给定一排 $n$ 个格子，初始时全部为白色。你可以使用一个印章，每次可以盖住任意两个相邻的格子，使得其中一个变为红色，另一个变为蓝色。印章可以旋转使用，即既可以用作 $\color{blue}{\texttt{B}}\color{red}{\texttt{R}}$，也可以用作 $\color{red}{\texttt{R}}\color{blue}{\texttt{B}}$。

每次使用时，印章必须完全覆盖在这 $n$ 个格子内（不能部分超出格子）。同一个格子可以被多次盖印。每次使用印章时，被盖住的两个格子都会被重新染色。

例如，要得到 $\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\color{blue}{\texttt{B}}\texttt{W}$ 这一状态，可以按如下顺序盖印：$\texttt{WWWWW} \to \texttt{WW}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\texttt{W} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\texttt{W} \to \color{blue}{\texttt{B}}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}\texttt{W}$。其中 $\texttt{W}$、$\color{red}{\texttt{R}}$ 和 $\color{blue}{\texttt{B}}$ 分别表示白色、红色和蓝色格子，被盖印的格子用下划线标记。

给定一个最终的图案，问是否可以通过若干次（可以为零次）使用印章得到该图案。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示图案的长度。

每个测试用例的第二行包含一个字符串 $s$，表示你需要得到的图案。保证 $s$ 的长度为 $n$，且仅包含字符 $\texttt{W}$、$\texttt{R}$ 和 $\texttt{B}$，分别表示白色、红色和蓝色格子。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

输出 $t$ 行，每行对应一个测试用例的答案。如果可以通过若干次（可以为零次）使用印章得到该图案，输出 "YES"；否则输出 "NO"。

答案不区分大小写（例如 "yEs"、"yes"、"Yes" 和 "YES" 都被认为是正确的正答）。

说明/提示

第一个测试用例的解释见题面。

对于第二、第三和第四个测试用例，无法只盖印单个格子，因此答案为 "NO"。

对于第五个测试用例，可以按如下方式盖印：$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{blue}{\texttt{B}}$。

对于第六个测试用例，可以按如下方式盖印：$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}$。

对于第七个测试用例，你可以完全不使用印章。

由 ChatGPT 4.1 翻译

样例

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

YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO