← 返回题目列表

Codeforces · 1231/E

E. 中出

中文机器翻译题面 查看原题

这个问题的灵感来自于花衣魔笛手的故事。在受到 Hooli 的压缩竞争对手 Nucleus 的挑战后,Richard 通宵达旦地发明了一种新的压缩方法:中出(middle-out)。

给定两个字符串 $$$s$$$ 和 $$$t$$$,长度相同 $$$n$$$。他们的字符从左到右(即从开始到结束)编号为 $$$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。

示例

输入 #1

3
9
iredppipe
piedpiper
4
estt
test
4
tste
test

输出 #1

2
1
2

输入 #2

4
1
a
z
5
adhas
dasha
5
aashd
dasha
5
aahsd
dasha

输出 #2

-1
2
2
3

注意

在第一个示例中,最佳答案之一的移动是:

- 第一个测试用例 $$$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"。