Problem Description

This problem is translated from PA 2022 Practice Round Palindrom.

Bytie attends a computer club, so he knows what a palindrome is. A palindrome is a word that reads the same from left to right and from right to left. For example, oko, kajak, kobyłamamałybok, and ababbaba are palindromes, but kajaki, zoo, alamakota, and abaababa are not.

He quickly opened his laptop and wrote down a word consisting only of the letters a and b. However, after thinking for a while, he remembered that this word is not necessarily a palindrome, so he decided to modify it. In one second, he can choose two adjacent letters and swap their positions. Can he turn this string into a palindrome using a finite number of operations (or by doing nothing)? If yes, what is the minimum number of seconds needed? Please help him write a program to compute this minimum time.

Input Format

One line containing a string, which is the word written by Bytie. The string contains only the letters a and b.

Output Format

Output one integer. If it is possible to transform the string into a palindrome using a finite number of operations, output the minimum time; otherwise output $-1$.

abbaaab

2

ab

-1

Hint

For $100\%$ of the testdata, the following holds:

The string length does not exceed $2 \times 10^5$.

Translated by ChatGPT 5