405904: GYM102155 F Shuffle

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Shuffletime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Given a string of even length s = s1... sn, we define operation which transforms a string into a new string according to the following rule:

For example, .

You are given two strings of equal even length, s and t. How many times do you have to apply shuffle operation to s in order to get t as a result?

In the other words, find minimum k such that or report that it is not possible to reach t in any number of operations.

Input

The first line of input contains a string s, the second contains a string t (|s| = |t|, 2 ≤ |s| ≤ 106, |s| is even). Both strings consist of lowercase English characters.

Output

Print minimum non-negative k such that it is possible to obtain t from s by applying shuffle operation k times (or maybe not applying at all if k = 0), or print -1 if it is impossible.

ExamplesInput
abcdef
aedcbf
Output
2
Input
petrozavodsk
poztsvoedark
Output
3
Input
qwerty
ytrewq
Output
-1

加入题单

上一题 下一题 算法标签: