CF1012D AB-Strings

There are two strings $ s $ and $ t $ , consisting only of letters a and b. You can make the following operation several times: choose a prefix of $ s $ , a prefix of $ t $ and swap them. Prefixes can be empty, also a prefix can coincide with a whole string. Your task is to find a sequence of operations after which one of the strings consists only of a letters and the other consists only of b letters. The number of operations should be minimized.

The first line contains a string $ s $ ( $ 1

The first line should contain a single integer $ n $ ( $ 0

In the first example, you can solve the problem in two operations: 1. Swap the prefix of the first string with length $ 1 $ and the prefix of the second string with length $ 0 $ . After this swap, you'll have strings ab and bbb. 2. Swap the prefix of the first string with length $ 1 $ and the prefix of the second string with length $ 3 $ . After this swap, you'll have strings bbbb and a. In the second example, the strings are already appropriate, so no operations are needed.