eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кактусы в ряд

Кактусы в ряд

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

К приезду президентля в "Бередееуэ Полянтли" было решено пересадить кактусы. Сейчас кактусы расположены в ряд, и известен вид каждого кактуса.

Шаман дизайна Эогенкуприлянтль хочет пересадить кактусы и тем самым добиться новой, более гармоничной последовательности видов кактусов.

Эогенкуприлянтль возьмёт с собой некоторое количество учеников (обозначим это количество m), после чего произвольное число раз проведёт следующую процедуру:

  • Эогенкуприлянтль выбирает k подряд растущих кактусов (km);

  • k учеников выкорчёвывают эти кактусы из сухой индейской земли;

  • Эогенкуприлянтль меняет некоторых учеников местами на своё усмотрение;

  • Каждый ученик закапывает кактус на том месте, где он стоит.

Ни один кактус не может быть выкорчеван и посажен более одного раза.

Какое минимальное количество учеников понадобиться Эогенкуприлянтлю, чтобы переупорядочить кактусы желаемым образом?

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

Первая и вторая строка содержат описание текущей и желаемой последовательности видов кактусов. Каждое из описаний представляет собой строку, состоящую из строчных латинских букв. Разные буквы соответствуют разным видам кактусов. Обе строки имеют одинаковую длину, не превышающую 100000.

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

Если добиться желаемой последовательности видов кактусов невозможно, выведите -1. В противном случае выведите неотрицательное число m - минимальное количество учеников, необходимое для получения искомого результата.

Пример

Входные данные #1
arabcabrad
abracadbra
Выходные данные #1
4