配点 : $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 と出力せよ。

5
abcde
aaacc

2

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

5
abcde
abcde

0

4
acaa
aaca

2

5
abcde
bbbbb

-1