AT_agc007_f [AGC007F] Shik and Copying String

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_f シックの仕事はコピー取りです。ある日、シックは上司から英小文字からなる長さ $ 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` と答えてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 1,000,000 $ - $ S_0 $ と $ T $ の長さはともに $ N $ である。 - $ S_0 $ と $ T $ はともに英小文字のみからなる。 ### Sample Explanation 1 $ S_0 $ = `abcde`, $ S_1 $ = `aaccc`, $ S_2 $ = `aaacc` のように、$ S_2\ =\ T $ となる可能性が存在します。