ZOJ Problem Set - 4079
A ternary string is a sequence of digits, where each digit is either $0$, $1$, or $2$.
Chiaki has a nonempty ternary string $s$. Initially, the characters are sorted in non-decreasing order (i.e. all $0$s appear before all $1$s and all $1$s appear before all $2$s). Chiaki would like to shuffle the characters such that no two consecutive characters have the same value using the following operation: choose two integers $l$ and $r$ ($l \le r$), take characters from position $l$ to position $r$ inclusively, and move them to the end of the string.
Chiaki would like to know the minimum number of operations needed.
There are multiple test cases. The first line of input is an integer $T$ indicates the number of test cases. For each test case:
The first line contains a ternary string $s$ ($1 \le |s| \le 10^6$).
It is guaranteed that the sum of all $|s|$ does not exceed $10^6$.
For each test case, output "-1" (without the quotes) if Chiaki can not shuffle the string using the operations described above. Otherwise, output an integer $k$ in the first line -- the minimum number of operations needed. Each of the next $k$ lines output two integers $l$ and $r$ -- denoting an operation.
2 001122 000022
2 4 5 1 1 -1
Author: LIN, Xi
Source: Yet Another Xi Lin Contest