前缀连接

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

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

对于 $1\le i\le |S|$，记 $S_i$ 为 $S$ 的长度为 $i$ 的前缀。请找到最小正整数 $k$，使得存在 $1\le a_1,a_2,\ldots,a_k\le |S|$，满足

其中加号表示字符串连接。

若无法表示，输出 $-1$。

输入格式

第一行包含字符串 $S$。

第二行包含字符串 $T$。

输出格式

若可以表示，输出所需前缀数量的最小值；否则输出 $-1$。

样例输入 1

aba
ababaab

样例输出 1

3

样例输入 2

atcoder
ac

样例输出 2

-1

数据范围

对于所有数据：

• $1\le |S|\le5\times10^5$；
• $1\le |T|\le5\times10^5$；
• $S,T$ 只包含小写英文字母。