String Transformations
We are given two strings u and v composed of letters a and b. Our goal is to transform the string u into v using the following swap operation: choose two disjoint fragments ab and ba in the first string and swap them. Can u be transformed into v using a sequence of swap operations?
Input
The first line contains one integer n (2 ≤ n ≤ 10^6), the length of the strings. Two lines follow, each containing a string composed of n letters a and/or b. The first line describes the string u and the second line describes v. You can assume that the two strings differ.
Output
The first line should contain one word TAK (Polish for yes) or NIE (Polish for no) indicating if u can be transformed into v using the swap operations.
If the answer is positive and n ≤ 4000, your program should output an example sequence of swap operations. The first line should contain one integer m (1 ≤ m ≤ 10^6), the number of operations. Each of the following m lines should contain two integers a[i], b[i] (1 ≤ a[i], b[i] ≤ 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 m.