← 返回题目列表

Codeforces · 1616/E

E. 字典顺序足够小

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

给定两个字符串 $$$s$$$ 和 $$$t$$$,长度相等 $$$n$$$。您可以一步操作交换字符串 $$$s$$$ 的任意两个相邻字符。

您需要找到使字符串 $$$s$$$ 按字典顺序小于字符串 $$$t$$$ 所需的最少操作数。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。

输入

第一行输入包含一个整数 $$$q$$$ ($$$1 \le q \le 10\,000$$$):测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

每个测试用例的第二行包含由 $$$n$$$ 小写英文字母组成的字符串 $$$s$$$。

每个测试用例的第三行包含由 $$$n$$$ 小写英文字母组成的字符串 $$$t$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行中打印使字符串 $$$s$$$ 按字典顺序小于字符串 $$$t$$$ 所需的最少操作数,或者如果不可能,则打印 $$$-1$$$。

示例

输入 #1

4
1
a
a
3
rll
rrr
3
caa
aca
5
ababa
aabba

输出 #1

-1
0
2
2