LEXSTR - Lexicographically Smallest
Taplu and Abhishar loved playing Scrabble. One day they thought of inventing a new game using alphabet tiles. Abhishar wrote a string using tiles and gave a set of pairs (i,j) to Taplu. Pair “i, j” (0 based indexing) means that Taplu can swap the i’th and j’th tile in the string any number of times. He then asks Taplu to give the lexicographically smallest string that can be produced by doing any number of swaps on the original string.
Input
First line contains T (1 <= T <= 10), the number of test cases.
First line of each test case contains the initial string S. Length of string is len (1 <= len <= 100000).
Next line contains the number of pairs M (1 <= M <= 100000).
Next M lines contains pairs i j that means ith character can be swapped with jth character.
Note - i and j can be same and same i, j pair can occur twice.
Output
For each testcase output the lexicographically smallest string that can be made from the initial string.
Example
Input: 1 lmaf 3 0 1 1 2 2 3 Output: aflm
hide comments
evang12:
2022-01-12 04:25:31
string S will only contain lowercase English letters. |
|
Ashish Khurange:
2021-02-09 07:37:07
What are the contents of S? Can it contain upper case char, digits etc? |
Added by: | Rajesh Kumar |
Date: | 2014-09-20 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |