Кактуси у рядок#4330
До приїзду президентля у Бередеує Полянтлі було вирішено пересадити кактуси. Зараз кактуси розміщені у рядок, і відомий вид кожного кактуса.
Шаман-дизайнер Еогенкупрілянтль хоче пересадити кактуси й таким чином досягти нової, більш гармонійної послідовності видів кактусів.
Еогенкупрілянтль візьме з собою певну кількість учнів (позначимо цю кількість через ), після чого необмежену кількість разів буде виконувати наступну процедуру:
Еогенкупрілянтль вибирає кактусів, які ростуть підряд (k \leq m);
учнів викорчовують ці кактуси із сухої індіанської землі;
Еогенкупрілянтль міняє деяких учнів місцями на свій розсуд;
Кожен учень закопує кактус на те місце, де він тепер стоїть.
Жоден кактус не може бути викорчуваний і посаджений більше одного разу.
Яка мінімальна кількість учнів знадобиться Еогенкупрілянтлю, щоб пересадити кактуси у бажаній послідовності?
Перший і другий рядки містять опис поточної та бажаної послідовності видів кактусів. Кожен опис являє собою рядок із малих латинських літер. Різні літери відповідають різним видам кактусів. Обидва рядки мають однакову довжину, яка не перевищує .
Якщо отримати бажану послідовність видів кактусів неможливо, виведіть . В іншому випадку виведіть невід'ємне число — мінімальну кількість учнів, необхідну для досягнення шуканого результату.
Приклад 1