CF1231E.Middle-Out

本题灵感来源于《吹笛人》的故事。在 Hooli 的压缩竞争对手 Nucleus 发起挑战后，Richard 熬夜发明了一种新的压缩方法：middle-out。

给定两个长度相同的字符串 $s$ 和 $t$，它们的字符从左到右编号为 $1$ 到 $n$（即从开头到结尾）。

每次操作你可以进行以下动作：

• 选择任意一个合法的下标 $i$（$1 \le i \le n$），
• 将 $s$ 的第 $i$ 个字符移动到字符串的开头，或者将 $s$ 的第 $i$ 个字符移动到字符串的结尾。

注意，这些操作不会改变字符串 $s$ 的长度。你只能对字符串 $s$ 进行操作。

例如，若 $s=$ "test"，一次操作后可以得到：

• 如果 $i=1$ 并且移动到开头，结果为 "test"（字符串不变）；
• 如果 $i=2$ 并且移动到开头，结果为 "etst"；
• 如果 $i=3$ 并且移动到开头，结果为 "stet"；
• 如果 $i=4$ 并且移动到开头，结果为 "ttes"；
• 如果 $i=1$ 并且移动到结尾，结果为 "estt"；
• 如果 $i=2$ 并且移动到结尾，结果为 "tste"；
• 如果 $i=3$ 并且移动到结尾，结果为 "tets"；
• 如果 $i=4$ 并且移动到结尾，结果为 "test"（字符串不变）。

你希望通过最少的操作次数将字符串 $s$ 变为字符串 $t$。如果无法将 $s$ 变为 $t$，输出 $-1$。

第一行包含一个整数 $q$（$1 \le q \le 100$），表示输入中独立测试用例的数量。

每个测试用例包含三行。第一行为一个整数 $n$（$1 \le n \le 100$），表示字符串 $s$ 和 $t$ 的长度。第二行为字符串 $s$，第三行为字符串 $t$。$s$ 和 $t$ 均为长度为 $n$ 的仅包含小写拉丁字母的字符串。

测试用例中 $n$ 的总和没有限制（即允许 $q=100$ 且所有 $n=100$ 的输入）。

对于每个测试用例，输出将 $s$ 变为 $t$ 所需的最小操作次数。如果无法完成转换，输出 $-1$。

在第一个示例中，一种最优操作方案如下：

• 对于第一个测试用例 $s=$ "iredppipe"，$t=$ "piedpiper"： "iredppipe" $\rightarrow$ "iedppiper" $\rightarrow$ "piedpiper"；
• 对于第二个测试用例 $s=$ "estt"，$t=$ "test"： "estt" $\rightarrow$ "test"；
• 对于第三个测试用例 $s=$ "tste"，$t=$ "test"： "tste" $\rightarrow$ "etst" $\rightarrow$ "test"。

由 ChatGPT 4.1 翻译