B. Чередующаяся строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем строку $$$t$$$ чередующейся, если для любого $$$i$$$ от $$$1$$$ до $$$n - 1$$$ выполняется $$$t_{i} \neq t_{i + 1}$$$.

Дана строка $$$s$$$, которая состоит только из букв «a» и/или «b». Вы можете не более одного раза совершить с ней следующую операцию:

  • выбрать подстроку $$$s_{l}s_{l+1}\ldots s_{r}$$$, состоящую хотя бы из одного символа;
  • после выбора подстроки можно изменить в ней все буквы, то есть заменить все «a» на «b» и все «b» на «a» (вы можете это сделать, но не обязаны);
  • перевернуть выбранную подстроку, то есть превратить строку $$$s_{1}s_{2}\dots s_{l-1}s_{l}s_{l+1}\ldots s_{r}s_{r+1}\ldots s_{n}$$$ в $$$s_{1}s_{2}\dots s_{l-1}s_{r}s_{r-1}\ldots s_{l}s_{r+1}\ldots s_{n}$$$.

Обратите внимание, что вы не обязаны выполнять второй пункт операции. Например, для строки $$$s =~$$$«ababbab» после одной операции можно получить «abababa», выбрав в операции подстроку $$$s_{5}s_{6}s_{7}$$$ и выполнив второй пункт операции, или «bababab», выбрав подстроку $$$s_{1}s_{2}s_{3}s_{4}$$$ и не выполнив второй пункт операции. Однако третий пункт операции выполняется всегда.

Можно ли получить из строки $$$s$$$ чередующуюся строку?

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

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

В единственной строке каждого набора входных данных содержится строка $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^{5}$$$). Строка состоит только из строчных латинских букв «a» и/или «b».

Дополнительные ограничения на входные данные:

  • сумма длин строк по всем наборам входных данных не превосходит $$$2 \cdot 10^{5}$$$.
Выходные данные

Для каждого набора входных данных выведите одно из двух:

  • YES, если возможно получить чередующуюся строку из $$$s$$$;
  • NO в противном случае.

Каждую букву можно выводить в любом регистре.

Пример
Входные данные
8
abbaba
aaaaa
bababba
ab
abbaabba
bbb
ababa
aabb
Выходные данные
YES
NO
YES
YES
NO
YES
YES
YES
Примечание

В первом примере можно выбрать подстроку $$$s_3 s_4 s_5 s_6$$$ и не выполнять второй шаг, тогда получим строку «ababab».

В третьем примере можно выбрать подстроку $$$s_1 s_2 s_3 s_4 s_5$$$ и выполнить второй шаг, тогда получим строку «abababa».

В четвертом примере строка уже чередующаяся.

В шестом примере можно выбрать подстроку $$$s_2$$$ и выполнить второй шаг, тогда получим строку «bab».