Вам дана строка \(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}\) — нет.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке «YES», если существует разбиение \(s\), части которого не являются палиндромами, или «NO», если такого разбиения не существует.
Если ответ «YES», то во второй строке выведите целое число \(k\) — количество частей, на которое нужно разбить \(s\), чтобы каждая часть не была палиндромом. В третьей строке выведите \(k\) строк \(t_1, t_2, \ldots, t_k\), представляющих такое разбиение. Если таких разбиений несколько, выведите любое из них.
Примечание
В первом наборе входных данных, поскольку \(\mathtt{sinktheyacht}\) уже не является палиндромом, разбиение \([\mathtt{sinktheyacht}]\) является допустимым.
Во втором наборе входных данных, поскольку любая подстрока строки \(s\) является палиндромом, не существует допустимых разбиений.
В третьем наборе входных данных еще одно допустимое разбиение — \([\mathtt{uw},\mathtt{uo}, \mathtt{wou}, \mathtt{wu}]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
sinktheyacht
lllllllll
uwuowouwu
|
YES
1
sinktheyacht
NO
YES
3
uw uow ouwu
|