Lexicographically Smallest String

You are given a string s and a list of operations. Each operation is represented by a pair of indices (i, j) which denotes that the characters in the string at positions i and j can be swapped. You can perform any operation any number of times. The goal is to produce the lexicographically smallest string obtainable through arbitrarily many swaps as allowed by the operations.

In other words, note that the swaps allow you to reorder characters within connected components of indices. For a connected component with indices \( i_1,i_2,\dots,i_k \) (sorted in increasing order), if you take the characters at these positions and sort them, placing the smallest character at \( i_1 \), the next smallest at \( i_2 \), and so on, you will obtain the lexicographically smallest arrangement for that component.

Input Constraint: The string can be up to 10⁵ characters long and the number of operations is non-negative.

Note: Indices in the operations are zero-indexed.

inputFormat

The input is given via standard input (stdin) and is structured as follows:

• The first line contains a non-empty string s.
• The second line contains an integer m representing the number of operations.
• The next m lines each contain two space-separated integers i and j indicating that the characters at positions i and j can be swapped.

outputFormat

Output the lexicographically smallest string that can be obtained after performing the allowed operations. The output should be printed via standard output (stdout).

dcab
2
0 3
1 2

bacd