Обратите внимание, что единственная разница между Трансформация строки 1 и Трансформация строки 2 заключается в операции, которую делает Коа. В этой версии буква \(y\), которую выбирает Koa, может быть любой из первых \(20\) букв английского алфавита (для лучшего понимания прочитайте условие). Вы можете делать взломы по этим задачам независимо.
Коала Коа имеет две строки \(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\) строчных букв английского алфавита).
- делает все буквы в позициях \(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\)-м наборе входных данных Koa:
- выбирает позиции \(1\) и \(2\) и устанавливает \(A_1 = A_2 = \) b (\(\color{red}{aa}b \rightarrow \color{blue}{bb}b\)).
- выбирает позиции \(2\) и \(3\) и устанавливает \(A_2 = A_3 = \) c (\(b\color{red}{bb} \rightarrow b\color{blue}{cc}\)).
- В \(2\)-м наборе входных данных Koa:
- выбирает позиции \(1\) и \(4\) и устанавливает \(A_1 = A_4 = \) a (\(\color{red}{c}ab\color{red}{c} \rightarrow \color{blue}{a}ab\color{blue}{a}\)).
- выбирает позиции \(2\) и \(4\) и устанавливает \(A_2 = A_4 = \) b (\(a\color{red}{a}b\color{red}{a} \rightarrow a\color{blue}{b}b\color{blue}{b}\)).
- выбирает позицию \(3\) и устанавливает \(A_3 = \) c (\(ab\color{red}{b}b \rightarrow ab\color{blue}{c}b\)).
- В \(3\)-м наборе входных данных Koa:
- выбирает позицию \(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
3
3
2
4
|