Rotating Substrings

2000ms

262144K

Description:

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.

Input:

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$$$.

Output:

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.

Sample Input:

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

Sample Output:

Note:

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$$$.

Informação

Provedor Codeforces

Código CF1363F