Minimum Operations to Transform String t to s

Given two strings \(t\) and \(s\), you can perform the following operation on string \(t\): remove a non-empty prefix or suffix of \(t\) (but not the entire string) such that the removed part appears as a contiguous substring in the remaining portion of \(t\) after the cut. Formally, if \(t\) has length \(n\) and you remove a prefix of length \(k\) (with \(1 \le k < n\)), then let \(x = t[0:k]\) and the new string becomes \(t[k:n]\); the operation is valid if and only if \(x\) is a substring of \(t[k:n]\). Similarly, you may remove a suffix of length \(k\) (with \(1 \le k .

Your task is to determine the minimum number of operations needed to transform \(t\) into \(s\). If it is not possible to obtain \(s\) from \(t\) via a sequence of valid operations, output \(-1\).

Note: A sequence of operations always results in a contiguous substring of the original string \(t\). All indices mentioned are 0-indexed. When comparing substrings, the match must be contiguous.

inputFormat

The input consists of two lines. The first line contains the string \(t\). The second line contains the string \(s\).

It is guaranteed that both strings are non-empty and consist of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of valid operations required to transform \(t\) into \(s\). If it is impossible, output \(-1\).

sample

ababa
aba

1