Трансформация строк
Имеются две строки u и v, состоящие из букв a и b. Наша цель - преобразовать строку uв v используя следующую операцию обмена: разрешается выбрать два непересекающихся фрагмента ab и ba в первой строке и поменять их местами. Можно ли u преобразовать в v используя некоторую последовательность операций обмена?
Входные данные
Первая строка содержит одно число n (2 ≤ n ≤ 10^6) - длину строк. Далее следуют две строки, каждая из которых состоит из n букв a и/или b. Первая строка описывает u, вторая строка описывает v. Считайте, что строки разные.
Выходные данные
В первой строке выведите слово TAK (польское да) или NIE (польское нет) если u можно преобразовать в v используя операции обмена.
Если ответ положительный и n ≤ 4000, программа должна вывести пример последовательности операций обменов. В первой строке вывести количество операций m (1 ≤ m ≤ 10^6). Каждая из следующих m строк содержит два целых числа a[i], b[i] (1 ≤ a[i], b[i] ≤ n - 1) - позиции начальных букв фрагментов, которые обмениваются: a[i] указывает на позицию ab, b[i] указывает на позицию ba.
Если существует несколько решений, выведите любое из них. В частности, Вам не следует минимизировать количество операций, то есть число m.