Вам дана строка \(s\), состоящая из строчных латинских букв. За одну операцию можно выбрать символ и заменить все вхождения этого символа на \(\texttt{0}\), или заменить все вхождения этого символа на \(\texttt{1}\).
Можно ли выполнить некоторое количество ходов так, чтобы в результате получилась чередующаяся бинарная строка\(^{\dagger}\)?
Например, рассмотрим строку \(\texttt{abacaba}\). Вы можете сделать следующие ходы:
- Заменить \(\texttt{a}\) на \(\texttt{0}\). Тогда строка будет иметь вид \(\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}\texttt{c}\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}\).
- Заменить \(\texttt{b}\) на \(\texttt{1}\). Тогда строка будет иметь вид \({\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}\texttt{c}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}\).
- Заменить \(\texttt{c}\) на \(\texttt{1}\). Теперь строка имеет вид \({\texttt{0}}{\texttt{1}}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}{\texttt{1}}{\texttt{0}}\). Это чередующаяся бинарная строка.
\(^{\dagger}\)Чередующаяся бинарная строка — это такая строка из \(\texttt{0}\) и \(\texttt{1}\), что никакие два соседних символа не равны. Например, \(\texttt{01010101}\), \(\texttt{101}\), \(\texttt{1}\) являются чередующимися бинарными строками, а \(\texttt{0110}\), \(\texttt{0a0a0}\), \(\texttt{10100}\) — нет.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если вы можете превратить строку в чередующуюся бинарную строку, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
Первый набор входных данных объясняется в условии.
Во втором наборе входных данных единственными возможными бинарными строками, которые вы можете получить, являются \(\texttt{00}\) и \(\texttt{11}\). Но они обе не являются чередующимися.
В третьем наборе входных данных можно получить \(\texttt{1}\), что является чередующейся бинарной строкой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
7
abacaba
2
aa
1
y
4
bkpt
6
ninfia
6
banana
10
codeforces
8
testcase
|
YES
NO
YES
YES
NO
YES
NO
NO
|