CF2029F Palindrome Everywhere

You are given a cycle with $ n $ vertices numbered from $ 0 $ to $ n-1 $ . For each $ 0\le i\le n-1 $ , there is an undirected edge between vertex $ i $ and vertex $ ((i+1)\bmod n) $ with the color $ c_i $ ( $ c_i=\texttt{R} $ or $ \texttt{B} $ ). Determine whether the following condition holds for every pair of vertices $ (i,j) $ ( $ 0\le i

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 3\leq n\leq10^6 $ ) — the number of vertices in the cycle. The second line contains a string $ c $ of length $ n $ ( $ c_i=\texttt{R} $ or $ \texttt{B} $ ) — the color of each edge. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, print "YES" (without quotes) if there is a palindrome route between any pair of nodes, and "NO" (without quotes) otherwise. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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.