Problem Description

Finn is playing a game called “Flip it and Stick it”, abbreviated as FiSi. FiSi is a single-player game played on two strings $S$ and $T$ consisting of 0s and 1s. Finn can perform the following type of operation:

Choose a substring of $S$ and reverse it, then stick the parts of the string back together in the original order to form a new string $S$. For example, Finn can take the string $S=101100$, choose the substring $011$ starting from position 2 (the string is indexed from $1$), and create the string $S=111000$ in one operation.

If $S$ does not contain $T$ as a substring, Finn wins the game. Your task is to help Finn determine the length of the shortest sequence of operations needed to win the game, or tell him that the game cannot be won.

Input Format

The first line contains a string $S$.

The second line contains a string $T$.

Output Format

Output one line containing an integer: the minimum number of operations needed to win if it is possible, otherwise output $-1$.

100110
10

2

000
00

-1

Hint

Sample Explanation 1

Finn starts from the string $100110$. He cannot make $10$ not be a substring with one operation, but he can do it in two operations.

For example, his first operation can be to reverse the substring from position 4 to position 6 ($110$), obtaining $100011$. Then, his second operation can be to reverse the substring from position 1 to position 4 ($1000$), obtaining $000111$, which does not contain $10$ as a substring.

Sample Explanation 2

No matter how many operations Finn performs, the string $T$ will always be a substring of $S$.

For all testdata, $1 \leq|S| \leq 2\times 10^5$, $1 \leq|T| \leq 3$.

Let $|T|=l$.

Translated by ChatGPT 5