LuoTianyi дала вам палиндром\(^{\dagger}\) \(s\), и она хочет, чтобы вы нашли длину самой большой непустой подпоследовательности\(^{\ddagger}\) \(s\), которая не является палиндромом. Если таких подпоследовательностей нет, выведите \(-1\).
\(^{\dagger}\) Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, строки «z», «aaa», «aba», «abccba» являются палиндромами, а строки «codeforces», «reality», «ab» не являются.
\(^{\ddagger}\) Строка \(a\) является подпоследовательностью строки \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из \(b\). Например, строки «a», «aaa», «bab» являются подпоследовательностями строки «abaab», но строки «codeforces», «bbb», «h» не являются.
Выходные данные
Для каждого набора входных данных выведите одно целое число — длину самой длинной непустой подпоследовательности, не являющейся строкой-палиндромом. Если такой подпоследовательности нет, выведите \(-1\).
Примечание
В первом наборе входных данных «abcaba» является подпоследовательностью «abacaba», так как мы можем удалить третью букву «abacaba», чтобы получить «abcaba», а «abcaba» не является строкой-палиндромом. Мы можем доказать, что «abcaba» является примером самой длинной подпоследовательности «abacaba», не являющейся палиндромом, так что ответ равен \(6\).
Во втором наборе входных данных мы можем получить только «a» и «aa», но все они являются строками-палиндромами, поэтому ответ равен \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
abacaba
aaa
codeforcesecrofedoc
lol
|
6
-1
18
2
|