Недавно в 179-й школе разработали уникальный алгоритм, который на вход принимает бинарную строку \(s\). Однако школьники обнаружили, что если какая-то подстрока \(t\) строки \(s\) является палиндромом длины больше чем 1, то алгоритм сработает некорректно. Им стало интересно, можно ли в строке \(s\) поменять порядок символов, чтобы на ней корректно отработал алгоритм?
Бинарная строка — это строка, состоящая только из символов 0 и 1.
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Палиндром — это строка, которая читается одинаково слева направо и справа налево.
Выходные данные
Для каждого набора входных данных выведите YES (без учета регистра), если в строке \(s\) можно как-то поменять порядок символов, чтобы в ней не было подстрок, которые являются палиндромами длины больше чем 1, и NO (без учета регистра) в противном случае.
Примечание
В первых трёх наборах исходные строки не содержат палиндромов длины больше чем 1, поэтому ответы YES.
В последнем наборе невозможно поменять порядок символов, чтобы в строке не было палиндромов длины больше чем 1, поэтому ответ NO.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1
2
10
2
01
4
1010
|
YES
YES
YES
NO
|