Олимпиадный тренинг

Задача . A. Трансформация строки 1


Обратите внимание, что единственная разница между Трансформация строки 1 и Трансформация строки 2 заключается в операции, которую делает Коа. В этой версии буква \(y\), которую выбирает Koa, должна быть строго больше по алфавиту, чем \(x\) (для лучшего понимания прочитайте условие). Вы можете делать взломы по этим задачам независимо.

У Коалы Коа есть две строки \(A\) и \(B\) одинаковой длины \(n\) (\(|A|=|B|=n\)), состоящие из первых \(20\) строчных букв английского алфавита (то есть от a до t).

В один ход Коа:

  1. выбирает некоторое подмножество позиций \(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\)).

  2. выбирает букву \(y\) (из первых \(20\) строчных букв английского алфавита) такую, что \(y>x\) (т. е. буква \(y\) в алфавитном порядке строго больше, чем \(x\)).

  3. делает все буквы в позициях \(p_1, p_2, \ldots, p_k\) равными \(y\). Более формально: для каждого \(i\) (\(1 \le i \le k\)) Коа устанавливает \(A_{p_i} = y\).

    Обратите внимание, что вы можете изменять только буквы в строке \(A\).

Коа хочет знать наименьшее число ходов, которые она должна сделать, чтобы сделать строки равными друг другу (\(A = B\)) или определить, что нет никакого способа сделать их равными. Помогите ей!

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит \(t\) (\(1 \le t \le 10\)) — количество наборов входных данных. Описание наборов входных данных приведено ниже.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 10^5\)) — длину строк \(A\) и \(B\).

Вторая строка каждого набора входных данных содержит строку \(A\) (\(|A|=n\)).

Третья строка каждого набора входных данных содержит строку \(B\) (\(|B|=n\)).

Обе строки состоят из первых строчных букв английского алфавита \(20\) (т.е. от a до t).

Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(10^5\).

Выходные данные

Для каждого набора входных данных:

Выведите в единственной строке минимальное количество ходов, которое Koa должна сделать, чтобы строки стали равны друг другу (\(A = B\)) или \(-1\), если нет никакого способа сделать их равными.

Примечание
  • В \(1\)-м наборе входных данных Коа:
    1. выбирает позиции \(1\) и \(2\) и устанавливает \(A_1 = A_2 = \) b (\(\color{red}{aa}b \rightarrow \color{blue}{bb}b\)).
    2. выбирает позиции \(2\) b \(3\) и устанавливает \(A_2 = A_3 = \) c (\(b\color{red}{bb} \rightarrow b\color{blue}{cc}\)).

  • Во \(2\)-м наборе входных данных Коа не может сделать строку \(A\) равной строке \(B\).

  • В \(3\)-м наборе входных данных Коа:
    1. выбирает позицию \(1\) и устанавливает \(A_1 = \) t (\(\color{red}{a}bc \rightarrow \color{blue}{t}bc\)).
    2. выбирает позицию \(2\) и устанавливает \(A_2 = \) s (\(t\color{red}{b}c \rightarrow t\color{blue}{s}c\)).
    3. выбирает позицию \(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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя