Problem Description

Finn is playing a game called "Flip it and Stick it," abbreviated as FiSi. FiSi is a single-player game where the objective is to manipulate two strings \( S \) and \( T \) consisting of 0s and 1s. Finn can perform the following type of operation:

Select a substring of \( S \) and reverse it, then paste the parts of the string together in their original order to form a new string \( S \).
For example, Finn can take the string \( S = 101100 \), select the substring starting at the 2nd position \( 011 \) (string indexing starts from 1), and create the string \( S = 111000 \) in one operation.

Finn wins the game if \( S \) does not contain \( T \) as a substring. Your task is to help Finn determine the minimum length of the operation sequence needed to win the game, or inform him that it is impossible to win.

Input Format

The first line contains a string \( S \).

The second line contains a string \( T \).

Output Format

Output a single integer, which is the minimum number of operations required to win the game, or output \(-1\) if it is impossible to win.

Sample Input and Output

Sample Input #1

100110
10

Sample Output #1

2

Sample Input #2

000
00

Sample Output #2

-1

Notes/Hints

Sample Explanation 1

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

For example, his first operation could be to reverse the substring from the 4th to the 6th position (\( 110 \)), resulting in \( 100011 \). Then, his second operation could be to reverse the substring from the 1st to the 4th position (\( 1000 \)), resulting in \( 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 data, \( 1 \leq |S| \leq 2 \times 10^5 \) and \( 1 \leq |T| \leq 3 \).

Let \( |T| = l \).

见题面 Input 部分

见题面 Output 部分