Problem A
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.
Input
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 a-z.
The third line of input contains the string T. T consists of exactly $N$ lowercase English characters 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.
Output
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 \leq 100$, $j=i+1$ for all swaps $(i,j)$ and T is sorted1. |
|
$2$ |
$14$ |
$j=i+1$ for all swaps $(i,j)$. |
|
$3$ |
$10$ |
$N, M \leq 100$, T is sorted and if swaps $(i,j)$ and $(j,k)$ are permitted, then the swap $(i,k)$ is also permitted2. |
|
$4$ |
$11$ |
$N, M \leq 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 \leq 2000$ and 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 \leq 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 abc can be swapped to obtain 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 nordic to cdinor is the following
![\includegraphics[width=0.4\textwidth ]{sample2.pdf}](/problems/namechange/file/statement/en/img-0001.png)
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 s in this position and T has a 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).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 abc acb 2 3 |
Yes |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 6 nordic cdinor 1 6 2 6 2 3 3 5 4 5 1 4 |
Yes |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 6 kattis sikatt 1 3 1 4 1 5 3 4 3 5 4 5 |
No |
Footnotes
- 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.
- 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.
