|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||7||2||2||100.000%|
There are two strings s and t, consisting only of letters
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
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.
2 1 0 1 3
In the first example, you can solve the problem in two operations:
In the second example, the strings are already appropriate, so no operations are needed.