Rotating Substrings

题意翻译

给定两个长度为 $n$ 的字符串 $s$，$t$。定义一次操作为选择 $s$ 的一个子串 $s_{l, l +1, \dots, r}$，然后将之修改为 $s_{r, l, l + 1, l + 2, \dots, r - 1 }$。请求助使 $s$ 与 $t$ 相等的最小操作次数。无解输出 $-1$。 多组数据，$\sum n \leq 2000$，$s, t$ 中只有小写字母。 translated by @一扶苏一。

题目描述

You are given two strings $ s $ and $ t $ , each of length $ n $ and consisting of lowercase Latin alphabets. You want to make $ s $ equal to $ t $ . You can perform the following operation on $ s $ any number of times to achieve it — - Choose any substring of $ s $ and rotate it clockwise once, that is, if the selected substring is $ s[l,l+1...r] $ , then it becomes $ s[r,l,l + 1 ... r - 1] $ . All the remaining characters of $ s $ stay in their position. For example, on rotating the substring $ [2,4] $ , string "abcde" becomes "adbce". A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. Find the minimum number of operations required to convert $ s $ to $ t $ , or determine that it's impossible.

输入输出格式

输入格式

The first line of the input contains a single integer $ t $ $ (1\leq t \leq 2000) $ — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ $ (1\leq n \leq 2000) $ — the length of the strings. The second and the third lines contain strings $ s $ and $ t $ respectively. The sum of $ n $ over all the test cases does not exceed $ 2000 $ .

输出格式

For each test case, output the minimum number of operations to convert $ s $ to $ t $ . If it is not possible to convert $ s $ to $ t $ , output $ -1 $ instead.

输入输出样例

输入样例 #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

说明

For the $ 1 $ -st test case, since $ s $ and $ t $ are equal, you don't need to apply any operation. For the $ 2 $ -nd test case, you only need to apply one operation on the entire string ab to convert it to ba. For the $ 3 $ -rd test case, you only need to apply one operation on the entire string abc to convert it to cab. For the $ 4 $ -th test case, you need to apply the operation twice: first on the entire string abc to convert it to cab and then on the substring of length $ 2 $ beginning at the second character to convert it to cba. For the $ 5 $ -th test case, you only need to apply one operation on the entire string abab to convert it to baba. For the $ 6 $ -th test case, it is not possible to convert string $ s $ to $ t $ .