Fatigue and Patience
Starting at A0 is challenging. I'm exhausted. It's hot and stuffy, my leg aches from yesterday's football game, I didn't get enough sleep, and I couldn't grasp the Stoer-Wagner algorithm. Worst of all, there's a lecture happening now, and I'm struggling to understand what's being taught while fighting off sleepiness. To stay awake, I began writing a long string using this algorithm:
In the first step, I wrote the string "a".
In the i-th step (i ≥ 2), I took the string S from the previous step, appended the i-th letter of the Latin alphabet to it, and then appended the string S again.
After just four steps, I ended up with the string "abacabadabacaba" and was about to continue when suddenly...
I noticed a piece of paper on the floor with a sequence of letters that looked strangely familiar. Could it be a fragment of the string that results from several steps of my algorithm? Is it possible that a similarly bored LKSH student once sat here and devised the same algorithm? If so, how many steps did my predecessor complete before they lost patience?
Input
The first line contains a fragment of a string of lowercase Latin letters, written by my predecessor. The length of the fragment is positive and does not exceed 100000.
Output
Output a single number - the minimum number of steps of the algorithm that my predecessor must have performed for such a fragment to appear in the string they wrote. If the fragment cannot be obtained in this way, output "-1".