← 返回题目列表

Codeforces · 1363/F

F. 旋转子串

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

给定两个字符串 $$$s$$$ 和 $$$t$$$,每个字符串的长度为 $$$n$$$ 并由小写拉丁字母组成。您想让 $$$s$$$ 等于 $$$t$$$。

您可以对 $$$s$$$ 执行以下操作任意次来实现 —

- 选择$$$s$$$的任意子串,顺时针旋转一次,即如果选择的子串是$$$s[l,l+1...r]$$$,那么它就变成$$$s[r,l,l + 1 ... r - 1]$$$。 $$$s$$$ 的所有剩余字符保持在其位置。例如,在旋转子字符串 $$$[2,4]$$$ 时,字符串“abcde”变为“adbce”。

字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

求将 $$$s$$$ 转换为 $$$t$$$ 所需的最少操作数,或者确定这是不可能的。

输入

输入的第一行包含一个整数 $$$t$$$ $$$(1\leq t \leq 2000)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1\leq n \leq 2000)$$$ — 字符串的长度。

第二行和第三行分别包含字符串 $$$s$$$ 和 $$$t$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,输出将 $$$s$$$ 转换为 $$$t$$$ 的最小操作数。如果无法将 $$$s$$$ 转换为 $$$t$$$,则输出 $$$-1$$$。

示例

输入 #1

6
1
a
a
2
ab
ba
3
abc
cab
3
abc
cba
4
abab
baba
4
abcc
aabc

输出 #1

0
1
1
2
1
-1

注意

对于 $$$1$$$-st 测试用例,由于 $$$s$$$ 和 $$$t$$$ 相等,因此不需要应用任何操作。

对于$$$2$$$-nd测试用例,只需对整个字符串ab进行一次操作即可将其转换为ba。

对于$$$3$$$-rd测试用例,只需对整个字符串abc进行一次操作即可将其转换为cab。

对于第 $$$4$$$ 个测试用例,您需要应用两次操作:首先对整个字符串 abc 将其转换为 cab,然后对从第二个字符开始的长度为 $$$2$$$ 的子字符串将其转换为 cba。

对于第 $$$5$$$ 测试用例,只需对整个字符串 abab 执行一次操作即可将其转换为 baba。

对于第 $$$6$$$ 个测试用例,无法将字符串 $$$s$$$ 转换为 $$$t$$$。