Трансформація рядків#5598
Маємо два рядки і , що складаються з літер a і b. Наша мета — перетворити рядок на за допомогою наступної операції обміну: можна вибрати два неперетинні фрагменти ab і ba в першому рядку і поміняти їх місцями. Чи можливо перетворити на за допомогою певної послідовності таких операцій?
Перший рядок містить одне число (2 \leq n \leq 10^6) — довжину рядків. Далі йдуть два рядки, кожен з яких складається з літер a та/або b. Перший рядок описує , другий рядок описує . Вважайте, що рядки різні.
У першому рядку виведіть слово TAK (польське так) або NIE (польське ні), якщо можна перетворити на за допомогою операцій обміну.
Якщо відповідь позитивна і n \leq 4000, програма повинна вивести приклад послідовності операцій обміну. У першому рядку виведіть кількість операцій (1 \leq m \leq 10^6). Кожен з наступних рядків містить два цілих числа a_i, b_i (1 \leq a_i, b_i \leq n-1) — позиції початкових літер фрагментів, які обмінюються: a_i вказує на позицію ab, b_i вказує на позицію ba.
Якщо існує декілька рішень, виведіть будь-яке з них. Зокрема, вам не потрібно мінімізувати кількість операцій, тобто число .
Приклад 1
Приклад 2