题目描述

译自 $CCO$ $2023$ $Day2$ $T1$「$Binaria$」。

Finn 正在玩一款名为「$Flip$ $it$ $and$ $Stick$ $it$」（简称 $FiSi$）的单人游戏，玩法是在两个由 $0$ 和 $1$ 组成的字符串 $S$ 和 $T$ 上进行操作。Finn 可进行的操作形式为： 选择 $S$ 的一个子串并将其翻转，再将字符串各部分按原顺序粘贴，形成新的 $S$。

例如，若 $S=101100$，选择从第 $2$ 位开始的子串 $011$ 翻转，可得到新 $S=111000$（字符串编号从 $1$ 开始）。

若操作后 $S$ 不包含 $T$ 作为子串，则 Finn 获胜。你的任务是确定 Finn 获胜所需的最短操作序列长度，若无法获胜则输出 $-1$。

输入格式

• 第一行：一个字符串 $S$。
• 第二行：一个字符串 $T$。

输出格式

输出一行一个整数，表示最少操作次数；若无法获胜则输出 $-1$。

样例 1

输入

100110
10

输出

2

说明

Finn 无法通过 $1$ 次操作让 $S$ 不包含 $10$，但 $2$ 次操作可以实现：

1. 翻转第 $4$ 到 $6$ 位的子串 $110$，得到 $100011$；
2. 翻转第 $1$ 到 $4$ 位的子串 $1000$，得到 $000111$（不含子串 $10$）。

样例 2

输入

000
00

输出

-1

说明

无论进行多少次操作，$S$ 始终包含子串 $00$，无法获胜。

数据范围与提示

• 对于所有数据：$1 \leq |S| \leq 2 \times 10^5$，$1 \leq |T| \leq 3$。
• 子任务信息如下：