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~?
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 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
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3