Think of it as a graph problem.

Consider the pairs as connected nodes in the graph, what can you do with a connected component of indices ?

We can sort each connected component alone to get the lexicographically minimum string.