Smallest String With Swaps

You are given a string s and a list of pairs of indices. Each pair indicates that you can swap the letters at those indices. You may perform as many swaps as you like. Your task is to output the lexicographically smallest string that can be obtained by performing these swaps.

Hint: The indices that are connected by swaps form a connected component. By sorting the characters within each connected component, you can achieve the smallest possible ordering for that section of the string.

Example 1:
Input: s = "dcab", pairs = [[0, 3], [1, 2]]
Output: "bacd"

Example 2:
Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]]
Output: "abcd"

Note: All indices are zero-indexed.

inputFormat

The input is read from stdin and has the following format:

<string s>
<number of pairs, n>
<index1> <index2>
... (n lines in total)

For example:

dcab
2
0 3
1 2

outputFormat

Output the lexicographically smallest string that can be obtained after performing any number of swaps, printed to stdout.

## sample

dcab
2
0 3
1 2

bacd