给出c++代码，限时1s

以下C++的标准代码实现，时间复杂度为 $O(nm)$：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
char s[N];
char pre[26];

int find(char x)  // 找到x的最终前驱
{
    if (pre[x-'a'] == x) return x;
    return pre[x-'a'] = find(pre[x-'a']);
}

int main()
{
    cin >> m >> n;
    cin >> s;
    for (int i = 0; i < 26; i ++ ) pre[i] = 'a' + i;
    while (n -- )
    {
        char a, b;
        cin >> a >> b;
        pre[find(b)] = find(a);
    }
    for (int i = 0; i < m - 1; i ++ )
        if (find(s[i]) != find(s[i+1]))
        {
            puts("-1");
            return 0;
        }
    for (int i = 0; i < m; i ++ ) cout << pre[s[i]-'a'];
    cout << endl;
    return 0;
}

具体思路和Python3的实现类似，只是用了一个并查集来维护每个字符的最终前驱。注意，由于字符只有 $26$ 个，因此在并查集的实现中可以直接用一个数组来维护。