Cacti in a row
Before the president's visit to "Beredeue Polyantli," a decision was made to rearrange the cacti. Currently, the cacti are lined up in a row, and the species of each cactus is known.
The design shaman, Eogenkuprilyantl, aims to transplant the cacti to create a new, more harmonious sequence of species.
Eogenkuprilyantl will bring along a certain number of students (denoted as m) and will repeatedly perform the following steps:
Eogenkuprilyantl selects k consecutive cacti (k ≤ m);
k students uproot these cacti from the dry Indian soil;
Eogenkuprilyantl rearranges some of the students as he sees fit;
Each student plants a cactus in the spot where they are standing.
No cactus can be uprooted and replanted more than once.
What is the minimum number of students Eogenkuprilyantl will need to reorder the cacti into the desired sequence?
Input
The first and second lines contain the current and desired sequences of cactus species, respectively. Each sequence is a string of lowercase Latin letters, where different letters represent different cactus species. Both strings are of the same length, not exceeding 100000.
Output
If it is impossible to achieve the desired sequence of cactus species, output -1. Otherwise, output a non-negative number m - the minimum number of students required to achieve the desired result.