405904: GYM102155 F Shuffle

Given a string of even length s = s₁... s_n, 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.

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

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.

abcdef
aedcbf

2

petrozavodsk
poztsvoedark

3

qwerty
ytrewq

-1