Codeforces Round 646 (Div. 2) |
---|
Finished |
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 —
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.
6 1 a a 2 ab ba 3 abc cab 3 abc cba 4 abab baba 4 abcc aabc
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$$$.
Name |
---|