#5708. 「NordicOI 2026」Name Change

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 NordicOI 2026 T1 「Name Change」

你的朋友目前的名字是字符串 $S$。他们希望将名字改为 $T$。

不幸的是，他们所在的国家不允许随意更改姓名。但这区区小事难不倒他们：他们对政府网站进行了一些「调查」，发现了一种交换某些特定位置字符的方法。

更确切地说，他们找到了 $M$ 对位置 $(i, j)$，并且可以交换这些位置上的字符（位置从 $1$ 开始计数）。他们可以进行任意次数的交换操作。

他们现在想知道，是否可以通过执行一系列交换操作，将 $S$ 转换为 $T$。

输入格式

第一行包含两个整数 $N$ 和 $M$ $(1 \leq N, M \leq 2 \cdot 10^5)$，分别表示字符串 $S$ 和 $T$ 的长度以及可用的交换次数。

第二行包含字符串 $S$。$S$ 由 $N$ 个小写英文字母 $\texttt{a-z}$ 组成。

第三行包含字符串 $T$。$T$ 由 $N$ 个小写英文字母 $\texttt{a-z}$ 组成。

最后 $M$ 行，每行包含两个整数 $i, j$ $(1 \leq i < j \leq N)$，表示你的朋友可以交换位置 $i$ 和 $j$ 上的字符。输入中每对位置 $(i,j)$ 最多出现一次。

输出格式

如果可以通过一系列交换操作将 $S$ 转换为 $T$，则输出 Yes。否则，输出 No。

样例 1

输入

3 1
abc
acb
2 3

输出

Yes

在样例 $1$ 中，字符串 $abc$ 的第 $2$ 位和第 $3$ 位字符可以交换，从而得到 $acb$。因此，答案是 Yes。 该样例满足所有交换都满足 $j=i+1$ 的约束，因此它可能出现在子任务 $2$ 中。由于它不满足 $T$ 已排序的约束，因此它不会出现在子任务 $1$ 中。

样例 2

输入

6 6
nordic
cdinor
1 6
2 6
2 3
3 5
4 5
1 4

输出

Yes

在样例 $2$ 中，将 $nordic$ 变为 $cdinor$ 的一种交换序列如下所示：

因此，答案是 Yes。请注意，在该样例中，$T$ 已排序，因此它可能出现在子任务 $7, 8$ 和 $9$ 中。它不满足其他子任务的约束条件。

样例 3

输入

6 6
kattis
sikatt
1 3
1 4
1 5
3 4
3 5
4 5

输出

No

在样例 $3$ 中，无法将 $S$ 转换为 $T$。一种观察方法是：第 $6$ 个字符不参与任何交换，且此处存在不匹配：$S$ 在该位置是 $s$，而 $T$ 在该位置是 $t$。因此，无论进行何种交换，该位置的字符永远不会相同。该样例满足“若允许交换 $(i,j)$ 和 $(j,k)$，则也允许交换 $(i,k)$”的约束。因此，它可能出现在子任务 $5, 6, 7$ 和 $9$ 中（不包括 $3$ 和 $4$，因为 $T$ 未排序）。

数据范围与提示

详细子任务附加限制及分值如下表所示：