Anonymous Letter Cuts

FJ had a terrible fight with his neighbor and decided to send him an anonymous nasty letter. He plans to form the letter by cutting out contiguous snippets from an infinite supply of the latest issue of the Moo York Times. The newspaper contains \(N\) uppercase letters arranged in a long string and the message he wants to compose contains \(M\) letters. Both the newspaper and the message are read as a series of shorter strings, which when concatenated form the full text.

With a single straight cut, FJ can extract any contiguous snippet from the newspaper. He can take advantage of this by cutting out long segments if they appear in the newspaper. What is the minimum number of cuts required to compose his message?

It is guaranteed that it is always possible for FJ to create the message using the newspaper.

Example:

Newspaper (concatenation of input lines):
THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG
Message (concatenation of input lines):
FOXDOGDOG
Explanation:
Since "FOXDOG" appears in the newspaper, FJ can cut this segment out. Then he can get "DOG" by cutting out either occurrence of "DOG". Thus, he only needs 2 cuts.

inputFormat

The input consists of two parts. The first part is the newspaper text and the second part is the message text that FJ wants to form. Each part may be given as multiple lines, and you should consider the concatenation of these lines as the full text. In many cases, the input will be provided as exactly two lines: the first line is the newspaper text and the second line is the message text.

Both texts consist only of uppercase letters.

outputFormat

Output a single integer representing the minimum number of cuts FJ needs to make to form his letter.

If it is impossible (which will not occur in the given constraints) output -1.

sample

THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG
FOXDOGDOG

2