Home


Contest: Task: Related: TaskE TaskG

Score : $1500$ points

Problem Statement

Shik's job is very boring. At day $0$, his boss gives him a string $S_0$ of length $N$ which consists of only lowercase English letters. In the $i$-th day after day $0$, Shik's job is to copy the string $S_{i-1}$ to a string $S_i$. We denote the $j$-th letter of $S_i$ as $S_i[j]$.

Shik is inexperienced in this job. In each day, when he is copying letters one by one from the first letter to the last letter, he would make mistakes. That is, he sometimes accidentally writes down the same letter that he wrote previously instead of the correct one. More specifically, $S_i[j]$ is equal to either $S_{i-1}[j]$ or $S_{i}[j-1]$. (Note that $S_i[1]$ always equals to $S_{i-1}[1]$.)

You are given the string $S_0$ and another string $T$. Please determine the smallest integer $i$ such that $S_i$ could be equal to $T$. If no such $i$ exists, please print -1.

Constraints

  • $1 \leq N \leq 1,000,000$
  • The lengths of $S_0$ and $T$ are both $N$.
  • Both $S_0$ and $T$ consist of lowercase English letters.

Input

The input is given from Standard Input in the following format:

$N$
$S_0$
$T$

Output

Print the smallest integer $i$ such that $S_i$ could be equal to $T$. If no such $i$ exists, print -1 instead.


Sample Input 1

5
abcde
aaacc

Sample Output 1

2

$S_0$ = abcde, $S_1$ = aaccc and $S_2$ = aaacc is a possible sequence such that $S_2 = T$.


Sample Input 2

5
abcde
abcde

Sample Output 2

0

Sample Input 3

4
acaa
aaca

Sample Output 3

2

Sample Input 4

5
abcde
bbbbb

Sample Output 4

-1

配点 : $1500$ 点

問題文

シックの仕事はコピー取りです。ある日、シックは上司から英小文字からなる長さ $N$ の文字列 $S_0$ を受け取りました(この日を $0$ 日目とします)。これ以降、$i$ 日目の仕事は、文字列 $S_{i-1}$ を $S_i$ にコピーすることです。以下、$S_i$ の $j$ 番目の文字を $S_i[j]$ と表します。

シックはまだこの仕事に慣れていません。毎日、文字列を先頭の文字から順に書き写していくのですが、正しい文字の代わりに誤って直前に書いた文字と同じ文字を書いてしまうことがあります。すなわち、$S_i[j]$ は $S_{i-1}[j]$ または $S_{i}[j-1]$ のどちらかと等しくなります。(ただし、文字列の先頭の文字を書き間違えることはありません。すなわち、$S_i[1]$ は必ず $S_{i-1}[1]$ と等しくなります。)

二つの文字列 $S_0$ と $T$ が与えられます。$S_i$ が $T$ と等しくなる可能性があるような最小の整数 $i$ を求めてください。もしそのような $i$ が存在しなければ、代わりに -1 と答えてください。

制約

  • $1 \leq N \leq 1,000,000$
  • $S_0$ と $T$ の長さはともに $N$ である。
  • $S_0$ と $T$ はともに英小文字のみからなる。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$S_0$
$T$

出力

$S_i$ が $T$ と等しくなる可能性のあるような $i$ が存在するならば、そのような $i$ のうち最小のものを出力せよ。そのような $i$ が存在しなければ、代わりに -1 と出力せよ。


入力例 1

5
abcde
aaacc

出力例 1

2

$S_0$ = abcde, $S_1$ = aaccc, $S_2$ = aaacc のように、$S_2 = T$ となる可能性が存在します。


入力例 2

5
abcde
abcde

出力例 2

0

入力例 3

4
acaa
aaca

出力例 3

2

入力例 4

5
abcde
bbbbb

出力例 4

-1