시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 67 | 8 | 6 | 21.429% |
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, but solutions that find non-optimal sequences will still get some points. Read the scoring section for more detailed information.
The first line contains a string s (1 ≤ |s| ≤ 2 · 105).
The second line contains a string t (1 ≤ |t| ≤ 2 · 105).
Here |s| and |t| denote the lengths of s and t, respectively. It is guaranteed that at least one of the strings contains at least one a
letter and at least one of the strings contains at least one b
letter.
The first line should contain a single integer n (0 ≤ n ≤ 5 · 105)—the number of operations.
Each of the next n lines should contain two space-separated integers ai, bi—the lengths of prefixes of s and t to swap, respectively.
If there are multiple possible solutions, you can print any of them.
a
bab bb
2 1 0 1 3
bbbb aaa
0
In the first example, you can solve the problem in two operations:
ab
and bbb
.bbbb
and a
.In the second example, the strings are already appropriate, so no operations are needed.