题目描述

Alex_Wei（以下简称小 A）有一个字符串 $s$。他觉得 $s$ 太冗长了，很不优美，于是想把它变成字符串 $t$。

具体地，他可以每次砍掉 $s$ 的一个前缀或后缀 $s'$，但必须保证 $s'$ 是切割后 $s$ 的子串。小 A 想请你帮他 求出最少操作次数，若无解输出 $-1$。

输入格式

两行字符串，分别表示 $s$ 和 $t$。

输出格式

一行一个整数，表示答案。

样例

abbabb
ba

3

abbabb$\to$abba$\to$bba$\to$ba。方案不唯一。

fxofoxxooffoxooo
fox

8

fxofoxxooffoxooo$\to$xofoxxooffoxooo$\to$foxxooffoxooo$\to$xooffoxooo$\to$ffoxooo$\to$ffoxoo$\to$ffoxo$\to$ffox$\to$fox。方案可能不唯一。

tzcakioi
ycxakioi

-1

abc
ac

-1

见附加文件 cutstring5.in

见附加文件 cutstring5.ans

该样例满足 Subtask 3 的限制。

见附加文件 cutstring6.in

见附加文件 cutstring6.ans

该样例满足 Subtask 5 的限制。

数据范围

对于 $100\%$ 的数据，$1\le |t|\le |s|\le 5\times 10^3$，字符集 $\in[a,z]$。