Дан цикл с \(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}\).
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если существует палиндромный маршрут между любой парой вершин, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных легко показать, что существует палиндромный маршрут между любыми двумя вершинами.
Во втором наборе входных данных между любыми двумя вершинами существует маршрут, состоящий только из красных рёбер.
В третьем наборе входных данных цикл выглядит следующим образом: \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5
RRRRR
5
RRRRB
5
RBBRB
6
RBRBRB
6
RRBBRB
5
RBRBR
12
RRBRRBRRBRRB
|
YES
YES
YES
NO
NO
YES
NO
|