Вдохновением для задачи послужила история компании Pied Piper. После анонса технологии Nucleus со стороны конкурирующей компании Hooli Ричард при содействии друзей изобрёл принципиально новый подход к сжатию: «из середины наружу».
Вам даны две строки \(s\) и \(t\) одинаковой длины \(n\). Пронумеруем их символы то \(1\) до \(n\) слева направо (т.е. от начала к концу)
За один ход вы можете сделать следующую последовательность действий:
- выбрать произвольный индекс \(i\) (\(1 \le i \le n\)),
- передвинуть \(i\)-й символ строки \(s\) с текущей позиции в начало строки или передвинуть \(i\)-й символ строки \(s\) с текущей позиции в конец строки.
Заметим, что длина строки \(s\) в результате хода не поменяется. Вы можете применить ход только к строке \(s\).
Например, если \(s=\)«test», то за один ход можно получить:
- если \(i=1\) и вы перемещаете символ в начало, то результат будет равен «test» (строка не изменяется),
- если \(i=2\) и вы перемещаете символ в начало, то результат будет равен «etst»,
- если \(i=3\) и вы перемещаете символ в начало, то результат будет равен «stet»,
- если \(i=4\) и вы перемещаете символ в начало, то результат будет равен «ttes»,
- если \(i=1\) и вы перемещаете символ в конец, то результат будет равен «estt»,
- если \(i=2\) и вы перемещаете символ в конец, то результат будет равен «tste»,
- если \(i=3\) и вы перемещаете символ в конец, то результат будет равен «tets»,
- если \(i=4\) и вы перемещаете символ в конец, то результат будет равен «test» (строка не изменяется).
Вы хотите преобразовать строку \(s\) в строку \(t\). Какое минимальное количество ходов для этого потребуется? Если преобразовать \(s\) в \(t\) невозможно, выведите -1.
Выходные данные
Для каждого набора входных данных выведите минимальное количество ходов, которое нужно чтобы превратить \(s\) в \(t\) или -1, если это сделать невозможно.