CF2029F Palindrome Everywhere

给定一个 $n$ 个点的环，编号为 $0$ 到 $n-1$，第 $i(0 \leq i \leq n-1)$ 个点向第 $((i+1) \bmod n)$ 个点连一条颜色为 $c_i$（$c_i$ 为 `R` 或 `B`）的无向边。问任意两点是否都满足它们之间有一条“回文路径”。 两点 $(i,j)$ 间的回文路径定义：（假设该回文路径包含的点集为 $p=[p_0,p_1,\dots,p_m]$） - 回文路径必须是两点之间的一条路径，但 **可以不是简单路径**。 - 对于满足 $x+y=m-1$ 且 $0 \leq x \leq y \leq m-1$ 的两点 $p_x,p_y$，连接 $p_x,p_{x+1}$ 的边的颜色和连接 $p_y,p_{y+1}$ 的边的颜色相同。

多测，第一行输入数据组数 $t(1 \leq t \leq 10^5)$。 对于每组数据，第一行一个整数 $n(3 \le n \le 10^6,\sum n \le 10^6)$，表示环长。 第二行有一个长度为 $n$ 的字符串 $c$，表示环上边的颜色。

对于每组测试数据，如果满足任意两个节点都有回文路径，输出 `YES`，否则输出 `NO`。 输出大小写不敏感，即输出 `yEs`，`yes`，`Yes` 或 `YES` 都表示 `YES`。

In the first test case, it is easy to show that there is a palindrome route between any two vertices. In the second test case, for any two vertices, there exists a palindrome route with only red edges. In the third test case, the cycle is as follows: $ 0\color{red}{\overset{\texttt{R}}{\longleftrightarrow}}1\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}2\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}3\color{red}{\overset{\texttt{R}}{\longleftrightarrow}}4\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}0 $ . Take $ (i,j)=(0,3) $ as an example, then $ 0\color{red}{\overset{\texttt{R}}{\longrightarrow}}1\color{blue}{\overset{\texttt{B}}{\longrightarrow}}2\color{blue}{\overset{\texttt{B}}{\longrightarrow}}3\color{red}{\overset{\texttt{R}}{\longrightarrow}}4\color{blue}{\overset{\texttt{B}}{\longrightarrow}}0\color{blue}{\overset{\texttt{B}}{\longrightarrow}}4\color{red}{\overset{\texttt{R}}{\longrightarrow}}3 $ is a palindrome route. Thus, the condition holds for $ (i,j)=(0,3) $ . In the fourth test case, when $ (i,j)=(0,2) $ , there does not exist a palindrome route.