E. Без палиндромов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Christopher Tin ft. Soweto Gospel Choir - Baba Yetu
ඞ

Вам дана строка $$$s$$$, состоящая из строчных латинских букв. Вам нужно разбить$$$^\dagger$$$ эту строку на некоторое количество подстрок так, чтобы каждая подстрока не была палиндромом$$$^\ddagger$$$.

$$$^\dagger$$$ Разбиение строки $$$s$$$ — это упорядоченная последовательность некоторых $$$k$$$ строк $$$t_1, t_2, \ldots, t_k$$$, таких, что $$$t_1 + t_2 + \ldots + t_k = s$$$, где $$$+$$$ обозначает операцию конкатенации.

$$$^\ddagger$$$ Строка $$$s$$$ называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, $$$\mathtt{racecar}$$$, $$$\mathtt{abccba}$$$ и $$$\mathtt{a}$$$ являются палиндромами, а $$$\mathtt{ab}$$$, $$$\mathtt{dokibird}$$$ и $$$\mathtt{kurosanji}$$$ — нет.

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

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

Каждый набор входных данных содержит строку $$$s$$$, состоящую из строчных латинских букв ($$$1 \le |s| \le 10^6$$$).

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

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

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

Если ответ «YES», то во второй строке выведите целое число $$$k$$$ — количество частей, на которое нужно разбить $$$s$$$, чтобы каждая часть не была палиндромом. В третьей строке выведите $$$k$$$ строк $$$t_1, t_2, \ldots, t_k$$$, представляющих такое разбиение. Если таких разбиений несколько, выведите любое из них.

Пример
Входные данные
3
sinktheyacht
lllllllll
uwuowouwu
Выходные данные
YES
1
sinktheyacht
NO
YES
3
uw uow ouwu
Примечание

В первом наборе входных данных, поскольку $$$\mathtt{sinktheyacht}$$$ уже не является палиндромом, разбиение $$$[\mathtt{sinktheyacht}]$$$ является допустимым.

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

В третьем наборе входных данных еще одно допустимое разбиение — $$$[\mathtt{uw},\mathtt{uo}, \mathtt{wou}, \mathtt{wu}]$$$.