# [Name Change](https://open.kattis.com/problems/namechange)

## $\texttt{T}$ is sorted and the swaps have special structure
Since $\texttt{T}$ is sorted, it suffices to sort $\texttt{S}$ as much as possible and check whether it's equal to $\texttt{T}$ after sorting. If we are given either that $j=i+1$ or that swaps are transitive (meaning, if we can swap $(i,j)$ and $(j,k)$, then we can swap $(i,k)$) we can use an algorithm similar to bubble sort. One way to do this is to repeatedly perform allowed swaps that make the string more sorted. As it turns out, either of these two conditions is enough to guarantee that this will work.

An example where it doesn't work is

3 2
bac
abc
1 3
2 3

$\texttt{S}$ can clearly be turned into $T$, but there are no possible swaps that make the string more sorted using only one swap.

## The swaps have special structure
Now, $\texttt{T}$ is no longer sorted. How can we handle this? We know how to sort $\texttt{S}$. So why not just sort $\texttt{T}$ and check if they're equal? This works, because we can never get "stuck": if we can go from $\texttt{S}$ to $\texttt{T}$, then we can also go from $\texttt{T}$ to $\texttt{S}$. Thus, both of them should sort to the same thing if we can go from $\texttt{S}$ to $\texttt{T}$.

If you were asked to find an explicit sequence, you could apply the swaps to sort $\texttt{S}$, and then apply the swaps to sort $\texttt{T}$ in reverse.

## Full solution
If you play around with pen and paper, you might notice that you are able to swap any pair of indices that are connected via some direct or indirect sequence of swaps. The proper way to analyze such relations is via graph theory. We will let every index be a node, and every swap be an edge. Within every connected component, we can swap the values at any pair of nodes. It turns out that this means that we can sort every connected component (in fact, we can attain every possible permutation).

Using the idea of sorting as much as possible, we can find the connected components, sort the values within them for both $\texttt{S}$ and $\texttt{T}$ and check whether they're equal.

## Alternative full solution
We could instead check every connected component independently. For two strings to be same after sorting, they must have the same number of occurences of individual characters. Thus, it suffices to count which characters occur in connected components.

## Challenge
How would you find any sequence of swaps that takes you from $\texttt{S}$ to $\texttt{T}$? Hint: || Spanning trees are useful ||