Vous disposez d'un cycle avec $n$ sommets numérotés de $0$ à $n - 1$. Pour chaque $0 \le i \le n - 1$, il existe une arête non orientée entre le sommet $i$ et le sommet $((i + 1) \pmod n)$ avec la couleur $c_i$ ($c_i = \text{R}$ ou $\text{B}$).
Déterminez si la condition suivante est vérifiée pour chaque paire de sommets $(i, j)$ ($0 \le i < j \le n - 1$) :
- Il existe un chemin palindrome entre le sommet $i$ et le sommet $j$. Notez que le chemin peut ne pas être simple. Formellement, il doit exister une séquence $p = [p_0, p_1, p_2, \dots, p_m]$ telle que :
- $p_0 = i$, $p_m = j$ ;
- Pour chaque $0 \le x \le m - 1$, soit $p_{x+1} = (p_x + 1) \pmod n$, soit $p_{x+1} = (p_x - 1) \pmod n$ ;
- Pour chaque $0 \le x \le y \le m - 1$ satisfaisant $x + y = m - 1$, l'arête entre $p_x$ et $p_{x+1}$ a la même couleur que l'arête entre $p_y$ et $p_{y+1}$.
Entrée
Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 10^5$) — le nombre de cas de test. La description des cas de test suit.
La première ligne de chaque cas de test contient un entier $n$ ($3 \le n \le 10^6$) — le nombre de sommets dans le cycle.
La deuxième ligne contient une chaîne $c$ de longueur $n$ ($c_i = \text{R}$ ou $\text{B}$) — la couleur de chaque arête.
Il est garanti que la somme de $n$ sur tous les cas de test n'excède pas $10^6$.
Sortie
Pour chaque cas de test, affichez « YES » (sans les guillemets) s'il existe un chemin palindrome entre toute paire de nœuds, et « NO » (sans les guillemets) sinon.
Vous pouvez afficher la réponse dans n'importe quelle casse (majuscules ou minuscules). Par exemple, les chaînes « yEs », « yes », « Yes » et « YES » seront reconnues comme des réponses positives.
Exemples
Entrée 1
5 RRRRR
Sortie 1
YES
Entrée 2
5 RRRRB
Sortie 2
YES
Entrée 3
5 RBBRB
Sortie 3
YES
Entrée 4
6 RBRBRB
Sortie 4
NO
Entrée 5
6 RRBBRB
Sortie 5
NO
Entrée 6
5 RBRBR
Sortie 6
YES
Entrée 7
12 RRBRRBRRBRRB
Sortie 7
NO
Remarque
Dans le premier cas de test, il est facile de montrer qu'il existe un chemin palindrome entre deux sommets quelconques.
Dans le deuxième cas de test, pour deux sommets quelconques, il existe un chemin palindrome avec uniquement des arêtes rouges.
Dans le troisième cas de test, le cycle est le suivant : $0 \overset{\text{R}}{\longleftrightarrow} 1 \overset{\text{B}}{\longleftrightarrow} 2 \overset{\text{B}}{\longleftrightarrow} 3 \overset{\text{R}}{\longleftrightarrow} 4 \overset{\text{B}}{\longleftrightarrow} 0$. Prenons $(i, j) = (0, 3)$ comme exemple, alors $0 \xrightarrow{\text{R}} 1 \xrightarrow{\text{B}} 2 \xrightarrow{\text{B}} 3 \xrightarrow{\text{R}} 4 \xrightarrow{\text{B}} 0 \xrightarrow{\text{B}} 4 \xrightarrow{\text{R}} 3$ est un chemin palindrome. Ainsi, la condition est vérifiée pour $(i, j) = (0, 3)$.
Dans le quatrième cas de test, lorsque $(i, j) = (0, 2)$, il n'existe pas de chemin palindrome.