eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Усталость и терпение

Усталость и терпение

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Учиться в A0 непросто. Я очень устал. Сейчас жарко и душно, моя нога болит после вчерашнего футбола, я не выспался и не понял вчера алгоритм Штора-Вагнера. Что хуже всего, сейчас идет лекция, я плохо понимаю то, что нам рассказывают, и мне очень хочется спать. Чтобы не провалиться в сон, я начал выписывать длинную строку по следующему алгоритму:

  • На первом шаге я выписал строку "a".

  • На i-м шаге (i2) к строке S, выписанной на предыдущем шаге, я приписал i-ю букву латинского алфавита, а потом еще раз приписал строку S.

Уже после четырех шагов я получил строку "abacabadabacaba" и собирался продолжить свое занятие, как вдруг...

Я заметил на полу клочок бумаги, на котором была написана удивительно похожая последовательность букв. Может, это фрагмент строки, которая получится после того, как я выполню несколько шагов своего алгоритма? Неужели когда-то давно на моем месте сидел такой же скучающий ЛКШонок, которому в голову пришел точно такой же алгоритм? Если это так, то сколько же шагов он успел проделать, прежде чем у него кончилось терпение?

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

В первой строке записан фрагмент строки из строчных латинских букв, выписанной моим предшественником. Длина фрагмента положительная и не превосходит 100000.

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

Выведите единственное число - минимальное количество шагов алгоритма, которое должен был выполнить мой предшественник, чтобы в выписанной им строке встречался такой фрагмент. Если я ошибся, и фрагмент нельзя получить таким образом, выведите "-1".

Пример

Входные данные #1
bacab
Выходные данные #1
3