问题描述

#nck { width: 30px; height: auto; }

Shik 的工作非常无聊。在第 $0$ 天，他的老板给了他一个长度为 $N$ 的字符串 $S_0$，它只包含小写英文字母。在第 $i$ 天，Shik 的工作是将字符串 $S_{i-1}$ 复制到字符串 $S_i$ 中。我们用 S_i\[j\] 表示 $S_i$ 的第 $j$ 个字母。

Shik 在这份工作中没有经验。每天，当他一边从第一个字母复制到最后一个字母时，他会犯错误。也就是说，他有时会意外地写下之前写过的相同的字母，而不是正确的字母。具体来说，S_i\[j\] 可以等于 S_{i-1}\[j\] 或 S_{i}\[j-1\]。（注意，S_i\[1\] 总是等于 S_{i-1}\[1\]。）

给定字符串 $S_0$ 和另一个字符串 $T$。请确定最小的正整数 $i$，使得 $S_i$ 可以等于 $T$。如果不存在这样的 $i$，请输出 -1。

约束条件

• $1 \\leq N \\leq 1,000,000$
• $S_0$ 和 $T$ 的长度都为 $N$。
• $S_0$ 和 $T$ 只包含小写英文字母。

输入

输入以以下格式从标准输入给出：

$N$ $S_0$ $T$

输出

输出最小的正整数 $i$，使得 $S_i$ 可以等于 $T$。如果不存在这样的 $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