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

문제

For a string $s$ consisting of only "a" and "b" , let $f(s)$ be the string obtained by replacing all "a" in $s$ with "aa" and "b" with "ab". For example, $f($"aba"$)$ = "aaabaa".

Given strings $s$ and $t$, determine the smallest non-negative integer $k$ where $t$ is a consecutive substring of $f^k(s)$.

Note that $f^k$ is defined by:

  • $f^0(s) = s$;
  • $f^k(s) = f^{k - 1}(f(s))$.

입력

The first and second lines contain string $s$ and $t$ respectively ($1 \leq |s|, |t| \leq 2 \cdot 10^5$).

Strings $s$ and $t$ consist of only characters "a" and "b".

출력

A single integer denotes the minimum $k$.

If $k$ does not exists, print "-1" instead.

예제 입력 1

b
ab

예제 출력 1

1

예제 입력 2

ababa
bab

예제 출력 2

0

예제 입력 3

a
b

예제 출력 3

-1