← 返回题目列表

Codeforces · 1383/C

C. 字符串转换 2

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

请注意,字符串转换 1 和字符串转换 2 之间的唯一区别在于 Koa 的移动方式。在此版本中,Koa 选择的字母 $$$y$$$ 可以是英文字母表中前 $$$20$$$ 小写字母中的任何字母(阅读声明以更好地理解)。您可以独立解决这些问题。

Koa 考拉有两个字符串 $$$A$$$ 和 $$$B$$$,长度相同 $$$n$$$ ($$$|A|=|B|=n$$$),由前 $$$20$$$ 小写英文字母组成(即从 a 到 t)。

一举Koa:

1. 选择 $$$A$$$ 的位置 $$$p_1, p_2, \ldots, p_k$$$ ($$$k \ge 1; 1 \le p_i \le n; p_i \neq p_j$$$ if $$$i \neq j$$$) 的一些子集,使得 $$$A_{p_1} = A_{p_2} = \ldots = A_{p_k} = x$$$ (即该位置上的所有字母都等于某个字母 $$$x$$$)。
2. 选择任意字母 $$$y$$$(从英文字母表中的前 $$$20$$$ 小写字母开始)。
3. 将位置 $$$p_1、p_2、\ldots、p_k$$$ 中的每个字母设置为字母 $$$y$$$。更正式地说:对于每个 $$$i$$$ ($$$1 \le i \le k$$$) Koa 都设置 $$$A_{p_i} = y$$$。请注意,您只能修改字符串 $$$A$$$ 中的字母。

Koa 想知道要使字符串彼此相等 ($$$A = B$$$) 所需执行的最小步数,或者确定无法使它们相等。帮助她!

输入

每个测试包含多个测试用例。第一行包含 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$A$$$ 和 $$$B$$$ 的长度。

每个测试用例的第二行包含字符串 $$$A$$$ ($$$|A|=n$$$)。

每个测试用例的第三行包含字符串 $$$B$$$ ($$$|B|=n$$$)。

两个字符串均由前 $$$20$$$ 小写英文字母组成(即从 a 到 t)。

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

输出

对于每个测试用例:

在一行上打印她必须执行的最小移动次数才能使字符串彼此相等 ($$$A = B$$$) 或 $$$-1$$$(如果无法使它们相等)。

示例

输入 #1

5
3
aab
bcc
4
cabc
abcb
3
abc
tsr
4
aabd
cccd
5
abcbd
bcdda

输出 #1

2
3
3
2
4

注意

- 在 $$$1$$$-st 测试用例 Koa 中:选择位置 $$$1$$$ 和 $$$2$$$ 并设置 $$$A_1 = A_2 = $$$ b ($$$\color{red}{aa}b \rightarrow \color{blue}{bb}b$$$)。 选择位置 $$$2$$$ 和 $$$3$$$ 并设置 $$$A_2 = A_3 = $$$ c ($$$b\color{red}{bb} \rightarrow b\color{blue}{cc}$$$)。
- 在 $$$2$$$-nd 测试用例 Koa 中:选择位置 $$$1$$$ 和 $$$4$$$ 并设置 $$$A_1 = A_4 = $$$ a ($$$\color{red}{c}ab\color{red}{c} \rightarrow \color{blue}{a}ab\color{blue}{a}$$$)。 选择位置 $$$2$$$ 和 $$$4$$$ 并设置 $$$A_2 = A_4 = $$$ b ($$$a\color{red}{a}b\color{red}{a} \rightarrow a\color{blue}{b}b\color{blue}{b}$$$)。 选择位置 $$$3$$$ 并设置 $$$A_3 = $$$ c ($$$ab\color{red}{b}b \rightarrow ab\color{blue}{c}b$$$)。
- 在 $$$3$$$-rd 测试用例 Koa 中:选择位置 $$$1$$$ 并设置 $$$A_1 = $$$ t ($$$\color{red}{a}bc \rightarrow \color{blue}{t}bc$$$)。 选择位置 $$$2$$$ 并设置 $$$A_2 = $$$ s ($$$t\color{red}{b}c \rightarrow t\color{blue}{s}c$$$)。 选择位置 $$$3$$$ 并设置 $$$A_3 = $$$ r ($$$ts\color{red}{c} \rightarrow ts\color{blue}{r}$$$)。