题目描述

Freda最近得到了一个信号发生器,它的开关是一串由小写字母组成的字符串,这个字符串中相邻的两个字母可以互相交换。据说只有用最少的交换次数把这个字符串变成回文串,这个信号发生器才能开启。不过这个问题对于Freda来说太简单了,于是她想考考你。

输入格式

一个仅含有小写英文字母的字符串。

输出格式

一个整数,表示最少交换次数。无解输出-1。

样例输入

abab

样例输出

1

数据范围与约定

对于10%的数据,字符串长度不超过20。

对于40%的数据,字符串长度不超过2000。

对于70%的数据,字符串长度不超过100000。

在其中均匀分布着20%的数据,字符串中仅含有a和b。

对于100%的数据,字符串长度不超过1000000。