Transformacje

Limit pamięci: 128 MB

Dane są dwa słowa i złożone z liter a i b. Naszym celem jest przekształcić słowo w słowo . 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ć w ?

Wejście

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

Wyjście

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

Jeśli odpowiedź jest twierdząca oraz , 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ą (), oznaczającą liczbę operacji. Każdy z kolejnych wierszy powinien zawierać dwie liczby całkowite , (), oznaczające pozycje pierwszych liter zamienianych fragmentów ab (odpowiednio ) i ba (odpowiednio ).

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 .

Przykład

Dla danych wejściowych:

6
aabbaa
baaaab

poprawną odpowiedzią jest:

TAK
2
2 4
1 5

natomiast dla danych:

6
aaabbb
ababab

poprawną odpowiedzią jest:

NIE

Autor zadania: Adam Polak.