
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 nondecreasing 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. InputThere 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$. OutputFor 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. Sample Input2 001122 000022 Sample Output2 4 5 1 1 1 Author: LIN, Xi Source: Yet Another Xi Lin Contest 