F. Палиндромы везде
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан цикл с $$$n$$$ вершинами, пронумерованными от $$$0$$$ до $$$n-1$$$. Для каждого $$$0\le i\le n-1$$$ существует неориентированное ребро между вершиной $$$i$$$ и вершиной $$$((i+1)\bmod n)$$$ с цветом $$$c_i$$$ ($$$c_i=\texttt{R}$$$ или $$$\texttt{B}$$$).

Проверьте, выполняется ли следующее условие для каждой пары вершин $$$(i,j)$$$ ($$$0\le i<j\le n-1$$$):

  • Существует палиндромный маршрут между вершиной $$$i$$$ и вершиной $$$j$$$. Обратите внимание, что маршрут может не быть простым. Формально, должна существовать последовательность $$$p=[p_0,p_1,p_2,\ldots,p_m]$$$, такая что:
    • $$$p_0=i$$$, $$$p_m=j$$$;
    • Для всех $$$0\leq x\le m-1$$$, либо $$$p_{x+1}=(p_x+1)\bmod n$$$, либо $$$p_{x+1}=(p_{x}-1)\bmod n$$$;
    • Для всех $$$0\le x\le y\le m-1$$$ таких, что $$$x+y=m-1$$$, ребро между $$$p_x$$$ и $$$p_{x+1}$$$ имеет такой же цвет, как и ребро между $$$p_y$$$ и $$$p_{y+1}$$$.
Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3\leq n\leq10^6$$$) — количество вершин в цикле.

Вторая строка содержит строку $$$c$$$ длиной $$$n$$$ ($$$c_i=\texttt{R}$$$ или $$$\texttt{B}$$$) — цвет каждого ребра.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если существует палиндромный маршрут между любой парой вершин, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
7
5
RRRRR
5
RRRRB
5
RBBRB
6
RBRBRB
6
RRBBRB
5
RBRBR
12
RRBRRBRRBRRB
Выходные данные
YES
YES
YES
NO
NO
YES
NO
Примечание

В первом наборе входных данных легко показать, что существует палиндромный маршрут между любыми двумя вершинами.

Во втором наборе входных данных между любыми двумя вершинами существует маршрут, состоящий только из красных рёбер.

В третьем наборе входных данных цикл выглядит следующим образом: $$$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$$$. Возьмём $$$(i,j)=(0,3)$$$ в качестве примера, тогда $$$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$$$ является палиндромным маршрутом. Таким образом, условие выполняется для $$$(i,j)=(0,3)$$$.

В четвёртом наборе входных данных не существует палиндромного маршрута для $$$(i,j)=(0,2)$$$.