Обратите внимание, что единственная разница между Трансформация строки 1 и Трансформация строки 2 заключается в операции, которую делает Коа. В этой версии буква \(y\), которую выбирает Koa, должна быть строго больше по алфавиту, чем \(x\) (для лучшего понимания прочитайте условие). Вы можете делать взломы по этим задачам независимо.
У Коалы Коа есть две строки \(A\) и \(B\) одинаковой длины \(n\) (\(|A|=|B|=n\)), состоящие из первых \(20\) строчных букв английского алфавита (то есть от a до t).
В один ход Коа:
- выбирает некоторое подмножество позиций \(p_1, p_2, \ldots, p_k\) (\(k \ge 1; 1 \le p_i \le n; p_i \neq p_j\) если \(i \neq j\)) из \(A\), такое что \(A_{p_1} = A_{p_2} = \ldots = A_{p_k} = x\) (т. е. все буквы на этой позиции равны некоторой букве \(x\)).
- выбирает букву \(y\) (из первых \(20\) строчных букв английского алфавита) такую, что \(y>x\) (т. е. буква \(y\) в алфавитном порядке строго больше, чем \(x\)).
- делает все буквы в позициях \(p_1, p_2, \ldots, p_k\) равными \(y\). Более формально: для каждого \(i\) (\(1 \le i \le k\)) Коа устанавливает \(A_{p_i} = y\).
Обратите внимание, что вы можете изменять только буквы в строке \(A\).
Коа хочет знать наименьшее число ходов, которые она должна сделать, чтобы сделать строки равными друг другу (\(A = B\)) или определить, что нет никакого способа сделать их равными. Помогите ей!
Выходные данные
Для каждого набора входных данных:
Выведите в единственной строке минимальное количество ходов, которое Koa должна сделать, чтобы строки стали равны друг другу (\(A = B\)) или \(-1\), если нет никакого способа сделать их равными.
Примечание
- В \(1\)-м наборе входных данных Коа:
- выбирает позиции \(1\) и \(2\) и устанавливает \(A_1 = A_2 = \) b (\(\color{red}{aa}b \rightarrow \color{blue}{bb}b\)).
- выбирает позиции \(2\) b \(3\) и устанавливает \(A_2 = A_3 = \) c (\(b\color{red}{bb} \rightarrow b\color{blue}{cc}\)).
- Во \(2\)-м наборе входных данных Коа не может сделать строку \(A\) равной строке \(B\).
- В \(3\)-м наборе входных данных Коа:
- выбирает позицию \(1\) и устанавливает \(A_1 = \) t (\(\color{red}{a}bc \rightarrow \color{blue}{t}bc\)).
- выбирает позицию \(2\) и устанавливает \(A_2 = \) s (\(t\color{red}{b}c \rightarrow t\color{blue}{s}c\)).
- выбирает позицию \(3\) и устанавливает \(A_3 = \) r (\(ts\color{red}{c} \rightarrow ts\color{blue}{r}\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3 aab bcc 4 cabc abcb 3 abc tsr 4 aabd cccd 5 abcbd bcdda
|
2
-1
3
2
-1
|