Усталость и терпение
Учиться в A0 непросто. Я очень устал. Сейчас жарко и душно, моя нога болит после вчерашнего футбола, я не выспался и не понял вчера алгоритм Штора-Вагнера. Что хуже всего, сейчас идет лекция, я плохо понимаю то, что нам рассказывают, и мне очень хочется спать. Чтобы не провалиться в сон, я начал выписывать длинную строку по следующему алгоритму:
На первом шаге я выписал строку "a".
На i-м шаге (i ≥ 2) к строке S, выписанной на предыдущем шаге, я приписал i-ю букву латинского алфавита, а потом еще раз приписал строку S.
Уже после четырех шагов я получил строку "abacabadabacaba" и собирался продолжить свое занятие, как вдруг...
Я заметил на полу клочок бумаги, на котором была написана удивительно похожая последовательность букв. Может, это фрагмент строки, которая получится после того, как я выполню несколько шагов своего алгоритма? Неужели когда-то давно на моем месте сидел такой же скучающий ЛКШонок, которому в голову пришел точно такой же алгоритм? Если это так, то сколько же шагов он успел проделать, прежде чем у него кончилось терпение?
Входные данные
В первой строке записан фрагмент строки из строчных латинских букв, выписанной моим предшественником. Длина фрагмента положительная и не превосходит 100000.
Выходные данные
Выведите единственное число - минимальное количество шагов алгоритма, которое должен был выполнить мой предшественник, чтобы в выписанной им строке встречался такой фрагмент. Если я ошибся, и фрагмент нельзя получить таким образом, выведите "-1".