У Монокарпа есть две строки \(s\) и \(t\) одинаковой длины, состоящие из латинских букв «a» и «b».
Монокарп хочет сделать строки \(s\) и \(t\) одинаковыми. Для этого он может выполнять следующие операции: выбрать в строке \(s\) позицию \(pos_1\), выбрать в строке \(t\) позицию \(pos_2\) и поменять местами буквы \(s_{pos_1}\) и \(t_{pos_2}\).
Перед вами стоит задача определить минимальное количество операций, которые должен сделать Монокарп, чтобы сделать строки \(s\) и \(t\) одинаковыми, а также вывести сами операции. Если невозможно сделать строки одинаковыми, сообщите об этом.
Выходные данные
Если невозможно сделать строки одинаковыми, выведите \(-1\).
В противном случае, в первую строку выведите целое число \(k\) — минимальное количество операций, которые нужно сделать, чтобы сделать строки одинаковыми. В каждой из следующих \(k\) строк выведите по два целых числа — позицию в строке \(s\) и позицию в строке \(t\), которые нужно использовать для обмена букв во время очередной операции.
Примечание
В первом примере достаточно двух операций обмена. Например, можно сначала поменять местами третью букву в строке \(s\) с третьей буквой в строке \(t\). После этого \(s = \) «abbb», \(t = \) «aaab». Затем нужно поменять третью букву в строке \(s\) со второй буквой в строке \(t\). После этого обе строки \(s\) и \(t\) будут равны «abab».
Во втором примере невозможно сделать строки одинаковыми.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
abab
aabb
|
2
3 3
3 2
|
|
2
|
1
a
b
|
-1
|
|
3
|
8
babbaabb
abababaa
|
3
2 6
1 3
7 8
|