Вам даны две строки \(s\) и \(t\), каждая из которых имеет длину \(n\) и состоит из строчных букв латинского алфавита. Вы хотите сделать \(s\) равной \(t\).
Вы можете выполнить следующую операцию над \(s\) любое количество раз, чтобы достичь этого —
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Найдите минимальное количество операций, необходимых для преобразования \(s\) в \(t\), или определите, что это невозможно.
Выходные данные
Для каждого набора входных данных выведите минимальное количество операций для преобразования \(s\) в \(t\). Если невозможно преобразовать \(s\) в \(t\), вместо этого выведите \(-1\).
Примечание
Для первого набора входных данных, поскольку \(s\) и \(t\) равны, вам не нужно применять какие-либо операции.
Для второго набора входных данных вам нужно применить только одну операцию ко всей строке ab, чтобы преобразовать ее в ba.
Для третьего набора входных данных вам нужно только применить одну операцию ко всей строке abc, чтобы преобразовать ее в cab.
Для четвертого набора входных данных вам нужно применить операцию дважды: сначала для всей строки abc, чтобы преобразовать ее в cab, а затем для подстроки длины \(2\), начинающейся со второго символа для преобразования ее в cba.
Для пятого набора входных данных вам нужно применить только одну операцию ко всей строке abab, чтобы преобразовать ее в baba.
Для шестого набора входных данных превратить строку \(s\) в строку \(t\) не является возможным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
a
a
2
ab
ba
3
abc
cab
3
abc
cba
4
abab
baba
4
abcc
aabc
|
0
1
1
2
1
-1
|