Summer Institute @ University of Central Florida: Contest 1, Problem 4

A YouTube Poop is a type of video which is a modification of another video, in which the modified video consists of several (possibly duplicate) clips of someone speaking in the original video, with an ordering which makes it sound like the speaker is saying something else. YouTube Poops are usually considered humorous and crude, but are almost universally considered of much higher quality when the YouTube Poop does not need to use as many clips to produce the desired mangled-up text the creator of the YouTube Poop intends.

Let's say string $A$ represents the speech given in an original video, and we want to create a YouTube Poop of the original video in which string $B$ represents the speech given in our YouTube Poop. What, then, is the minimum amount of substrings of $A$ needed to form string $B$?

Input Specification

The first line of input consists of the string $A$ $(1\le |A|\le {10}^5)$. The second line of input consists of the string $B$ $(1\le |B|\le {10}^5)$. All strings will only contain lower-case Latin letters.

Output Specification

Output the minimum number of substrings of $A$ necessary to form $B$. If it is not possible to take substrings of $A$ to make $B$, output -1.

Sample Input 1

abcbcd
abcd

Sample Output 1

2

Sample Input 2

iamsmart
iamdumb

Sample Output 2

-1

Sample Input 3

asmallmallinmalta
atallmallinlima

Sample Output 3

5