Swap Coupled Cargo Lex Smallest

A cargo label is a string s of L lowercase letters, positions indexed 0 through L-1. A set of p swap couplings is given; each coupling is a pair of positions (i, j) meaning you may swap the characters at positions i and j any number of times. Positions in the same connected coupling group can therefore be rearranged into any order among themselves.

Output the lexicographically smallest string obtainable.

Input format

• Line 1: two integers L and p.
• Line 2: the string s (exactly L lowercase letters).
• Next p lines: two integers i and j (0-indexed), a swap coupling.

Output format

The lexicographically smallest achievable string.

Constraints

• 1 <= L <= 100000
• 0 <= p <= 200000
• 0 <= i, j < L