题目描述

给定两个由小写英文字母组成的字符串 $S$ 和 $T$。

找到最小的正整数 $k$，使得你可以选择 $k$ 个 $S$ 的前缀（可以不唯一），使得它们的连接与 $T$ 相等。

换句话说，找到最小的正整数 $k$，使得存在一个 $k$ 元组 $(a_1,a_2,\\ldots, a_k)$，其中 $a_i$ 是介于 $1$ 和 $|S|$ 之间的整数，满足
$T=S_{a_1}+S_{a_2}+\\cdots +S_{a_k}$，这里 $S_i$ 表示从第 $1$ 个字符到第 $i$ 个字符的子串，$+$ 表示字符串的连接。

如果无法使其与 $T$ 相等，则打印 $-1$。

约束条件

• $1 \\leq |S| \\leq 5\\times 10^5$
• $1 \\leq |T| \\leq 5\\times 10^5$
• $S$ 和 $T$ 是由小写英文字母组成的字符串。

输入

从标准输入读入输入数据，输入格式如下：

$S$ $T$

输出

打印最小的正整数 $k$，使得你可以选择 $k$ 个 $S$ 的前缀，使得它们的连接与 $T$ 相等。如果无法使其与 $T$ 相等，则打印 $-1$。

示例输入1

aba
ababaab

示例输出1

3

$T=$ ababaab 可以写成 ab + aba + ab，其中 ab 和 aba 是 $S=$ aba 的前缀。
由于无法用 $S=$ aba 的两个或更少的前缀表示 ababaab，所以打印 $3$。

示例输入2

atcoder
ac

示例输出2

-1

由于无法用 $S$ 的前缀的连接来表示 $T$，所以打印 $-1$。