Lead Software Engineer

You are given a string S of words. Your task is to count the occurrence of each word present in the string S. A word is a sequence of one or more non-space characters, and there can be multiple spaces between two words, and also there can be leading or trailing spaces in a string S.

For Example:

For the given string  “what we think we become”

“what”,” think”, and “become” occurs 1 time, and “we” occurs 2 times in the given string.

You and your friend found a string ‘S’ of length ‘N’. You love to rearrange the strings, So you decided to rearrange this string too. But this time, your friend puts a constraint on rearranging. He gave you ‘M’ pairs of integers, each pair denoting two indices of the string ‘S’. He also gave you an operation. In one operation, you can select a pair of indices from the given ‘M’ pairs and swap the character present at those indices in the string.

Your task is to rearrange the strings following the given constraints and find the lexicographically smallest string that you can obtain by doing the operations any number of times (might be 0 as well).