P16377 [NordicOI 2026] Name Change 改名

翻译来源：loj [#5708. 「NordicOI 2026」Name Change](https://loj.ac/p/5708)。 3s，1024MB。 Subtask 0 为样例，Subtask 10 为官方的 Hack（符合所有点的要求）。

你的朋友目前的名字是字符串 $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$ | $5$ | $N, M \leq 100$，所有交换 $(i,j)$ 均满足 $j=i+1$，且 $T$ 已排序[^1] | | $2$ | $14$ | 所有交换 $(i,j)$ 均满足 $j=i+1$ | | $3$ | $10$ | $N, M \leq 100$，$T$ 已排序，且若允许交换 $(i,j)$ 和 $(j,k)$，则也允许交换 $(i,k)$[^2] | | $4$ | $11$ | $N, M \leq 2000$，$T$ 已排序，且若允许交换 $(i,j)$ 和 $(j,k)$，则也允许交换 $(i,k)$ | | $5$ | $17$ | $N, M \leq 2000$，且若允许交换 $(i,j)$ 和 $(j,k)$，则也允许交换 $(i,k)$ | | $6$ | $18$ | 若允许交换 $(i,j)$ 和 $(j,k)$，则也允许交换 $(i,k)$ | | $7$ | $7$ | $N, M \leq 2000$ | | $8$ | $8$ | $T$ 已排序 | | $9$ | $10$ | 无额外限制 | ### 样例解释 在样例 $1$ 中，字符串 $\texttt{abc}$ 的第 $2$ 位和第 $3$ 位字符可以交换，从而得到 $\texttt{acb}$。因此，答案是 `Yes`。该样例满足所有交换都满足 $j=i+1$ 的约束，因此它可能出现在子任务 $2$ 中。由于它不满足 $T$ 已排序的约束，因此它不会出现在子任务 $1$ 中。 在样例 $2$ 中，将 $\texttt{nordic}$ 变为 $\texttt{cdinor}$ 的一种交换序列如下所示：  因此，答案是 `Yes`。请注意，在该样例中，$T$ 已排序，因此它可能出现在子任务 $7, 8$ 和 $9$ 中。它不满足其他子任务的约束条件。 在样例 $3$ 中，无法将 $S$ 转换为 $T$。一种观察方法是：第 $6$ 个字符不参与任何交换，且此处存在不匹配：$S$ 在该位置是 $\texttt{s}$，而 $T$ 在该位置是 $\texttt{t}$。因此，无论进行何种交换，该位置的字符永远不会相同。该样例满足“若允许交换 $(i,j)$ 和 $(j,k)$，则也允许交换 $(i,k)$”的约束。因此，它可能出现在子任务 $5, 6, 7$ 和 $9$ 中（不包括 $3$ 和 $4$，因为 $T$ 未排序）。 [^1]:若字符串中不存在满足左边的字母在字母表中排序晚于右边的字母的相邻字母对，则该字符串被视为已排序。 [^2]:需注意，此条件同样适用于间接交换：若两个下标 $s$ 和 $t$ 可通过间接交换序列 $(s,a), (a,b), \dots, (f, t)$ 进行交换，则直接交换 $(s,t)$ 也必须被允许。