← 返回题目列表

Codeforces · 1800/E1

E1. 不可饶恕的诅咒(简易版)

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

这是问题的简单版本。在此版本中,$$$k$$$ 始终为 $$$3$$$。

威森加摩的首席巫师曾经抓住了邪恶巫师德拉赫特,但邪恶巫师又回来了,想要向首席巫师报仇。所以他从他的学生哈利那里偷了咒语$$$s$$$。

拼写 — 是 $$$n$$$ 长度的小写拉丁字母字符串。

Drahyrt 想用不可饶恕的诅咒来代替咒语——字符串 $$$t$$$。

Drahyrt 使用古代魔法,可以在咒语中任意多次地交换距离 $$$k$$$ 或 $$$k+1$$$ 的字母。在此版本的问题中,您可以在 $$$3$$$ 或 $$$4$$$ 的距离处交换字母。换句话说,如果 $$$|i-j|=3$$$ 或 $$$|i-j|=4$$$,Drahyrt 可以更改拼写 $$$s$$$ 中位置 $$$i$$$ 和 $$$j$$$ 的字母。

例如,如果 $$$s = $$$ "talant" 且 $$$t = $$$ "atltna",Drahyrt 可以执行以下操作:

- 交换位置 $$$1$$$ 和 $$$4$$$ 处的字母以获得拼写“aaltnt”。
- 交换位置 $$$2$$$ 和 $$$6$$$ 处的字母以获得拼写“atltna”。

你获得了咒语 $$$s$$$ 和 $$$t$$$。 Drahyrt 可以将法术 $$$s$$$ 更改为 $$$t$$$ 吗?

输入

输入的第一行给出一个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$) - 测试中测试用例的数量。

测试用例的描述如下。

第一行包含两个整数 $$$n, k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$k = 3$$$) — 咒语长度和数字 $$$k$$$,这样 Drahyrt 就可以在距离 $$$k$$$ 或 $$$k+1$$$ 处更改咒语中的字母。

第二行给出拼写 $$$s$$$ — 长度为 $$$n$$$ 的字符串,由小写拉丁字母组成。

第三行给出拼写 $$$t$$$ — 长度为 $$$n$$$ 的字符串,由小写拉丁字母组成。

保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。请注意,所有测试用例的 $$$k$$$ 值的总和没有限制。

输出

对于每个测试用例,如果 Drahyrt 可以将拼写 $$$s$$$ 更改为 $$$t$$$,则在单独的行上输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,行“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

7
6 3
talant
atltna
7 3
abacaba
aaaabbc
12 3
abracadabraa
avadakedavra
5 3
accio
cicao
5 3
lumos
molus
4 3
uwjt
twju
4 3
kvpx
vxpk

输出 #1

YES
YES
NO
YES
NO
YES
NO

注意

第一个例子在条件中解释。

在第二个示例中,我们可以按如下方式进行:

- 交换位置 $$$2$$$ 和 $$$5$$$ 处的字母(距离 $$$3$$$),然后我们得到拼写“aaacbba”。
- 交换位置 $$$4$$$ 和 $$$7$$$ 处的字母(距离 $$$3$$$),然后得到拼写“aaaabbc”。

在第三个例子中,我们可以证明,通过交换距离 $$$3$$$ 或 $$$4$$$ 的字母,不可能从字符串 $$$s$$$ 中得到字符串 $$$t$$$。

例如,在第四个示例中,以下转换顺序是合适的:

- “accio” $$$\rightarrow$$$ “aocic” $$$\rightarrow$$$ “cocia” $$$\rightarrow$$$ “iocca” $$$\rightarrow$$$ “aocci” $$$\rightarrow$$$ “aicco” $$$\rightarrow$$$ “cicao”

在第五个示例中,您可以证明不可能从字符串 $$$t$$$ 中获取字符串 $$$s$$$。

在第六个示例中,交换最外面的两个字母就足够了。