Даны строка \(x\) длины \(n\) и строка \(s\) длины \(m\) (\(n \cdot m \le 25\)), состоящие из строчных латинских букв. Вы можете применить любое количество операций к строке \(x\).
За одну операцию вы приписываете текущее значение строки \(x\) к концу \(x\). Обратите внимание, что значение \(x\) после этого изменится.
Например, если \(x =\)«aba», то при применении операций \(x\) будет меняться следующим образом: «aba» \(\rightarrow\) «abaaba» \(\rightarrow\) «abaabaabaaba».
После какого минимального количества операций \(s\) встретится в \(x\) в качестве подстроки? Подстрокой строки называется любой её непрерывный отрезок.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное количество операций, после которых \(s\) встретится в \(x\) в качестве подстроки. Если это невозможно, выведите \(-1\).
Примечание
В первом наборе входных данных примера, после \(2\) применений операции строка станет равна «aaaa», а после \(3\) «aaaaaaaa», так что ответ \(3\).
Во втором наборе входных данных примера после применения \(1\) операции строка станет равна «\(\text{e}\color{red}{\text{force}}\text{forc}\)», вхождение подстроки выделено красным.
В четвёртом наборе входных данных примера можно показать, что получить нужную строку как подстроку невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12
1 5
a
aaaaa
5 5
eforc
force
2 5
ab
ababa
3 5
aba
ababa
4 3
babb
bbb
5 1
aaaaa
a
4 2
aabb
ba
2 8
bk
kbkbkbkb
12 2
fjdgmujlcont
tf
2 2
aa
aa
3 5
abb
babba
1 19
m
mmmmmmmmmmmmmmmmmmm
|
3
1
2
-1
1
0
1
3
1
0
2
5
|