시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

Given a string of even length $s = s_1 \ldots s_n$, we define $\mathrm{shuffle}$ operation which transforms a string into a new string according to the following rule:

$$\mathrm{shuffle}(s) = s_1 s_3 \ldots s_{n-1} s_2 s_4 \ldots s_n$$

For example, $\mathrm{shuffle}(\texttt{abcdef}) = \texttt{acebdf}$.

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 $\underbrace{\mathrm{shuffle}(\mathrm{shuffle}(\dots \mathrm{shuffle}}_{k\ \mathrm{times}} (s)\dots)) = t$ 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 \leq |s| \leq 10^6$, $|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.

예제 입력 1

abcdef
aedcbf

예제 출력 1

2

예제 입력 2

petrozavodsk
poztsvoedark

예제 출력 2

3

예제 입력 3

qwerty
ytrewq

예제 출력 3

-1