8269번 - Transformacje 스페셜 저지다국어

Dane są dwa słowa u i v złożone z liter a i b. Naszym celem jest przekształcić słowo u w słowo v. Mamy w tym celu do dyspozycji następującą operację zamiany: wybieramy dwa rozłączne fragmenty ab i ba w pierwszym słowie i zamieniamy je miejscami. Czy, wykonując skończoną liczbę takich operacji, możemy przekształcić u w v?

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (2 ≤ n ≤ 1 000 000), oznaczającą długość słów. Każdy z dwóch następnych wierszy zawiera ciąg złożony z n znaków a i/lub b. Pierwszy wiersz opisuje słowo u, a drugi - słowo v. Możesz założyć, że słowa te będą różne.

W pierwszym wierszu wyjścia powinno znaleźć się jedno słowo TAK lub NIE, oznaczające, czy słowo u można przekształcić w słowo v, wykonując jedynie operacje zamiany.

Jeśli odpowiedź jest twierdząca oraz n ≤ 4 000, Twój program powinien także wypisać przykładowy ciąg operacji prowadzących do celu. Pierwszy wiersz tego opisu powinien zawierać jedną liczbę całkowitą m (1 ≤ m ≤ 1 000 000), oznaczającą liczbę operacji. Każdy z kolejnych m wierszy powinien zawierać dwie liczby całkowite a_i, b_i (1 ≤ a_i, b_i ≤ n - 1), oznaczające pozycje pierwszych liter zamienianych fragmentów ab (odpowiednio a_i) i ba (odpowiednio b_i).

Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien wypisać jakiekolwiek z nich. W szczególności Twoje rozwiązanie nie musi minimalizować liczby operacji, tj. liczby m.