P16377 [NordicOI 2026] Name Change

Your friend's name is currently the string $S$. They wish to change their name to $T$. Unfortunately, they live in a country where you aren't allowed to change your name. Such trivial issues won't stop them: they have done some "investigative" work on the government's website and found a way to switch the letters at some pairs of positions. More exactly, they have found $M$ pairs $(i,j)$ and are able to swap characters at positions $i$ and $j$ ($1$-indexed). They are able to do this an arbitrary number of times. They now wonder whether it is possible to transform $S$ to $T$ by performing some sequence of swaps.

The first line contains two integers $N$ and $M\,(1 \leq N, M \leq 2 \cdot 10^5)$, the length of $S$ and $T$, and the number of swaps that are available. The second line of input contains the string $S$. $S$ consists of exactly $N$ lowercase English characters $\texttt{a-z}$. The third line of input contains the string $T$. $T$ consists of exactly $N$ lowercase English characters $\texttt{a-z}$. The final $M$ lines each contain the pair of integers $i,j\,(1 \leq i < j \leq N)$, meaning that your friend is able to swap the characters at positions $i$ and $j$. Each pair of indices $(i,j)$ shows up at most once in the input.

If $S$ can be transformed into $T$ using some sequence of swaps, print `Yes`. Otherwise, print `No`.

### Scoring Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group. |Group|Points|Constraints| |:---:|:----:|:--------:| |$1$ |$5$ |$N,M \le 100$, $j=i+1$ for all swaps $(i,j)$ and $T$ is sorted[^1].| |$2$ |$14$ |$j=i+1$ for all swaps $(i,j)$.| |$3$ |$10$ |$N,M \le 100$, $T$ is sorted and if swaps $(i,j)$ and $(j,k)$ are permitted, then the swap $(i,k)$ is also permitted[^2].| |$4$ |$11$ |$N,M \le 2000$, $T$ is sorted and if swaps $(i,j)$ and $(j,k)$ are permitted, then the swap $(i,k)$ is also permitted.| |$5$ |$17$ |$N,M \le 2000$, if swaps $(i,j)$ and $(j,k)$ are permitted, then the swap $(i,k)$ is also permitted.| |$6$ |$18$ |If swaps $(i,j)$ and $(j,k)$ are permitted, then the swap $(i,k)$ is also permitted.| |$7$ |$7$ |$N,M \le 2000$| |$8$ |$8$ |$T$ is sorted.| |$9$ |$10$ |No additional constraints.| ### Explanation of Samples In sample $1$, the letters at positions $2$ and $3$ of $\texttt{abc}$ can be swapped to obtain $\texttt{acb}$. Thus, the answer is `Yes`. This sample satisfies the constraint that $j=i+1$ for all swaps, so it could appear in subtask $2$. It does not satisfy that $T$ is sorted, so it could not appear in subtask $1$. In sample $2$, one sequence of swaps to go from $\texttt{nordic}$ to $\texttt{cdinor}$ is the following  Therefore, the answer is `Yes`. Note that in this sample, $T$ is sorted, and it could thus appear in subtasks $7$, $8$ and $9$. It does not satisfy enough constraints to appear in other subtasks. In sample $3$, it is impossible to go from $S$ to $T$. One way to see this is that the sixth letter is not part of any swap, and there is a mismatch: $S$ has an $\texttt{s}$ in this position and $T$ has a $\texttt{t}$. Thus, no matter which swaps are made, the letters at this position will always differ. This sample satisfies the constraint that if swaps $(i,j)$ and $(j,k)$ are permitted, then the swap $(i,k)$ is also permitted. Thus, it could appear in subtasks $5$, $6$, $7$ and $9$ (not $3$ and $4$, as $T$ is not sorted). [^1]:A string is considered sorted if there is no pair of adjacent letters where the left one comes later in the alphabet than the right one. [^2]:Note that this condition applies even to indirect swaps: if two indices $s$ and $t$ can be swapped via an indirect sequence of swaps $(s,a), (a,b), \dots , (f, t)$, then the direct swap $(s,t)$ must also be permitted.