시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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 ai, bi (1 ≤ ai, bin - 1), oznaczające pozycje pierwszych liter zamienianych fragmentów ab (odpowiednio ai) i ba (odpowiednio bi).

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.

예제 입력 1

6
aabbaa
baaaab

예제 출력 1

TAK
2
2 4
1 5

예제 입력 2

6
aaabbb
ababab

예제 출력 2

NIE