Smallest String with Swaps

You are given a string s of length n and a list of m pairs of indices. Each pair [i, j] indicates that you can swap the characters at positions i and j in the string. Moreover, the swaps can be performed any number of times and can be applied indirectly, meaning that if index i can be swapped with j and j can be swapped with k, then the characters at indices i and k can be indirectly swapped.

Your task is to determine the lexicographically smallest string that can be obtained after performing any number of valid swaps.

Formally, let \(s\) be the given string and the allowed swaps be defined by the pairs \(\{[i_1,j_1], [i_2,j_2], \dots, [i_m,j_m]\}\). You need to produce the smallest string \(s'\) such that by swapping characters only within the connected components (as determined by the swap pairs) of the indices, \(s'\) is lexicographically minimal.

Note: Two indices are considered connected if there is a path using the given swap operations between them.

inputFormat

The input is given via stdin and has the following format:

• The first line contains a string s.
• The second line contains an integer m, the number of pairs.
• The next m lines each contain two space-separated integers, representing a pair of indices that can be swapped.

Indices are 0-indexed.

outputFormat

Output the lexicographically smallest string that can be obtained, printed via stdout.

dcab
2
0 3
1 2

bacd