Minimum Swaps to Make Palindrome

You are given a string s consisting only of the characters 0 and 1. In each operation you may swap the characters at any two positions i and j (they do not need to be adjacent). Find the minimum number of swaps needed to turn s into a palindrome; if it cannot be done, output −1.

A palindrome reads the same forward and backward. For example, "0", "111", "010" and "10101" are palindromes, while "001", "10" and "11101" are not.

输入格式

One line containing a 01 string s. 1≤length of s≤10^6.

输出格式

Output a single integer, the minimum number of swaps, or −1 if there is no solution.

样例 1

输入：

0100101

输出：

2

样例 2

输入：

10

输出：

-1

样例 3

输入：

0011

输出：

1

样例说明

Example 1: s="0100101" (1-indexed). Swapping (4,5) gives "0101001", and then swapping (1,2) gives "1001001", for 2 swaps in total; one swap is not enough, so the answer is 2. Example 2: "10" has only one 1, and an even-length palindrome needs an even number of 1s, so the answer is −1. Example 3: swapping the 1st and 3rd characters of "0011" gives "1001" in a single swap, so the answer is 1.