String Transformations#5598
We are given two strings and composed of letters a and b. Our goal is to transform the string into using the following swap operation: choose two disjoint fragments ab and ba in the first string and swap them. Can be transformed into using a sequence of swap operations?
The first line contains one integer (2 \leq n \leq 10^6), the length of the strings. Two lines follow, each containing a string composed of letters a and/or b. The first line describes the string and the second line describes . You can assume that the two strings differ.
The first line should contain one word TAK (Polish for yes) or NIE (Polish for no) indicating if can be transformed into using the swap operations.
If the answer is positive and n \leq 4000, your program should output an example sequence of swap operations. The first line should contain one integer (1 \leq m \leq 10^6), the number of operations. Each of the following lines should contain two integers a_i, b_i (1 \leq a_i, b_i \leq n - 1), the positions of the starting letters of the fragments being swapped: a_i denotes the position of ab and b_i denotes the position of ba.
If there is more than one solution, your program should output any one of them. In particular, you do not need to minimize the number of operations, that is, the number .
Example 1
Example 2